Tengo una pila masiva de más de 300 pares de calcetines. ¿Cuál es el algoritmo más rápido que puedo usar para extraer unos 25 pares coincidentes de la pila desordenada?

Interesante problema Si lavaste un poco más a menudo, es posible que no estés en esta situación …

La mayoría de las respuestas parecen suponer que lo único que necesita para combinar los pares de calcetines es el color. Al doblar mi ropa (lo que hago más de una vez al año), tengo que emparejar los calcetines no solo por color, sino también por longitud. Hay largos de tobillo, largos de tripulación y largos de pantorrilla.

Visualmente es más fácil ordenar por color primero, pero sospecho que lo contrario es cierto para un algoritmo. Entonces, al resolver este problema en la computadora, probablemente dividiría la pila en tres pilas por longitud (suponiendo que no haya más longitudes que solo tres). Una vez que se complete ese paso, haría una clasificación de burbujas contra el color en cada una de las tres pilas de longitud. Los tipos de burbujas son efectivos para lotes pequeños.

En este punto, creo que deberías tener tus pares. Los dos primeros en cada pila ahora deben clasificarse por longitud y color. Elimina ese par y toma el siguiente par. Repita hasta que se quede con ese calcetín inexplicable que no puede explicar o encontrar una coincidencia. Es posible que deba verificar debajo de la secadora para ver si perdió su compañero allí. Si es así, deberá agregarlo a la pila y repetir todo el proceso.

Dependiendo de qué tan bien haya codificado el color, los calcetines también pueden clasificarse por la cantidad relativa de desgaste. Un par de medias negras que se hayan usado y lavado 40 veces no serán del mismo color que un par negro nuevo. Si ha utilizado un medio de asignación de color lo suficientemente sensible como para detectar estas gradaciones en color, tendrá pilas de calcetines perfectamente ordenadas.

¿Recuerdas el calcetín no coincidente de antes? El inexplicable? ¿Y si hubiera habido dos así? Puede tener sentido agregar una marca en su código para asegurarse de que la distancia de color entre dos en un par no sea mayor que … x.

Es posible que también deba rediseñar su proceso si tiene otras características. Tengo unos calcetines blancos con gris en la puntera y el talón solamente. Otros son grises en todo el fondo, y otros no tienen color gris, pero son de color blanco puro. Del mismo modo, algunos de mis calcetines negros tienen dedos dorados y otros no. Hay diferentes estilos de tejido que conforman la parte del tubo de cada calcetín … Si esto describe su problema, deberá rediseñarlo para dividir el lote total en subpilas por cualquier criterio discreto que tenga antes de ordenar el color.

Ahora … vamos a lavar los platos. Porque sospecho que si tus calcetines no se han cuidado en un año, tu cocina es un desastre absoluto. No puedes tener la casa así si tienes amigos que vienen.

Vamos a suponer algunos hechos:

– Tienes un color preferido para los calcetines. Y es blanco
– tienes pares de colores distintos al blanco.
– tienes más medias blancas que de otros colores.

Además, suponiendo que desee elegir menos del 10% de sus medias, es muy probable que tenga 25 pares de medias no blancas. Siempre me funciona:

Paso 1. Quítese todos los calcetines blancos (mi experiencia personal dice que puede reducir el espacio de búsqueda en aproximadamente un 50%)

Paso 2. Entre los calcetines restantes, adivina el color más frecuente x . Póngalos a un lado en una pila, etiquetándolo como [math] socks_x [/ math].

Paso 3. Repita el paso 2 hasta que quede un color restante.

Paso 4. Ahora tienes n pilas de calcetines: {[math] socks_ {c_n}, socks_ {c_ {n-1}}, …, socks_ {c_1} [/ math]}, donde [math] c_i [/ ​​math ] es el i-ésimo color elegido y el tamaño [matemático] (calcetines_ {c_i}) <= tamaño (calcetines_ {c_ {i-1}}) [/ matemático]. Sea el conjunto [math] colors = {c_n, c_ {n-1}, ..., c_1} [/ math].

Paso 5. Para cada elemento i en colores : toma la pila [math] socks_i [/ ​​math] . Tome un calcetín de este conjunto. Entre todos los calcetines restantes en la pila, compare uno por uno hasta que tenga una coincidencia. Detente si tienes 25 pares de calcetines . Haga esto para todos los calcetines en [math] socks_i [/ ​​math]. Unir los pares de esta pila es [matemáticas] O (n ^ 2), n = tamaño (calcetines_i) [/ matemáticas].

Paso 6. Toma todos los calcetines que no coincidan y colócalos en el mismo montón para que puedas divertirte usando este algoritmo la próxima vez.

El inconveniente de este algoritmo es que probablemente no encontrarás pares de tu color favorito. Si desea priorizarlo, debe donar algunos pares de calcetines blancos para maximizar sus posibilidades.

¿Por qué 300 pares de calcetines? Primera imagen que salió en mi mente!

Tipo rudo primero. En este caso, no tiene que pensar en lo que está haciendo para el primer paso.

Primer paso:

Divide la pila en 15 grupos de 20 medias. O lo que sea. Desea un buen número de grupos, con cada uno lo suficientemente grande como para que pueda mirar la mayoría de los elementos de la pila con un vistazo.

Si tiene todo tipo de colores, lo ideal es que cada pila contenga una amplia variedad de colores en lugar de combinaciones cercanas.

Segundo paso:

Ahora elige un calcetín de la primera pila y el globo ocular de esa pila para un partido. Saca la no coincidencia más cercana y colócala en una pila nueva (incluso si haces una coincidencia). Luego pasa a la siguiente pila, repitiendo. Comienza una nueva pila cuando tu nueva pila actual alcanza aproximadamente el tamaño que has elegido.

Si consigues una cerilla, únelos y tíralos a un lado, elige un calcetín nuevo del primer montón y comienza de nuevo. Si no hace una combinación después de mirar todas las pilas, deje caer su primer calcetín en la última pila nueva, ya que está bastante seguro de que no contiene una coincidencia. Comenzar de nuevo.

No persigas los calcetines que hayas visto en una de las pilas. Su cerebro insistirá en que sí, pero perderá todo tipo de tiempo.

Su objetivo es reducir el tamaño de las pilas mediante un proceso de clasificación de rechazo. Reduce cuánto tiene que pensar, cuánto maneja, y también puede alejarse de esto y regresar, ya que no tiene que recordar posiciones.

A medida que las pilas disminuyen, debe comenzar a encontrar coincidencias a un ritmo cada vez mayor hasta que esté medio terminado. Pero debe tener sus 25 pares mucho antes de ese punto, y ha sentado las bases para terminar la tarea.

Tienes dos manos. Entonces puedes sacar dos calcetines a la vez y ver cómo se ven.

Entonces haz eso. Saque de dos en dos y mírelos. Si coinciden, déjelos a un lado como un par. De lo contrario, compare cada una con una línea de medias separadas de la pila, haciendo una combinación si encuentra una. Si no encuentra ninguna coincidencia, agréguelas por separado al final de la línea y repita.

Comparar cada calcetín entre sí requeriría operaciones O (n ^ 2), lo que claramente no es factible. Lo que puede hacer es usar algún tipo de algoritmo de agrupación. Primero revise todos los calcetines y agrúpelos por color y longitud, así que tenga una pila para calcetines negros cortos, uno para calcetines azules largos, etc. Esta operación es solo O (n). Entonces tienes un conjunto de problemas más pequeños que deberían ser manejables.