algorithm - ¿Cómo emparejar calcetines de una pila de manera eficiente?

sorting language-agnostic (30)

Como la arquitectura del cerebro humano es completamente diferente a una CPU moderna, esta pregunta no tiene sentido práctico.

Los humanos pueden ganar a los algoritmos de la CPU usando el hecho de que "encontrar un par coincidente" puede ser una operación para un conjunto que no es demasiado grande.

Mi algoritmo:

spread_all_socks_on_flat_surface(); while (socks_left_on_a_surface()) { // Thanks to human visual SIMD, this is one, quick operation. pair = notice_any_matching_pair(); remove_socks_pair_from_surface(pair); }

Al menos esto es lo que estoy usando en la vida real, y lo encuentro muy eficiente. El inconveniente es que requiere una superficie plana, pero suele ser abundante.

Ayer estaba emparejando los calcetines de la ropa limpia y descubrí que la forma en que lo estaba haciendo no es muy eficiente. Estaba haciendo una búsqueda ingenua, recogiendo un calcetín e "iterando" la pila para encontrar su par. Esto requiere una iteración sobre n / 2 * n / 4 = n 2/8 calcetines en promedio.

Como informático, estaba pensando en lo que podía hacer. La clasificación (según el tamaño / color / ...), por supuesto, vino a la mente para lograr una solución O (NlogN).

Hashing u otras soluciones no en el lugar no son una opción, porque no puedo duplicar mis calcetines (aunque podría ser bueno si pudiera).

Entonces, la pregunta es básicamente:

Dado un montón de n pares de calcetines, que contienen 2n elementos (suponiendo que cada calcetín tiene exactamente un par coincidente), ¿cuál es la mejor manera de emparejarlos eficientemente con espacio extra logarítmico? (Creo que puedo recordar esa cantidad de información si es necesario).

Apreciaré una respuesta que aborde los siguientes aspectos:

Una solución teórica general para un gran número de calcetines.
El número real de calcetines no es tan grande, no creo que mi cónyuge y yo tengamos más de 30 pares. (Y es bastante fácil de distinguir entre mis calcetines y los de ella; ¿también se puede usar?)
¿Es equivalente al problema de la distinción del elemento ?

Como solución práctica:

Hacer rápidamente pilas de calcetines fácilmente distinguibles. (Decir por color)
Ordena rápidamente cada pila y usa la longitud del calcetín para comparar. Como humano, puede tomar una decisión bastante rápida qué calcetín usar para particionar que evite el peor de los casos. (Puedes ver varios calcetines en paralelo, úsalo para tu ventaja).
Deje de clasificar las pilas cuando hayan alcanzado un umbral en el que se sienta cómodo para encontrar pares de puntos y calcetines desmontables al instante

Si tiene 1000 calcetines, con 8 colores y una distribución promedio, puede hacer 4 pilas de cada 125 calcetines en c * n. Con un umbral de 5 calcetines, puedes clasificar cada pila en 6 carreras. (Si cuenta 2 segundos para lanzar un calcetín en la pila correcta, le llevará poco menos de 4 horas).

Si solo tiene 60 calcetines, 3 colores y 2 tipos de calcetines (los suyos / los de su esposa), puede ordenar cada pila de 10 calcetines en 1 corridas (nuevamente, umbral = 5). (Contando 2 segundos te llevará 2 min).

La clasificación inicial de los cubos acelerará su proceso, ya que divide sus n calcetines en k compartimientos en c*n por lo que solo tendrá que hacer el trabajo de c*n*log(k) . (No teniendo en cuenta el umbral). Así que, en general, se trata del trabajo de n*c*(1 + log(k)) , donde c es el momento de arrojar un calcetín a una pila.

Este enfoque será favorable en comparación con cualquier método c*x*n + O(1) aproximadamente siempre que log(k) < x - 1 .

En informática, esto puede ser útil: tenemos una colección de n cosas , un orden en ellas (longitud) y también una relación de equivalencia (información adicional, por ejemplo, el color de los calcetines). La relación de equivalencia nos permite hacer una partición de la colección original, y en cada clase de equivalencia nuestro orden aún se mantiene. La asignación de una cosa a su clase de equivalencia se puede hacer en O (1), por lo que solo se necesita O (n) para asignar cada elemento a una clase. Ahora hemos utilizado nuestra información adicional y podemos proceder de cualquier manera para clasificar cada clase. La ventaja es que los conjuntos de datos ya son significativamente más pequeños.

El método también puede ser anidado, si tenemos múltiples relaciones de equivalencia -> hacer pilas de colores, que dentro de cada partición de pila en textura, que ordenar en longitud. Cualquier relación de equivalencia que cree una partición con más de 2 elementos que tengan un tamaño similar traerá una mejora de la velocidad sobre la clasificación (siempre que podamos asignar directamente un calcetín a su pila), y la clasificación puede realizarse muy rápidamente en conjuntos de datos más pequeños.

El límite teórico es O (n) porque necesitas tocar cada calcetín (a menos que algunos ya estén emparejados de alguna manera).

Puedes lograr O (n) con la ordenación de radix . Solo necesitas elegir algunos atributos para los cubos.

Primero puedes elegir (la de ella, la mía), dividirlas en 2 pilas,
luego use colores (puede tener cualquier orden para los colores, por ejemplo, alfabéticamente por nombre de color) - divídalos en pilas por color (recuerde mantener el orden inicial del paso 1 para todos los calcetines en la misma pila),
luego la longitud del calcetín,
luego textura, ....

Si puede elegir un número limitado de atributos, pero suficientes atributos que puedan identificar de forma única cada par, debe hacerlo en O (k * n), que es O (n) si podemos considerar que k es limitado.

Esta pregunta es en realidad profundamente filosófica. En el fondo se trata de si el poder de las personas para resolver problemas (el "wetware" de nuestros cerebros) es equivalente a lo que pueden lograr los algoritmos.

Un algoritmo obvio para la clasificación de calcetines es:

Let N be the set of socks that are still unpaired, initially empty for each sock s taken from the dryer if s matches a sock t in N remove t from N, bundle s and t together, and throw them in the basket else add s to N

Ahora la informática en este problema tiene que ver con los pasos

"si s se empareja con un calcetín t en N". ¿Qué tan rápido podemos "recordar" lo que hemos visto hasta ahora?
"quitar t de N" y "agregar s a N". ¿Qué tan caro es hacer un seguimiento de lo que hemos visto hasta ahora?

Los seres humanos usarán varias estrategias para efectuar esto. La memoria humana es asociativa , algo así como una tabla hash donde los conjuntos de características de los valores almacenados se emparejan con los valores correspondientes. Por ejemplo, el concepto de "coche rojo" se asigna a todos los coches rojos que una persona es capaz de recordar. Alguien con una memoria perfecta tiene un mapeo perfecto. La mayoría de las personas son imperfectas en este sentido (y en la mayoría de los demás). El mapa asociativo tiene una capacidad limitada. Las asignaciones pueden desaparecer de la existencia en varias circunstancias (una cerveza demasiada), ser registradas por error ("Me pareció que su nombre era Betty, no Nettie"), o nunca ser sobrescritas aunque observamos que la verdad ha cambiado ("la de papá "evoca" Firebird naranja "cuando en realidad sabíamos que lo había cambiado por el Camaro rojo).

En el caso de los calcetines, la recuperación perfecta significa que mirar un calcetín siempre produce la memoria de su hermano t , incluida la información suficiente (donde se encuentra en la tabla de planchar) para ubicar t en un tiempo constante. Una persona con memoria fotográfica logra 1 y 2 en tiempo constante sin falta.

Alguien con una memoria menos que perfecta puede usar algunas clases de equivalencia de sentido común basadas en características dentro de su capacidad de seguimiento: tamaño (papá, mamá, bebé), color (verdoso, rojizo, etc.), patrón (argyle, plano, etc.) , estilo (footie, rodilla-alto, etc.). Así que la tabla de planchar se dividiría en secciones para las categorías. Esto generalmente permite que la categoría se ubique en el tiempo constante por la memoria, pero luego se necesita una búsqueda lineal a través de la categoría "cubo".

Alguien sin memoria o imaginación (lo siento) mantendrá los calcetines en una pila y hará una búsqueda lineal de toda la pila.

Un monstruo aseado podría usar etiquetas numéricas para pares como alguien sugirió. Esto abre la puerta a una ordenación total, lo que permite al ser humano usar exactamente los mismos algoritmos que podríamos usar con una CPU: búsqueda binaria, árboles, hashes, etc.

Por lo tanto, el "mejor" algoritmo depende de las cualidades de wetware / hardware / software que lo ejecuta y de nuestra disposición a "hacer trampa" al imponer un orden total en pares. Sin duda, un " meta " algoritmo es contratar al mejor clasificador de calcetines del mundo: una persona o máquina que puede adquirir y almacenar rápidamente un gran conjunto de conjuntos de atributos de calcetines en una memoria asociativa de 1-1 con búsqueda de tiempo constante, insertar, y eliminar. Tanto personas como máquinas como esta pueden ser adquiridas. Si tiene uno, puede emparejar todos los calcetines en tiempo O (N) para N pares, lo que es óptimo. Las etiquetas de pedido total le permiten utilizar el hash estándar para obtener el mismo resultado con una computadora humana o de hardware.

Esto es hacer la pregunta incorrecta. La pregunta correcta es: ¿por qué dedico tiempo a clasificar calcetines? ¿Cuánto cuesta anualmente, cuando valora su tiempo libre para X unidades monetarias de su elección?

Y la mayoría de las veces, esto no es solo un tiempo libre, es tiempo libre matutino , que podría estar pasando en la cama, tomando un sorbo de café, o saliendo un poco antes y sin ser atrapado en el tráfico.

A menudo es bueno dar un paso atrás y pensar una forma de solucionar el problema.

¡Y hay un camino!

Encuentra un calcetín que te guste. Tenga en cuenta todas las características relevantes: color en diferentes condiciones de iluminación, calidad y durabilidad en general, confort en diferentes condiciones climáticas y absorción de olores. También es importante que no pierdan elasticidad en el almacenamiento, por lo que las telas naturales son buenas y deberían estar disponibles en una envoltura de plástico.

Es mejor si no hay diferencia entre los calcetines derecho e izquierdo, pero no es crítico. Si los calcetines son simétricos de izquierda a derecha, encontrar un par es una operación O (1), y clasificar los calcetines es una operación aproximada O (M), donde M es el número de lugares en su casa, que ha cubierto con calcetines, idealmente algunos pequeño número constante.

Si eligió un par elegante con un calcetín izquierdo y derecho diferente, haciendo una clasificación de cubos completos al pie izquierdo y derecho, tome O (N + M), donde N es el número de calcetines y M es el mismo que el anterior. Alguien más puede dar la fórmula de iteraciones promedio para encontrar el primer par, pero el peor de los casos para encontrar un par con búsqueda a ciegas es N / 2 + 1, lo que se convierte en un caso astronómicamente improbable para un N razonable. Esto puede acelerarse usando una imagen avanzada Algoritmos de reconocimiento y heurística, al escanear la pila de calcetines sin clasificar con Mk1 Eyeball .

Por lo tanto, un algoritmo para lograr la eficiencia de emparejamiento de calcetines O (1) (suponiendo un calcetín simétrico) es:

Necesita estimar cuántos pares de calcetines necesitará para el resto de su vida, o tal vez hasta que se retire y se mueva a climas más cálidos sin necesidad de usar los calcetines nunca más. Si usted es joven, también puede estimar cuánto tiempo lleva antes de que todos tengamos robots de clasificación de calcetines en nuestras casas, y todo el problema se vuelva irrelevante.
Debe averiguar cómo puede pedir su calcetín seleccionado a granel, y cuánto cuesta, y cómo se lo entregan.
¡Pide los calcetines!
Deshazte de tus calcetines viejos.

Un paso alternativo 3 implicaría comparar los costos de comprar la misma cantidad de calcetines quizás más baratos unos cuantos pares a la vez a lo largo de los años y agregar el costo de clasificar los calcetines, pero confíe en mi opinión: ¡comprar en grandes cantidades es más barato! Además, los calcetines en almacenamiento aumentan en valor a la tasa de inflación del precio de las acciones, que es más de lo que obtendría en muchas inversiones. Por otra parte, también hay un costo de almacenamiento, pero los calcetines realmente no ocupan mucho espacio en el estante superior de un armario.

Problema resuelto. Entonces, obtenga nuevos calcetines, deseche / done sus viejos y viva feliz para siempre sabiendo que está ahorrando dinero y tiempo todos los días por el resto de su vida.

Lo que hago es que levanto el primer calcetín y lo coloco (por ejemplo, en el borde del tazón de la lavandería). Luego levanto otro calcetín y verifico si es lo mismo que el primer calcetín. Si es así, los quito a ambos. Si no lo es, lo pongo al lado del primer calcetín. Luego levanto el tercer calcetín y lo comparo con los dos primeros (si todavía están allí). Etc.

~~Este enfoque se puede implementar bastante fácilmente en una matriz, suponiendo que "quitar" los calcetines es una opción.~~ En realidad, ni siquiera es necesario "quitar" los calcetines. Si no necesita clasificar los calcetines (ver más abajo), puede moverlos y terminar con una matriz que tiene todos los calcetines dispuestos en pares en la matriz.

Suponiendo que la única operación para los calcetines es comparar la igualdad, este algoritmo sigue siendo básicamente un algoritmo n ² , aunque no conozco el caso promedio (nunca aprendí a calcularlo).

La clasificación, por supuesto, mejora la eficiencia, especialmente en la vida real, donde puede "insertar" fácilmente un calcetín entre otros dos calcetines. En computación, lo mismo podría lograrse con un árbol, pero eso es espacio extra. Y, por supuesto, estamos de vuelta en NlogN (o un poco más, si hay varios calcetines que son iguales según los criterios de clasificación, pero no del mismo par).

Aparte de eso, no puedo pensar en nada, pero este método parece ser bastante eficiente en la vida real. :)

Se han propuesto soluciones de clasificación , pero la clasificación es demasiado : no necesitamos orden; Solo necesitamos grupos de igualdad .

Así que el hash sería suficiente (y más rápido).

Para cada color de calcetines, formar una pila . Iterar sobre todos los calcetines en su cesta de entrada y distribuirlos en las pilas de colores .
Iterar sobre cada pila y distribuirla por alguna otra métrica (por ejemplo, patrón) en el segundo conjunto de pilas
Aplique recursivamente este esquema hasta que haya distribuido todos los calcetines en pilas muy pequeñas que pueda procesar visualmente de inmediato

SQL Server está realizando este tipo de partición hash recursiva cuando necesita unir o unir hash en conjuntos de datos enormes. Distribuye su flujo de entrada de compilación en muchas particiones que son independientes. Este esquema se ajusta a cantidades arbitrarias de datos y varias CPU de forma lineal.

No necesita una partición recursiva si puede encontrar una clave de distribución (clave hash) que proporcione suficientes depósitos para que cada depósito sea lo suficientemente pequeño como para ser procesado muy rápidamente. Desafortunadamente, no creo que los calcetines tengan tal propiedad.

Si cada calcetín tuviera un número entero llamado "PairID", podría distribuirlos fácilmente en 10 cubos de acuerdo con PairID % 10 (el último dígito).

La mejor partición del mundo real que se me ocurre es crear un rectángulo de pilas : una dimensión es el color, la otra es el patrón. ¿Por qué un rectángulo? Porque necesitamos O (1) acceso aleatorio a las pilas. (Un cuboid 3D también funcionaría, pero eso no es muy práctico).

Actualizar:

¿Qué pasa con el paralelismo ? ¿Pueden varios humanos igualar los calcetines más rápido?

La estrategia de paralelización más simple es hacer que varios trabajadores tomen la cesta de entrada y coloquen los calcetines en las pilas. Esto solo aumenta mucho - imagina a 100 personas peleando en 10 pilas. Los costos de sincronización (que se manifiestan como colisiones manuales y comunicación humana) destruyen la eficiencia y la aceleración (¡consulte la Ley de Escalabilidad Universal !). ¿Es esto propenso a los puntos muertos ? No, porque cada trabajador solo necesita acceder a una pila a la vez. Con un solo "bloqueo" no puede haber un interbloqueo. Livelocks podría ser posible dependiendo de cómo los humanos coordinan el acceso a las pilas. Es posible que solo usen un backoff aleatorio, como las tarjetas de red hacen eso a nivel físico para determinar qué tarjeta puede acceder exclusivamente al cable de red. Si funciona para NICs , también debería funcionar para humanos.
Se escala casi indefinidamente si cada trabajador tiene su propio conjunto de pilas . Los trabajadores pueden tomar grandes trozos de calcetines de la canasta de entrada (muy poca contención, ya que rara vez lo hacen) y no necesitan sincronizarse cuando distribuyen los calcetines (porque tienen pilas de hilos locales). Al final, todos los trabajadores necesitan unir sus conjuntos de pilas. Creo que eso se puede hacer en O (registro (conteo de trabajadores * pilas por trabajador)) si los trabajadores forman un árbol de agregación .

¿Qué pasa con el problema de la distinción del elemento ? Como lo indica el artículo, el problema de la distinción de elementos se puede resolver en O(N) . Esto es lo mismo para el problema de los calcetines (también O(N) , si solo necesita un paso de distribución (propuse varios pasos solo porque los humanos son malos en los cálculos: un solo paso es suficiente si distribuye en md5(color, length, pattern, ...) , es decir, un hash perfecto de todos los atributos)).

Claramente, uno no puede ir más rápido que O(N) , por lo que hemos alcanzado el límite inferior óptimo .

Aunque las salidas no son exactamente iguales (en un caso, solo un booleano. En el otro caso, los pares de calcetines), las complejidades asintóticas son las mismas.

Caso 1 : todos los calcetines son idénticos (esto es lo que hago en la vida real, por cierto).

Elige cualquiera de los dos para hacer un par. Tiempo constante.

Caso 2 : hay un número constante de combinaciones (propiedad, color, tamaño, textura, etc.).

Utilice la ordenación de radix . Esto es solo un tiempo lineal ya que la comparación no es necesaria.

Caso 3 : El número de combinaciones no se conoce de antemano (caso general).

Tenemos que hacer una comparación para comprobar si dos calcetines vienen en par. Elija uno de los algoritmos de ordenación basados en la comparación O(n log n) .

Sin embargo, en la vida real, cuando el número de calcetines es relativamente pequeño (constante), estos algoritmos teóricamente óptimos no funcionarán bien. Puede llevar incluso más tiempo que la búsqueda secuencial, lo que teóricamente requiere tiempo cuadrático.

Estás tratando de resolver el problema equivocado.

Solución 1: Cada vez que pongas calcetines sucios en la cesta de la ropa, haz un nudo pequeño. De esa forma no tendrás que hacer ninguna clasificación después del lavado. Piense en ello como registrar un índice en una base de datos Mongo. Un poco de trabajo por delante para algunos ahorros de CPU en el futuro.

Solución 2: si es invierno, no tienes que usar calcetines a juego. Somos programadores. Nadie necesita saber, mientras funcione.

Solución 3: Difunde el trabajo. Desea realizar un proceso de CPU tan complejo de forma asíncrona, sin bloquear la interfaz de usuario. Toma ese montón de calcetines y metelos en una bolsa. Solo busca un par cuando lo necesites. De esa manera, la cantidad de trabajo que se necesita es mucho menos notable.

¡Espero que esto ayude!

Respuesta no algorítmica, pero "eficiente" cuando lo hago:

paso 1) desecha todos tus calcetines existentes
paso 2) vaya a Walmart y compre por paquetes de 10 n paquetes de blanco y m paquetes de negro. No hay necesidad de otros colores en la vida cotidiana.

Sin embargo, de vez en cuando, tengo que hacer esto nuevamente (calcetines perdidos, calcetines dañados, etc.), y odio descartar calcetines perfectamente buenos con demasiada frecuencia (¡y me hubiera gustado que siguieran vendiendo la misma referencia de calcetines!), Así que hace poco tomé un enfoque diferente.

Respuesta algorítmica:

Tenga en cuenta que si dibuja solo un calcetín para la segunda pila de calcetines, como está haciendo, las probabilidades de encontrar el calcetín a juego en una búsqueda ingenua son bastante bajas.

Así que escoge cinco de ellos al azar y memoriza su forma o su longitud.

¿Por que cinco? Por lo general, los seres humanos son buenos, están recordando entre cinco y siete elementos diferentes en la memoria de trabajo (un poco como el equivalente humano de una pila RPN , cinco es un valor predeterminado seguro.

Recoge uno de la pila de 2n-5.
Ahora busque una coincidencia (coincidencia de patrones visuales: los humanos son buenos en eso con una pila pequeña) dentro de los cinco que dibujó, si no encuentra uno, añádalo a sus cinco.
Sigue escogiendo calcetines al azar y compáralos con tus calcetines 5 + 1 para un partido. A medida que tu pila crezca, reducirá tu rendimiento pero aumentará tus probabilidades. Mucho mas rápido.

Siéntase libre de escribir la fórmula para calcular cuántas muestras debe dibujar para una probabilidad del 50% de una coincidencia. IIRC es una ley hipergeométrica.

Hago eso todas las mañanas y rara vez necesito más de tres sorteos, pero tengo n pares similares (alrededor de 10, dar o tomar los perdidos) de calcetines blancos en forma de m . Ahora puedes estimar el tamaño de mi pila de acciones :-)

Por cierto , encontré que la suma de los costos de transacción de clasificar todos los calcetines cada vez que necesitaba un par era mucho menor que hacerlo una vez y atar los calcetines. Un Justo a tiempo funciona mejor porque entonces no tiene que atar los calcetines, y también hay un rendimiento marginal decreciente (es decir, sigue buscando esos dos o tres calcetines que cuando están en algún lugar de la lavandería y que necesita). para terminar de emparejar tus calcetines y pierdes tiempo en eso).

Considere una tabla hash de tamaño ''N''.

Si asumimos una distribución normal, entonces el número estimado de ''inserciones'' para tener al menos un calcetín asignado a un compartimiento es NlogN (es decir, todos los compartimientos están llenos)

Derivé esto como parte de otro rompecabezas, pero me encantaría que me demostraran que estoy equivocado. Aquí está mi artículo de blog sobre el mismo

Deje que ''N'' corresponda a un límite superior aproximado en el número de colores / patrones únicos de calcetines que tenga.

Una vez que tenga una colisión (también conocida como: una coincidencia), simplemente quite ese par de calcetines. Repita el mismo experimento con el siguiente lote de calcetines NlogN. La belleza de esto es que podrías estar haciendo comparaciones paralelas de NlogN (resolución de colisión) debido a la forma en que funciona la mente humana. :-)

Costo: Mover calcetines -> calcetines altos, encontrar / buscar en línea -> pequeños

Lo que queremos hacer es reducir el número de movimientos y compensar con el número de búsquedas. Además, podemos utilizar el entorno de múltiples sistemas del Homo Sapiens para mantener más cosas en el caché de descisión.

X = Tuyo, Y = Tus cónyuges

De la pila A de todos los calcetines:

Elija dos calcetines, coloque el calcetín X correspondiente en la línea X y el calcetín Y en la línea Y en la siguiente posición disponible.

Hacer hasta que A esté vacío.

Para cada línea X e Y

Elija el primer calcetín en línea, busque a lo largo de la línea hasta que encuentre el calcetín correspondiente.
Poner en la correspondiente línea acabada de calcetines.
Opcional Mientras busca en la línea y el calcetín actual que está viendo es idéntico al anterior, realice el paso 2 para estos calcetines.

Opcionalmente, en el paso uno, toma dos calcetines de esa línea en lugar de dos, ya que la memoria caché es lo suficientemente grande como para que podamos identificar rápidamente si alguno de los calcetines coincide con el actual en la línea que está observando. Si tienes la suerte de tener tres brazos, puedes analizar tres calcetines al mismo tiempo, dado que la memoria del sujeto es lo suficientemente grande.

Hacer hasta que tanto X como Y estén vacías.

Hecho

Sin embargo, como esto tiene una complejidad similar como orden de selección, el tiempo empleado es mucho menor debido a las velocidades de E / S (medias móviles) y búsqueda (búsqueda de una línea de una media).

Enfoque del mundo real:

Tan pronto como sea posible, quite los calcetines de la pila sin clasificar de uno en uno y colóquelos en pilas delante de usted. Las pilas deben estar dispuestas de forma algo eficiente en cuanto al espacio, con todos los calcetines apuntando en la misma dirección; el número de pilas está limitado por la distancia que puede alcanzar fácilmente. La selección de una pila sobre la cual colocar un calcetín debe ser, tan rápido como sea posible, colocando un calcetín en una pila de aparentemente como calcetines; el tipo ocasional I (poner un calcetín en una pila a la que no pertenece) o el tipo II (poner un calcetín en su propia pila cuando hay una pila existente de calcetines similares) se puede tolerar el error: la consideración más importante es la velocidad. Una vez que todos los calcetines están en pilas, recorra rápidamente las pilas de múltiples calcetines creando pares y quitándolos (estos se dirigen al cajón). Si hay calcetines que no coinciden en la pila, vuelva a amontonarlos hasta su mejor pila (dentro de la pila tan rápida como sea posible). Cuando se hayan procesado todas las pilas de calcetines múltiples, haga coincidir los calcetines emparejados restantes que no se emparejaron debido a errores de tipo II. Whoosh, has terminado, y tengo muchos calcetines y no los lavo hasta que una gran parte esté sucia. Otra nota práctica: muevo la parte superior de uno de un par de calcetines sobre el otro, aprovechando sus propiedades elásticas, para que permanezcan juntos mientras son transportados al cajón y mientras están en el cajón.

He terminado de emparejar mis calcetines ahora mismo, y descubrí que la mejor manera de hacerlo es la siguiente:

Elija uno de los calcetines y guárdelo (cree un ''cubo'' para ese par)
Si el siguiente es el par del anterior, colóquelo en el depósito existente, de lo contrario, cree uno nuevo.

En el peor de los casos, significa que tendrá n / 2 cubos diferentes, y tendrá n-2 determinaciones acerca de qué cubo contiene el par del calcetín actual. Obviamente, este algoritmo funciona bien si tiene solo unos pocos pares; Lo hice con 12 pares.

No es tan científico, pero funciona bien :)

He tomado pasos simples para reducir mi esfuerzo en un proceso que toma O (1) tiempo.

Al reducir mis entradas a uno de dos tipos de calcetines (calcetines blancos para recreación, calcetines negros para el trabajo), solo necesito determinar cuál de los dos calcetines tengo en la mano. (Técnicamente, ya que nunca se lavan juntos, he reducido el proceso a O (0) tiempo)

Se requiere un esfuerzo inicial para encontrar calcetines deseables y comprar en cantidad suficiente para eliminar la necesidad de los calcetines existentes. Como lo había hecho antes de mi necesidad de calcetines negros, mi esfuerzo era mínimo, pero el kilometraje puede variar.

Tal esfuerzo inicial se ha visto muchas veces en un código muy popular y efectivo. Los ejemplos incluyen # DEFINE''ing pi a varios decimales (existen otros ejemplos, pero ese es el que me viene a la mente en este momento).

Los calcetines, ya sean reales o una estructura de datos análoga, se suministrarán en pares.

La respuesta más simple es antes de permitir que el par se separe, se debería haber inicializado una única estructura de datos para el par que contenía un puntero hacia el calcetín izquierdo y derecho, lo que permite hacer referencia a los calcetines directamente o mediante su par. Un calcetín también se puede extender para contener un puntero a su compañero.

Esto resuelve cualquier problema de emparejamiento computacional al eliminarlo con una capa de abstracción.

Aplicando la misma idea al problema práctico de emparejar calcetines, la respuesta aparente es: no permitas que tus calcetines queden sin emparejarse. Los calcetines se proporcionan como un par, se ponen en el cajón como un par (tal vez uniéndolos juntos), se usan como un par. Pero el punto donde es posible desemparejar es en la lavadora, por lo que todo lo que se requiere es un mecanismo físico que permita que los calcetines permanezcan juntos y se laven eficientemente.

Hay dos posibilidades físicas:

Para un objeto ''par'' que mantiene un puntero a cada calcetín, podríamos tener una bolsa de tela que usamos para mantener los calcetines juntos. Esto parece una sobrecarga masiva.

Pero para cada calcetín para mantener una referencia a la otra, hay una solución clara: un popper (o un "botón de presión" si eres estadounidense), como estos:

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

Luego, todo lo que debe hacer es juntar los calcetines justo después de quitarlos y ponerlos en la canasta de lavado, y nuevamente eliminó el problema de la necesidad de combinar los calcetines con una abstracción física del concepto de "par".

Para decir qué tan eficiente es emparejar los calcetines de una pila, primero debemos definir la máquina, ya que la vinculación no se realiza ya sea por turbo ni por una máquina de acceso aleatorio, que normalmente se utilizan como base para una Análisis algorítmico.

La máquina

La máquina es una abstracción de un elemento del mundo real llamado ser humano. Es capaz de leer desde el entorno a través de un par de ojos. Y nuestro modelo de máquina es capaz de manipular el entorno utilizando 2 brazos. Las operaciones lógicas y aritméticas se calculan utilizando nuestro cerebro (con suerte ;-)).

También debemos considerar el tiempo de ejecución intrínseco de las operaciones atómicas que pueden llevarse a cabo con estos instrumentos. Debido a restricciones físicas, las operaciones que se llevan a cabo con un brazo u ojo tienen una complejidad de tiempo no constante. Esto se debe a que no podemos mover un montón de calcetines sin fin con un brazo ni un ojo puede ver el calcetín superior en un montón de calcetines sin fin.

Sin embargo, la física mecánica también nos da algo bueno. No estamos limitados a mover a lo sumo un calcetín con un brazo. Podemos mover un par de ellos a la vez.

Por lo tanto, según el análisis anterior, las siguientes operaciones deben usarse en orden descendente:

Operaciones lógicas y aritméticas.
lecturas ambientales
modificaciones ambientales

También podemos aprovechar el hecho de que las personas solo tienen una cantidad muy limitada de calcetines. Así que una modificación ambiental puede involucrar a todos los calcetines en la pila.

El algoritmo

Así que aquí está mi sugerencia:

Extiende todos los calcetines en la pila sobre el piso.
Encuentra un par mirando los calcetines en el suelo.
Repita desde 2 hasta que no se pueda hacer un par.
Repita desde 1 hasta que no haya calcetines en el suelo.

La operación 4 es necesaria, porque al extender calcetines sobre el piso, algunos calcetines pueden ocultar otros. Aquí está el análisis del algoritmo:

El analisis

El algoritmo termina con alta probabilidad. Esto se debe al hecho de que uno no puede encontrar pares de calcetines en el paso número 2.

Para el siguiente análisis de tiempo de ejecución del par de npares de calcetines, suponemos que al menos la mitad de los 2ncalcetines no están ocultos después del paso 1. Por lo tanto, en el caso promedio podemos encontrar n/2pares. Esto significa que el bucle es el paso 4 se ejecuta O(log n)veces. Paso 2 se ejecuta O(n^2)tiempos. Entonces podemos concluir:

El algoritmo incluye O(ln n + n)modificaciones ambientales (paso 1 O(ln n)y toma cada par de calcetines del piso)
El algoritmo involucra O(n^2)lecturas ambientales del paso 2
El algoritmo incluye O(n^2)operaciones lógicas y aritméticas para comparar un calcetín con otro en el paso 2

Así que tenemos una complejidad total de tiempo de ejecución de O(r*n^2 + w*(ln n + n))dónde ry wson los factores para la lectura ambiental y las operaciones de escritura ambiental, respectivamente, para una cantidad razonable de calcetines. El costo de las operaciones lógicas y aritméticas se omite, porque suponemos que se necesita una cantidad constante de operaciones lógicas y aritméticas para decidir si 2 calcetines pertenecen al mismo par. Esto puede no ser factible en todos los escenarios.

Se me ocurrió otra solución que no prometía menos operaciones, ni menos consumo de tiempo, pero debería intentarse ver si puede ser una heurística lo suficientemente buena como para proporcionar menos consumo de tiempo en grandes series de pares de calcetines.

Condiciones previas: no hay garantía de que haya los mismos calcetines. Si son del mismo color, no significa que tengan el mismo tamaño o patrón. Los calcetines se barajan aleatoriamente. Puede haber un número impar de calcetines (algunos faltan, no sabemos cuántos). Prepárese para recordar una variable "índice" y establézcala en 0.

El resultado tendrá una o dos pilas: 1. "emparejado" y 2. "faltante"

Heurístico:

Encuentra el calcetín más distintivo.
Encuentra su partido.
Si no hay coincidencia, póngalo en la pila "faltante".
Repita desde 1. hasta que no haya más calcetines más distintivos.
Si hay menos de 6 calcetines, ve a 11.
Empareja ciegamente todos los calcetines a su vecino (no lo empaques)
Encuentre todos los pares emparejados, empáquelos y mueva los pares empacados a la pila "emparejada"; Si no hubiera nuevas coincidencias, aumente el "índice" en 1
Si "índice" es mayor que 2 (esto podría depender del valor del número de calcetines porque con un mayor número de calcetines hay menos posibilidades de emparejarlos ciegamente) vaya a 11
Barajar el resto
Ir a 1
Olvida el "índice"
Elige un calcetín
Encuentra su par
Si no hay un par para el calcetín, muévalo a la pila "faltante"
Si se encuentra una coincidencia, empareje, empareje y muévala a la pila "emparejada"
Si todavía hay más de un calcetín pasa a 12.
Si solo queda uno, ve a 14.
Sonrisa satisfecha :)

Además, también se puede agregar un control para detectar calcetines dañados, como si se eliminaran. Podría insertarse entre 2 y 3, y entre 13 y 14.

Estoy deseando escuchar sobre cualquier experiencia o corrección.

Si la operación de "movimiento" es bastante costosa, y la operación de "comparación" es barata, y usted necesita mover todo el conjunto de todos modos, a un búfer donde la búsqueda es mucho más rápida que en el almacenamiento original ... simplemente integre la clasificación en lo obligatorio movimiento.

Descubrí que integrar el proceso de clasificación para colgar en seco hace que sea muy fácil. Necesito recoger cada calcetín de todos modos, colgarlo (moverlo) y no me cuesta nada colgarlo en un lugar específico de las cuerdas. Ahora solo no para forzar la búsqueda de todo el búfer (las cuerdas) elijo colocar los calcetines por color / sombra. Más oscuro a la izquierda, más brillante a la derecha, más colorido en el frente, etc. Ahora, antes de colgar cada calcetín, miro en su "proximidad derecha" si ya hay uno que coincida, esto limita el "escaneo" a otros 2 y otros , Cuelgo el otro justo al lado. Luego los enrollo en pares mientras los quito de las cuerdas, cuando están secos.

Ahora, esto puede no parecer tan diferente de "formar pilas por color" sugerido por las respuestas principales, pero primero, al no seleccionar pilas discretas sino rangos, no tengo ningún problema en clasificar si "púrpura" va a pila "roja" o "azul"; sólo va entre. Y luego, al integrar dos operaciones (colgar para secar y clasificar) la sobrecarga de clasificación mientras se cuelga es como el 10% de lo que sería una clasificación separada.

Aquí hay un límite inferior Omega (n log n) en el modelo basado en comparación. (La única operación válida es comparar dos calcetines.)

Supongamos que sabes que tus calcetines 2n están dispuestos de esta manera:

p ₁ p ₂ p ₃ ... p _n p _{f (1)} p _{f (2)} ... p _{f (n)}

donde f es una permutación desconocida del conjunto {1,2, ..., n}. Saber esto no puede dificultar el problema. ¡No hay! salidas posibles (coincidencias entre la primera y la segunda mitad), lo que significa que necesita comparaciones de log (n!) = omega (n log n). Esto se puede obtener por clasificación.

Ya que está interesado en las conexiones con el problema de la distinción de elementos: probar que el límite Omega (n log n) para la distinción de elementos es más difícil, porque la salida es binaria sí / no. Aquí, la salida tiene que ser una coincidencia y el número de salidas posibles es suficiente para obtener un límite decente. Sin embargo, hay una variante conectada a la distinción del elemento. Supongamos que te dan 2n calcetines y te preguntas si se pueden emparejar de forma única. Puede obtener una reducción de ED enviando (a ₁ , a ₂ , ..., a _n ) a (a ₁ , a ₁ , a ₂ , a ₂ , ..., a _n , a _n ). (Parenthetic, la prueba de la dureza de ED es muy interesante,a través de la topología .)

Creo que debería haber un límite Omega (n ² ) para el problema original si solo permites pruebas de igualdad. Mi intuición es: considere un gráfico en el que agregue un borde después de una prueba, y sostenga que si el gráfico no es denso, la salida no se determina de manera única.

Así es como lo hago, para p pares de calcetines ( n = 2p calcetines individuales):

Agarra un calcetín al azar de la pila.
Para el primer calcetín, o si todos los calcetines elegidos anteriormente han sido emparejados, simplemente coloque el calcetín en la primera "ranura" de un "conjunto" de calcetines sin par delante de usted.
Si tiene uno o más calcetines sin emparejar seleccionados, verifique su calcetín actual contra todos los calcetines sin emparejar en la matriz.
- Es posible separar los calcetines en clases o tipos generales (blanco / negro, tobillo / equipo, atletismo / vestimenta) cuando se construye su matriz, y "profundizar" para comparar solo like-like.
- Si encuentra una coincidencia aceptable, junte ambos calcetines y elimínelos de la matriz.
- Si no lo hace, coloque el calcetín actual en la primera ranura abierta de la matriz.
Repita con cada calcetín.

El peor de los escenarios de este esquema es que cada par de calcetines es lo suficientemente diferente como para que tenga que coincidir exactamente, y que los primeros n / 2 calcetines que elija sean todos diferentes. Este es su escenario O (n ² ), y es extremadamente improbable. Si el número de tipos únicos de calcetín t es menor que el número de pares p = n / 2 , y los calcetines en cada tipo son lo suficientemente similares (generalmente en términos relacionados con el desgaste), que cualquier calcetín de ese tipo puede emparejarse con cualquier otra, entonces, como he deducido anteriormente, el número máximo de calcetines que nunca tendrá que comparar a es t , después de lo cual el siguiente que tire voluntademparejar uno de los calcetines sin par. Este escenario es mucho más probable en el cajón de calcetines promedio que en el caso más desfavorable, y reduce la complejidad del caso más desfavorable a O (n * t) donde normalmente t << n .

Cada vez que levantes un calcetín, ponlo en un lugar. Luego, el siguiente calcetín que recoja, si no coincide con el primer calcetín, colóquelo junto al primero. Si lo hace, hay un par. De esta manera, realmente no importa cuántas combinaciones haya, y solo hay dos posibilidades para cada calcetín que levantes, ya sea que tenga una coincidencia que ya esté en tu conjunto de calcetines, o no, lo que significa agregarlo a un lugar en la matriz.

Esto también significa que es casi seguro que nunca tendrás todos tus calcetines en la matriz, porque los calcetines se quitarán a medida que se ajusten.

Coge un primer calcetín y colócalo en una mesa. Ahora escoge otro calcetín; si coincide con el primero escogido, colóquelo encima del primero. Si no es así, colóquelo en la mesa a poca distancia de la primera. Elige un tercer calcetín; si coincide con alguno de los dos anteriores, colóquelo encima de ellos o, si no, colóquelo a una pequeña distancia del tercero. Repita hasta que haya recogido todos los calcetines.

Cree una tabla hash que se utilizará para los calcetines no coincidentes, utilizando el patrón como hash. Iterar sobre los calcetines uno por uno. Si el calcetín tiene una coincidencia de patrón en la tabla hash, saque el calcetín de la mesa y haga un par. Si el calcetín no tiene una coincidencia, póngalo en la mesa.

Cuando ordeno los calcetines, hago un ordenamiento aproximado de radix , dejando caer los calcetines cerca de otros calcetines del mismo color / tipo de patrón. Excepto en el caso en que puedo ver una coincidencia exacta en / cerca de la ubicación que estoy a punto de dejar caer el calcetín, extraigo el par en ese punto.

Casi todos los otros algoritmos (incluida la respuesta de puntuación más alta por usr ) ordenan y luego eliminan los pares. Encuentro que, como humano, es mejor minimizar el número de calcetines que se consideran al mismo tiempo.

Hago esto por:

Escoger un calcetín distintivo (lo que me llame la atención primero en la pila).
Comenzar una clasificación de radix desde esa ubicación conceptual tirando de los calcetines de la pila basándose en la similitud con esa.
Coloque el nuevo calcetín cerca de la pila actual, con una distancia basada en qué tan diferente es. Si se encuentra colocando el calcetín encima de otro porque es idéntico, forme el par allí y retírelos. Esto significa que las comparaciones futuras requieren menos esfuerzo para encontrar el lugar correcto.

Esto aprovecha la capacidad humana para hacer coincidencias difusas en el tiempo O (1), que es algo equivalente al establecimiento de un mapa hash en un dispositivo informático.

Al tirar primero de los calcetines distintivos, deja espacio para "acercar" las características que son menos distintivas, para empezar.

Después de eliminar el fluro de color, los calcetines con rayas y los tres pares de calcetines largos, es posible que termines con los calcetines en su mayoría blancos aproximadamente ordenados por el uso que tienen.

En algún momento, las diferencias entre los calcetines son lo suficientemente pequeñas como para que otras personas no noten la diferencia, y no es necesario ningún esfuerzo adicional.

De su pregunta queda claro que no tiene mucha experiencia real con la lavandería :). Necesita un algoritmo que funcione bien con una pequeña cantidad de calcetines que no se puedan emparejar.

Las respuestas hasta ahora no hacen un buen uso de nuestras capacidades de reconocimiento de patrones humanos. El juego de Set proporciona una pista de cómo hacerlo bien: coloca todos los calcetines en un espacio bidimensional para que ambos puedan reconocerlos bien y alcanzarlos fácilmente con las manos. Esto te limita a un área de aproximadamente 120 * 80 cm o menos. Desde allí, selecciona los pares que reconoces y elimínalos. Pon calcetines extra en el espacio libre y repite. Si lava para personas con calcetines fácilmente reconocibles (los niños pequeños vienen a la mente), puede hacer una clasificación de radix seleccionando esos calcetines primero. Este algoritmo funciona bien solo cuando el número de calcetines individuales es bajo

El problema de clasificar tus n pares de calcetines es O (n) . Antes de tirarlos en la cesta de la ropa , ensarta la izquierda a la derecha. Al sacarlos, corta el hilo y coloca cada par en su cajón: 2 operaciones en n pares, así que O (n).

Ahora la siguiente pregunta es simplemente si usted hace su propia ropa y su esposa hace la suya. Ese es un problema probable en un dominio de problemas completamente diferente . :)

Espero poder aportar algo nuevo a este problema. Noté que todas las respuestas descuidan el hecho de que hay dos puntos en los que puede realizar el preprocesamiento , sin ralentizar el rendimiento general de la lavandería.

Además, no necesitamos asumir una gran cantidad de calcetines, incluso para familias numerosas. Los calcetines se sacan del cajón y se usan, y se tiran en un lugar (tal vez un contenedor) donde se quedan antes de ser lavados. Si bien no llamaría a dicho contenedor una pila LIFO, diría que es seguro asumir que

la gente tira sus dos calcetines aproximadamente en la misma área de la papelera,
la papelera no es aleatoria en ningún punto, y por lo tanto
cualquier subconjunto tomado de la parte superior de este contenedor generalmente contiene ambos calcetines de un par.

Dado que todas las lavadoras que conozco son limitadas en tamaño (independientemente de cuántos calcetines tengas que lavar), y la aleatorización real ocurre en la lavadora, no importa cuántos calcetines tengamos, siempre tenemos pequeños subconjuntos que casi no contienen singletons

Nuestras dos etapas de preprocesamiento son "poner los calcetines en el tendedero" y "Sacar los calcetines del tendedero", lo que tenemos que hacer, para obtener calcetines que no solo estén limpios sino también secos. Al igual que con las lavadoras, los tendederos son finitos, y asumo que tenemos toda la parte de la línea donde ponemos los calcetines a la vista.

Aquí está el algoritmo para put_socks_on_line ():

while (socks left in basket) { take_sock(); if (cluster of similar socks is present) { Add sock to cluster (if possible, next to the matching pair) } else { Hang it somewhere on the line, this is now a new cluster of similar-looking socks. Leave enough space around this sock to add other socks later on } }

No pierda el tiempo moviendo los calcetines o buscando la mejor combinación, todo esto debe hacerse en O (n), que también necesitaríamos para ponerlos en la línea sin clasificar. Los calcetines aún no están emparejados, solo tenemos varios grupos de similitud en la línea. Es útil que tengamos un conjunto limitado de calcetines aquí, ya que esto nos ayuda a crear "buenos" agrupamientos (por ejemplo, si solo hay calcetines negros en el conjunto de calcetines, el agrupamiento por colores no sería lo correcto)

Aquí está el algoritmo para take_socks_from_line ():

while(socks left on line) { take_next_sock(); if (matching pair visible on line or in basket) { Take it as well, pair ''em and put ''em away } else { put the sock in the basket }

Debo señalar que para mejorar la velocidad de los pasos restantes, es aconsejable no elegir aleatoriamente el siguiente calcetín, sino tomar secuencialmente calcetín tras calcetín de cada grupo. Ambos pasos de preprocesamiento no toman más tiempo que solo poner los calcetines en la línea o en la canasta, lo que tenemos que hacer sin importar qué, así que esto debería mejorar enormemente el rendimiento de la lavandería.

Después de esto, es fácil hacer el algoritmo de partición hash. Por lo general, alrededor del 75% de los calcetines ya están emparejados, lo que me deja con un subconjunto muy pequeño de calcetines, y este subconjunto ya está (algo) agrupado (no introduzco mucha entropía en mi cesta después de los pasos de preprocesamiento). Otra cosa es que los grupos restantes tienden a ser lo suficientemente pequeños para ser manejados a la vez, por lo que es posible sacar un grupo completo de la canasta.

Aquí está el algoritmo para sort_remaining_clusters ():

while(clusters present in basket) { Take out the cluster and spread it Process it immediately Leave remaining socks where they are }

Después de eso, sólo quedan unos pocos calcetines. Aquí es donde introduzco calcetines que no estaban pareados anteriormente en el sistema y proceso los calcetines restantes sin ningún algoritmo especial; los calcetines restantes son muy pocos y se pueden procesar visualmente muy rápido.

Para todos los calcetines restantes, asumo que sus contrapartes aún están sin lavar y los guardan para la siguiente iteración. Si registra un crecimiento de calcetines no emparejados con el tiempo (una "fuga de calcetines"), debe revisar su contenedor: podría ser aleatorio (¿tiene gatos que duermen allí?)

Sé que estos algoritmos toman muchas suposiciones: un contenedor que actúa como una especie de pila LIFO, una lavadora normal limitada y un tendedero normal limitado, pero esto todavía funciona con un gran número de calcetines.

Acerca del paralelismo: siempre que lance ambos calcetines en el mismo recipiente, puede paralelizar fácilmente todos esos pasos.

Mi solución no corresponde exactamente a sus requisitos, ya que requiere formalmente O(n)espacio "extra". Sin embargo, considerando mis condiciones es muy eficiente en mi aplicación práctica. Por eso creo que debería ser interesante.

Combinar con otra tarea

La condición especial en mi caso es que no uso una secadora, simplemente cuelgo mis paños en un secador de ropa común. Colgar telas requiere O(n)operaciones (por cierto, siempre considero un problema de empaque de basura aquí) y el problema por su naturaleza requiere el espacio "extra" lineal. Cuando saco un nuevo calcetín del cubo, intento colgarlo junto a su par si el par ya está colgado. Si es un calcetín de un par nuevo, le dejo un espacio al lado.

Oracle Machine es mejor ;-)

Obviamente, se requiere un poco de trabajo extra para comprobar si el calcetín correspondiente ya está colgado en alguna parte y podría dar una solución O(n^2)con un coeficiente 1/2para una computadora. Pero en este caso, el "factor humano" es en realidad una ventaja. Por lo general, puedo O(1)identificar (casi ) rápidamente el calcetín correspondiente si ya estaba colgado (probablemente esté involucrado un almacenamiento en el cerebro imperceptible). Considérelo como una especie de "oráculo" limitado como en Oracle Machine ;-) Nosotros, los humanos tenemos estas ventajas sobre las máquinas digitales en algunos casos ;-)

Lo tengo casi `O(n)`!

De este modo, al conectar el problema de emparejar los calcetines con el problema de colgar telas, obtengo O(n)"espacio extra" de forma gratuita, y tengo una solución que está O(n)a tiempo, requiere un poco más de trabajo que las telas colgadas y permite acceder de inmediato a un par completo de calcetines incluso en una muy mala mañana de lunes ... ;-)

List<Sock> UnSearchedSocks = getAllSocks(); List<Sock> UnMatchedSocks = new list<Sock>(); List<PairOfSocks> PairedSocks = new list<PairOfSocks>(); foreach (Sock newSock in UnsearchedSocks) { Sock MatchedSock = null; foreach(Sock UnmatchedSock in UnmatchedSocks) { if (UnmatchedSock.isPairOf(newSock)) { MatchedSock = UnmatchedSock; break; } } if (MatchedSock != null) { UnmatchedSocks.remove(MatchedSock); PairedSocks.Add(new PairOfSocks(MatchedSock, NewSock)); } else { UnmatchedSocks.Add(NewSock); } }