Cómo emparejar calcetines de una stack de manera eficiente?

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, escogiendo un calcetín e “iterando” el montón para encontrar su pareja. Esto requiere iterar en promedio sobre n / 2 * n / 4 = n 2/8 calcetines.

Como científico informático, ¿estaba pensando qué podría hacer? La clasificación (según tamaño / color / …) por supuesto vino a la mente para lograr una solución O (NlogN).

Las soluciones hash u otras soluciones in situ no son una opción, porque no puedo duplicar mis calcetines (aunque podría ser bueno si pudiera).

Entonces, la pregunta es básicamente:

Dada una stack 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 hasta un espacio extra logarítmico? (Creo que puedo recordar esa cantidad de información si es necesario).

Agradecería una respuesta que aborde los siguientes aspectos:

  • Una solución teórica general para una gran cantidad de calcetines.
  • La cantidad real de medias no es tan grande, no creo que mi pareja y yo tengamos más de 30 pares. (Y es bastante fácil distinguir entre mis calcetines y los de ella; ¿se puede usar también?)
  • ¿Es equivalente al problema de distinción de elementos ?

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

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

  1. Para cada color de calcetines, forma una stack . Itere sobre todos los calcetines en su cesta de entrada y distribúyalos en las stacks de colores .
  2. Iterate sobre cada stack y distribúyela por alguna otra métrica (por ejemplo, patrón) en el segundo conjunto de stacks
  3. Aplica de forma recursiva este esquema hasta que hayas distribuido todos los calcetines en stacks muy pequeñas que puedes procesar visualmente de inmediato

Este tipo de partición de hash recursivo se está realizando realmente por SQL Server cuando se necesita combinar hash o hash en grandes conjuntos de datos. Distribuye su flujo de entrada de construcción en muchas particiones que son independientes. Este esquema escala a cantidades arbitrarias de datos y múltiples CPU linealmente.

No necesita particiones recursivas si puede encontrar una clave de distribución (tecla de almohadilla) que proporcione cubos suficientes para que cada segmento sea lo suficientemente pequeño como para ser procesado muy rápidamente. Desafortunadamente, no creo que los calcetines tengan esa propiedad.

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

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


Actualizar:

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

  1. La estrategia de paralelización más simple es hacer que varios trabajadores tomen de la canasta de entrada y coloquen los calcetines en las stacks. Esto solo aumenta mucho: imagina a 100 personas peleando por 10 montones. 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 estancamientos ? No, porque cada trabajador solo necesita acceder a un montón a la vez. Con solo un “candado” no puede haber un punto muerto. Livelocks podría ser posible dependiendo de cómo los humanos coordinan el acceso a las stacks. Tal vez solo utilicen la desactivación aleatoria como las tarjetas de red en un nivel físico para determinar qué tarjeta puede acceder exclusivamente al cable de la red. Si funciona para NIC , también debería funcionar para humanos.
  2. Se escala casi indefinidamente si cada trabajador tiene su propio conjunto de stacks . Los trabajadores pueden tomar grandes trozos de calcetines de la canasta de entrada (muy poca contención ya que lo hacen con poca frecuencia) y no necesitan sincronizarse cuando distribuyen los calcetines (porque tienen montones locales). Al final, todos los trabajadores necesitan unir sus conjuntos de pilotes. Creo que se puede hacer en O (log (conteo de trabajadores * stacks por trabajador)) si los trabajadores forman un árbol de agregación .

¿Qué pasa con el problema de distinción de elementos ? Como dice el artículo, el problema de 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 paso es suficiente si lo 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 las mismas (en un caso, solo un booleano. En el otro caso, los pares de calcetines), las complejidades asintóticas son las mismas.

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

Los seres humanos pueden ganar los algoritmos de CPU utilizando 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 por lo general es abundante.

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

Elige a dos de ellos para hacer un par. Tiempo constante.

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

Use el tipo de raíz . Este es solo el tiempo lineal ya que no se requiere comparación.

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

Tenemos que hacer una comparación para verificar si dos calcetines vienen en pareja. Elija uno de los algoritmos de clasificació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ían bien. Puede llevar incluso más tiempo que la búsqueda secuencial, que teóricamente requiere tiempo cuadrático.

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

  • paso 1) descarta todos tus calcetines existentes

  • paso 2) ir a Walmart y comprarlos por paquetes de 10 – n paquete de blanco ym paquetes de negro. No hay necesidad de otros colores en la vida cotidiana.

Sin embargo, en ocasiones, tengo que hacer esto otra vez (calcetines perdidos, medias dañadas, etc.), y odio tirar calcetines perfectamente buenos con demasiada frecuencia (y ¡ojalá siguieran vendiendo los mismos calcetines de referencia!), Así que recientemente tomé un enfoque diferente.

Respuesta algorítmica:

Considere que si dibuja solo un calcetín para la segunda stack de calcetines, como lo está haciendo, sus probabilidades de encontrar el calcetín coincidente en una búsqueda ingenua son bastante bajas.

  • Así que escoja cinco de ellos al azar y memorice su forma o su longitud.

¿Por que cinco? Por lo general, los humanos somos buenos recordando entre cinco y siete elementos diferentes en la memoria de trabajo, un poco como el equivalente humano de una stack RPN , cinco es un valor predeterminado seguro.

  • Recoge uno de la stack de 2n-5.

  • Ahora busque una coincidencia (coincidencia de patrones visuales – los humanos son buenos en eso con una pequeña stack) dentro de los cinco que dibujó, si no encuentra uno, luego agréguelo a sus cinco.

  • Mantenga los calcetines al azar de la stack y compárelos con los calcetines 5 + 1 para un partido. A medida que su stack crezca, reducirá su rendimiento pero boostá sus probabilidades. Mucho mas rápido.

No dude en escribir la fórmula para calcular cuántas muestras debe dibujar para obtener un 50% de probabilidades 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, más o menos) de calcetines blancos en forma de m . Ahora puedes estimar el tamaño de mi stack de acciones 🙂

Por cierto , descubrí que la sum de los costos de transacción de clasificar todos los calcetines cada vez que necesitaba un par era mucho menor que hacerlo una sola vez y unir los calcetines. Un just-in-time funciona mejor porque entonces no tiene que atar los calcetines, y también hay un retorno marginal decreciente (es decir, sigue buscando esos dos o tres calcetines que cuando en algún lugar de la lavandería y que necesita) para terminar de hacer coincidir tus calcetines y pierdes tiempo con eso).

Lo que hago es levantar el primer calcetín y dejarlo (por ejemplo, en el borde del recipiente para lavar la ropa). Luego tomo otro calcetín y compruebo si es igual al primer calcetín. Si es así, los elimino a los dos. Si no es así, lo coloco al lado del primer calcetín. Luego tomo el tercer calcetín y lo comparo con los dos primeros (si todavía están allí). Etc.

Este enfoque se puede implementar con bastante facilidad en una matriz, suponiendo que “quitar” calcetines es una opción. En realidad, ni siquiera necesitas “quitar” los calcetines. Si no necesita ordenar los calcetines (ver a continuación), 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 calcetines es comparar por igualdad, este algoritmo sigue siendo básicamente un algoritmo n 2 , aunque no conozco el caso promedio (nunca aprendí a calcular eso).

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 informática, un árbol puede lograr lo mismo, pero eso es espacio extra. Y, por supuesto, estamos de regreso 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. 🙂

Esto es hacer la pregunta incorrecta. La pregunta correcta es, ¿por qué gasto tiempo ordenando 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, no se trata de ningún tiempo libre, es el tiempo libre de la mañana , que podría estar pasando en la cama, o bebiendo su café, o saliendo un poco temprano y no quedar atrapado en el tráfico.

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

¡Y hay una manera!

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 generales, comodidad 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 del pie izquierdo y derecho, pero no es crítico. Si los calcetines son simétricos entre la izquierda y la derecha, encontrar un par es O (1) operación, y ordenar los calcetines es O (M) operación aproximada, donde M es el número de lugares en su casa, que ha ensuciado con calcetines, idealmente algunos pequeño número constante.

Si eliges un par elegante con diferente calcetín izquierdo y derecho, haciendo una clasificación completa del cubo a los cubos izquierdo y derecho del pie, toma 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 caso para encontrar un par con búsqueda ciega es N / 2 + 1, lo que se convierte en un caso astronómicamente improbable para N. razonable. Esto se puede acelerar utilizando una imagen avanzada algoritmos de reconocimiento y heurística, al escanear el montón de calcetines sin clasificar con Mk1 Eyeball .

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

  1. Debe estimar cuántos pares de calcetines necesitará para el rest de su vida, o tal vez hasta que se retire y se mueva a climas más cálidos sin necesidad de usar calcetines nunca más. Si eres joven, también puedes calcular cuánto tiempo pasará antes de que todos tengamos robots de clasificación de calcetines en nuestros hogares, y todo el problema se vuelve irrelevante.

  2. Debe averiguar cómo puede pedir el calcetín seleccionado a granel, cuánto cuesta y entregan.

  3. Ordene los calcetines!

  4. Deshazte de tus viejos calcetines.

Un paso 3 alternativo implicaría comparar los costos de comprar la misma cantidad de calcetines quizás más baratos con algunos pares a la vez a lo largo de los años y agregar el costo de clasificar los calcetines, pero tome mi palabra: ¡comprar a granel es más barato! Además, los calcetines en almacenamiento aumentan en valor a la tasa de inflación de los precios 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 no ocupan mucho espacio en el estante superior de un armario.

Problema resuelto. Por lo tanto, solo consigue calcetines nuevos, tira / dona tus viejos y vive feliz para siempre sabiendo que estás ahorrando dinero y tiempo todos los días para el rest de tu vida.

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

Puede lograr O (n) con clasificación de radix . Solo necesita elegir algunos atributos para los cubos.

  1. Primero puedes elegir (la suya, la mía) dividirlos en 2 montones,
  2. luego use colores (puede tener cualquier orden para los colores, por ejemplo, alfabéticamente por nombre de color) – divídalos en montones por color (recuerde mantener el orden inicial del paso 1 para todos los calcetines en el mismo montón),
  3. luego la longitud del calcetín,
  4. 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.

Como una solución práctica:

  1. Haga rápidamente montones de calcetines fácilmente distinguibles. (Decir por color)
  2. Coloca rápidamente cada montón y usa la longitud del calcetín para comparar. Como ser humano, puede tomar una decisión bastante rápida que utilizar para particionar y evitar el peor de los casos. (Puedes ver varios calcetines en paralelo, ¡utiliza eso para tu ventaja!)
  3. Deje de clasificar las stacks cuando alcanzan un umbral en el que se siente cómodo para encontrar pares de puntos y calcetines no deseables al instante

Si tiene 1000 calcetines, con 8 colores y una distribución promedio, puede hacer 4 stacks de 125 calcetines en c * n de tiempo. Con un umbral de 5 calcetines, puedes ordenar cada montón en 6 carreras. (Contar 2 segundos para tirar un calcetín en el montón correcto le tomará poco menos de 4 horas).

Si solo tienes 60 calcetines, 3 colores y 2 tipos de calcetines (el tuyo o el de tu esposa) puedes clasificar cada stack de 10 calcetines en 1 carrera (Umbral de nuevo = 5). (Contar 2 segundos le tomará 2 minutos).

La clasificación inicial de los depósitos acelerará el proceso, ya que divide los n calcetines en k cubetas en c*n vez, de modo que solo tendrá que hacer c*n*log(k) . (No teniendo en cuenta el umbral). Así que todo lo que haces sobre n*c*(1 + log(k)) funciona, donde c es el momento de tirar un calcetín sobre una stack.

Este enfoque será favorable en comparación con cualquier método c*x*n + O(1) más o menos tan largo como 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. El mapeo 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 se puede anidar, si tenemos múltiples relaciones de equivalencia -> hacer stacks de colores, que dentro de cada partición de stack en la textura, que ordenar por la longitud. Cualquier relación de equivalencia que cree una partición con más de 2 elementos que tengan un tamaño par traerá una mejora de velocidad sobre la clasificación (siempre que podamos asignar directamente un calcetín a su stack), y la clasificación puede suceder muy rápidamente en conjuntos de datos más pequeños.

Esta pregunta es realmente profundamente filosófica. En esencia se trata de si el poder de las personas para resolver problemas (el “wetware” de nuestros cerebros) es equivalente a lo que se puede lograr mediante algoritmos.

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

 Let N be the set of socks that are still unpaird, 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 ciencia de la computación en este problema es todo acerca de los pasos

  1. “si s se empareja con un calcetín t en N”. ¿Qué tan rápido podemos “recordar” lo que hemos visto hasta ahora?
  2. “eliminar 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 autos rojos que una persona es capaz de recordar. Alguien con una memoria perfecta tiene una asignación perfecta. La mayoría de las personas son imperfectas a este respecto (y la mayoría de las demás). El mapa asociativo tiene una capacidad limitada. Las asignaciones pueden desaparecer en varias circunstancias (una cerveza demasiada), registrarse por error (“Creo que su nombre era Betty, no Nettie”), o nunca se sobrescribirán aunque observemos que la verdad ha cambiado (“papá el coche “evoca” a Orange Firebird “cuando en realidad sabíamos que había cambiado eso 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 , incluyendo suficiente información (donde está en la tabla de planchar) para ubicar t en tiempo constante. Una persona con memoria fotográfica logra tanto 1 como 2 en tiempo constante sin falta.

Alguien con memoria menos que perfecta podría usar algunas clases de equivalencia de sentido común basadas en las características dentro de su capacidad para rastrear: tamaño (papá, mamá, bebé), color (verdoso, rojizo, etc.), patrón (argyle, liso, etc.) , estilo (footie, hasta la rodilla, etc.). Entonces, la tabla de planchar se dividiría en secciones para las categorías. Esto generalmente permite que la categoría se ubique en un tiempo constante por 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) simplemente mantendrá los calcetines en una stack y hará una búsqueda lineal de la stack completa.

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

Entonces, el “mejor” algoritmo depende de las cualidades del wetware / hardware / software que lo está ejecutando y de nuestra disposición a “hacer trampa” al imponer un orden total en pares. Ciertamente, un “mejor” meta- algoritmo es contratar el 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 calcetín en una memoria asociativa 1-1 con búsqueda de tiempo constante, insertar, y eliminar Se pueden conseguir personas y máquinas como esta. Si tiene uno, puede emparejar todos los calcetines en el tiempo O (N) para N pares, lo cual es óptimo. The total order tags allow you to use standard hashing to get the same result with either a human or hardware computer.

You are trying to solve the wrong problem.

Solution 1: Each time you put dirty socks in your laundry basket, tie them in a little knot. That way you will not have to do any sorting after the washing. Think of it like registering an index in a Mongo database. A little work ahead for some CPU savings in the future.

Solution 2: If it’s winter, you don’t have to wear matching socks. We are programmers. Nobody needs to know, as long as it works.

Solution 3: Spread the work. You want to perform such a complex CPU process asynchronously, without blocking the UI. Take that pile of socks and stuff them in a bag. Only look for a pair when you need it. That way the amount of work it takes is much less noticeable.

¡Espero que esto ayude!

Here’s an Omega(n log n) lower bound in comparison based model. (The only valid operation is comparing two socks.)

Suppose that you know that your 2n socks are arranged this way:

p 1 p 2 p 3 … p n p f(1) p f(2) … p f(n)

where f is an unknown permutation of the set {1,2,…,n}. Knowing this cannot make the problem harder. There are n! possible outputs (matchings between first and second half), which means you need log(n!) = Omega(n log n) comparisons. This is obtainable by sorting.

Since you are interested in connections to element distinctness problem: proving the Omega(n log n) bound for element distinctness is harder, because the output is binary yes/no. Here, the output has to be a matching and the number of possible outputs suffices to get a decent bound. However, there’s a variant connected to element distinctness. Suppose you are given 2n socks and wonder if they can be uniquely paird. You can get a reduction from ED by sending (a 1 , a 2 , …, a n ) to (a 1 , a 1 , a 2 , a 2 , …, a n , a n ). (Parenthetically, the proof of hardness of ED is very interesting, via topology .)

I think that there should be an Omega(n 2 ) bound for the original problem if you allow equality tests only. My intuition is: Consider a graph where you add an edge after a test, and argue that if the graph is not dense the output is not uniquely determined.

Cost: Moving socks -> high, finding/search socks in line -> small

What we want to do is reduce the number of moves, and compensate with the number of searches. Also, we can utilize the multithreded environment of the Homo Sapiens to hold more things in the descision cache.

X = Yours, Y = Your spouses

From pile A of all socks:

Pick two socks, place corresponding X sock in X line, and Y sock in Y line at next available position.

Do until A is empty.

For each line X and Y

  1. Pick the first sock in line, search along the line until it finds the corresponding sock.

  2. Put into the corresponding finished line of socks.

  3. Optional While you are searching the line and and the current sock you are looking at is identical to the previous, do step 2 for these socks.

Optionally to step one, you pick up two sock from that line instead of two, as the caching memory is large enough we can quickly identify if either sock matches the current one on the line you are observing. If you are fortunate enough to have three arms, you could possibly parse three socks at the same time given that the memory of the subject is large enough.

Do until both X and Y is empty.

Hecho

However, as this have simillar complexity as selection sort, the time taken is far less due to the speeds of I/O(moving socks) and search(searching the line for a sock).

This is how I actually do it, for p pairs of socks ( n = 2p individual socks):

  • Grab a sock at random from the pile.
  • For the first sock, or if all previously-chosen socks have been paird, simply place the sock into the first “slot” of an “array” of unpaird socks in front of you.
  • If you have one or more selected unpaird socks, check your current sock against all the unpaird socks in the array.
    • It is possible to separate socks into general classes or types (white/black, ankle/crew, athletic/dress) when building your array, and “drill-down” to only compare like-for-like.
    • If you find an acceptable match, put both socks together and remove them from the array.
    • If you do not, put the current sock into the first open slot in the array.
  • Repeat with every sock.

The worst-case scenario of this scheme is that every pair of socks is different enough that it must be matched exactly, and that the first n/2 socks you pick are all different. This is your O (n 2 ) scenario, and it’s extremely unlikely. If the number of unique types of sock t is less than the number of pairs p = n/2 , and the socks in each type are alike enough (usually in wear-related terms) that any sock of that type can be paird with any other, then as I inferred above, the maximum number of socks you will ever have to compare to is t , after which the next one you pull will match one of the unpaird socks. This scenario is much more likely in the average sock drawer than the worst-case, and reduces the worst-case complexity to O (n*t) where usually t << n .

Real world approach:

As rapidly as possible, remove socks from the unsorted pile one at a time and place in piles in front of you. The piles should be arranged somewhat space-efficiently, with all socks pointing the same direction; the number of piles is limited by the distance you can easily reach. The selection of a pile on which to put a sock should be — as rapidly as possible — by putting a sock on a pile of apparently like socks; the occasional type I (putting a sock on a pile it doesn’t belong to) or type II (putting a sock in its own pile when there’s an existing pile of like socks) error can be tolerated — the most important consideration is speed . Once all the socks are in piles, rapidly go through the multi-sock piles creating pairs and removing them (these are heading for the drawer). If there are non-matching socks in the pile, re-pile them to their best (within the as-fast-as-possible constraint) pile. When all the multi-sock piles have been processed, match up remaining pairable socks that weren’t paird due to type II errors. Whoosh, you’re done — and I have a lot of socks and don’t wash them until a large fraction are dirty. Another practical note: I flip the top of one of a pair of socks down over the other, taking advantage of their elastic properties, so they stay together while being transported to the drawer and while in the drawer.

From your question it is clear you don’t have much actual experience with laundry :). You need an algorithm that works well with a small number of non-pairable socks.

The answers till now don’t make good use of our human pattern recognition capabilities. The game of Set provides a clue of how to do this well: put all socks in a two-dimensional space so you can both recognize them well and easily reach them with your hands. This limits you to an area of about 120 * 80 cm or so. From there select the pairs you recognize and remove them. Put extra socks in the free space and repeat. If you wash for people with easily recognizable socks (small kids come to mind), you can do a radix sort by selecting those socks first. This algorithm works well only when the number of single socks is low

Pick up a first sock and place it on a table. Now pick another sock; if it matches the first picked, place it on top of the first. If not, place it on the table a small distance from the first. Pick a third sock; if it matches either of the previous two, place it on top of them or else place it a small distance from the third. Repeat until you have picked up all the socks.

In order to say how efficient it is to pair socks from a pile, we have to define the machine first, because the pairing isn’t done whether by a turing nor by a random access machine, which are normally used as the basis for an algorithmic analysis.

The machine

The machine is an abstraction of a the real world element called human being. It is able to read from the environment via a pair of eyes. And our machine model is able to manipulate the environment by using 2 arms. Logical and arithmetic operations are calculated using our brain (hopefully ;-)).

We also have to consider the intrinsic runtime of the atomic operations that can be carried out with these instruments. Due to physical constraints, operations which are carried out by an arm or eye have non constant time complexity. This is because we can’t move an endlessly large pile of socks with an arm nor can an eye see the top sock on an endlessly large pile of socks.

However mechanical physics give us some goodies as well. We are not limited to move at most one sock with an arm. We can move a whole couple of them at once.

So depending on the previous analysis following operations should be used in descending order:

  • logical and arithmetic operations
  • environmental reads
  • environmental modifications

We can also make use of the fact that people only have a very limited amount of socks. So an environmental modification can involve all socks in the pile.

El algoritmo

Así que aquí está mi sugerencia:

  1. Spread all socks in the pile over the floor.
  2. Find a pair by looking at the socks on the floor.
  3. Repeat from 2 until no pair can be made.
  4. Repeat from 1 until there are no socks on the floor.

Operation 4 is necessary, because when spreading socks over the floor some socks may hide others. Here is the analysis of the algorithm:

The analysis

The algorithm terminates with high probability. This is due to the fact that one is unable to find pairs of socks in step number 2.

For the following runtime analysis of pairing n pairs of socks, we suppose that at least half of the 2n socks aren’t hidden after step 1. So in the average case we can find n/2 pairs. This means that the loop is step 4 is executed O(log n) times. Step 2 is executed O(n^2) times. So we can conclude:

  • The algorithm involves O(ln n + n) environmental modifications (step 1 O(ln n) plus picking every pair of sock from the floor)
  • The algorithm involves O(n^2) environmental reads from step 2
  • The algorithm involves O(n^2) logical and arithmetic operations for comparing a sock with another in step 2

So we have a total runtime complexity of O(r*n^2 + w*(ln n + n)) where r and w are the factors for environmental read and environmental write operations respectively for a reasonable amount of socks. The cost of the logical and arithmetical operations are omitted, because we suppose that it takes a constant amount of logical and arithmetical operations to decide whether 2 socks belong to the same pair. This may not be feasible in every scenario.

 List UnSearchedSocks = getAllSocks(); List UnMatchedSocks = new list(); List PairdSocks = new list(); 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); PairdSocks.Add(new PairOfSocks(MatchedSock, NewSock)); } else { UnmatchedSocks.Add(NewSock); } } 

I came out with another solution which would not promise fewer operations, neither less time consumption, but it should be tried to see if it can be a good-enough heuristic to provide less time consumption in huge series of sock pairing.

Preconditions: There is no guarantee that there are the same socks. If they are of the same color it doesn’t mean they have the same size or pattern. Socks are randomly shuffled. There can be odd number of socks (some are missing, we don’t know how many). Prepare to remember a variable “index” and set it to 0.

The result will have one or two piles: 1. “matched” and 2. “missing”

Heuristic:

  1. Find most distinctive sock.
  2. Find its match.
  3. If there is no match, put it on the “missing” pile.
  4. Repeat from 1. until there are no more most distinctive socks.
  5. If there are less then 6 socks, go to 11.
  6. Pair blindly all socks to its neighbor (do not pack it)
  7. Find all matched pairs, pack it and move packed pairs to “matched” pile; If there were no new matches – increment “index” by 1
  8. If “index” is greater then 2 (this could be value dependent on sock number because with greater number of socks there are less chance to pair them blindly) go to 11
  9. Shuffle the rest
  10. Go to 1
  11. Forget “index”
  12. Pick a sock
  13. Find its pair
  14. If there is no pair for the sock, move it to the “missing” pile
  15. If match found pair it, pack pair and move it to the “matched” pile
  16. If there are still more then one socks go to 12
  17. If there is just one left go to 14
  18. Smile satisfied 🙂

Also, there could be added check for damaged socks also, as if the removal of those. It could be inserted between 2 and 3, and between 13 and 14.

I’m looking forward to hear about any experiences or corrections.

Socks, whether real ones or some analogous data structure, would be supplied in pairs.

The simplest answer is prior to allowing the pair to be separated, a single data structure for the pair should have been initialized that contained a pointer to the left and right sock, thus enabling socks to be referred to directly or via their pair. A sock may also be extended to contain a pointer to its partner.

This solves any computational pairing problem by removing it with a layer of abstraction.

Applying the same idea to the practical problem of pairing socks, the apparent answer is: don’t allow your socks to ever be unpaird. Socks are provided as a pair, put in the drawer as a pair (perhaps by balling them together), worn as a pair. But the point where unpairing is possible is in the washer, so all that’s required is a physical mechanism that allows the socks to stay together and be washed efficiently.

There are two physical possibilities:

For a ‘pair’ object that keeps a pointer to each sock we could have a cloth bag that we use to keep the socks together. This seems like massive overhead.

But for each sock to keep a reference to the other, there is a neat solution: a popper (or a ‘snap button’ if you’re American), such as these:

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

Then all you do is snap your socks together right after you take them off and put them in your washing basket, and again you’ve removed the problem of needing to pair your socks with a physical abstraction of the ‘pair’ concept.

When I sort socks, I do an approximate radix sort , dropping socks near other socks of the same colour/pattern type. Except in the case when I can see an exact match at/near the location I’m about to drop the sock I extract the pair at that point.

Almost all the other algorithms (including the top scoring answer by usr ) sort, then remove pairs. I find that, as a human, it is better to minimize the number of socks being considered at one time.

I do this by:

  1. Picking a distinctive sock (whatever catches my eye first in the pile).
  2. Starting a radix sort from that conceptual location by pulling socks from the pile based on similarity to that one.
  3. Place the new sock near into the current pile, with a distance based on how different it is. If you find yourself putting the sock on top of another because it is identical, form the pair there, and remove them. This means that future comparisons take less effort to find the correct place.

This takes advantage of the human ability to fuzzy-match in O(1) time, which is somewhat equivalent to the establishment of a hash-map on a computing device.

By pulling the distinctive socks first, you leave space to “zoom” in on the features which are less distinctive, to begin with.

After eliminating the fluro coloured, the socks with stripes, and the three pairs of long socks, you might end up with mostly white socks roughly sorted by how worn they are.

At some point, the differences between socks are small enough that other people won’t notice the difference, and any further matching effort is not needed.

Whenever you pick up a sock, put it in one place. Then the next sock you pick up, if it doesn’t match the first sock, set it beside the first one. If it does, there’s a pair. This way it doesn’t really matter how many combinations there are, and there are only two possibilities for each sock you pick up — either it has a match that’s already in your array of socks, or it doesn’t, which means you add it to a place in the array.

This also means that you will almost certainly never have all your socks in the array, because socks will get removed as they’re matched.

Consider a hash-table of size ‘N’.

If we assume normal distribution, then the estimated number of ‘insertions’ to have atleast one sock mapped to one bucket is NlogN (ie, all buckets are full)

I had derived this as a part of another puzzle,but I would be happy to be proven wrong. Here’s my blog article on the same

Let ‘N’ correspond to an approximate upper-bound on the number of number of unique colors/pattern of socks that you have.

Once you have a collision(aka : a match) simply remove that pair of socks. Repeat the same experiment with the next batch of NlogN socks. The beauty of it is that you could be making NlogN parallel comparisons(collision-resolution) because of the way the human mind works. 🙂

If the “move” operation is fairly expensive, and the “compare” operation is cheap, and you need to move the whole set anyway, into a buffer where search is much faster than in original storage… just integrate sorting into the obligatory move.

I found integrating the process of sorting into hanging to dry makes it a breeze. I need to pick up each sock anyway, and hang it (move) and it costs me about nothing to hang it in a specific place on the strings. Now just not to force search of the whole buffer (the strings) I choose to place socks by color/shade. Darker left, brighter right, more colorful front etc. Now before I hang each sock, I look in its “right vicinity” if a matching one is there already – this limits “scan” to 2-3 other socks – and if it is, I hang the other one right next to it. Then I roll them into pairs while removing from the strings, when dry.

Now this may not seem all that different from “forming piles by color” suggested by top answers but first, by not picking discrete piles but ranges, I have no problem classifying whether “purple” goes to “red” or “blue” pile; it just goes between. And then by integrating two operations (hang to dry and sort) the overhead of sorting while hanging is like 10% of what separate sorting would be.

I hope I can contribute something new to this problem. I noticed that all of the answers neglect the fact that there are two points where you can perform preprocessing , without slowing down your overall laundry performance.

Also, we don’t need to assume a large number of socks, even for large families. Socks are taken out of the drawer and are worn, and they are tossed in a place (maybe a bin) where they stay before being laundered. While I wouldn’t call said bin a LIFO-Stack, I’d say it is safe to assume that

  1. people toss both of their socks roughly in the same area of the bin,
  2. the bin is not randomized at any point, and therefore
  3. any subset took from the top of this bin generally contains both socks of a pair.

Since all washing machines I know about are limited in size (regardless of how many socks you have to wash), and the actual randomizing occurs in the washing machine, no matter how many socks we have, we always have small subsets which contain almost no singletons.

Our two preprocessing stages are “putting the socks on the clothesline” and “Taking the socks from the clothesline”, which we have to do, in order to get socks which are not only clean but also dry. As with washing machines, clotheslines are finite, and I assume that we have the whole part of the line where we put our socks in sight.

Here’s the algorithm for 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 } } 

Don’t waste your time moving socks around or looking for the best match, this all should be done in O(n), which we would also need for just putting them on the line unsorted. The socks aren’t paird yet, we only have several similarity clusters on the line. It’s helpful that we have a limited set of socks here, as this helps us to create “good” clusters (for example, if there are only black socks in the set of socks, clustering by colours would not be the way to go)

Here’s the algorithm for 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 } 

I should point out that in order to improve the speed of the remaining steps, it is wise not to randomly pick the next sock, but to sequentially take sock after sock from each cluster. Both preprocessing steps don’t take more time than just putting the socks on the line or in the basket, which we have to do no matter what, so this should greatly enhance the laundry performance.

After this, it’s easy to do the hash partitioning algorithm. Usually, about 75% of the socks are already paird, leaving me with a very small subset of socks, and this subset is already (somewhat) clustered (I don’t introduce much entropy into my basket after the preprocessing steps). Another thing is that the remaining clusters tend to be small enough to be handled at once, so it is possible to take a whole cluster out of the basket.

Here’s the algorithm for sort_remaining_clusters():

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

After that, there are only a few socks left. This is where I introduce previously unpaird socks into the system and process the remaining socks without any special algorithm – the remaining socks are very few and can be processed visually very fast.

For all remaining socks, I assume that their counterparts are still unwashed and put them away for the next iteration. If you register a growth of unpaird socks over time (a “sock leak”), you should check your bin – it might get randomized (do you have cats which sleep in there?)

I know that these algorithms take a lot of assumptions: a bin which acts as some sort of LIFO stack, a limited, normal washing machine, and a limited, normal clothesline – but this still works with very large numbers of socks.

About parallelism: As long as you toss both socks into the same bin, you can easily parallelize all of those steps.

I have taken simple steps to reduce my effort into a process taking O(1) time.

By reducing my inputs to one of two types of socks (white socks for recreation, black socks for work), I only need to determine which of two socks I have in hand. (Technically, since they are never washed together, I have reduced the process to O(0) time)

Some upfront effort is required to find desirable socks, and to purchase in sufficient quantity as to eliminate need for your existing socks. As I’d done this before my need for black socks, my effort was minimal, but mileage may vary.

Such an upfront effort has been seen many times in very popular and effective code. Examples include #DEFINE’ing pi to several decimals (other examples exist, but that’s the one that comes to mind right now).

Create a hash table which will be used for unmatched socks, using the pattern as the hash. Iterate over the socks one by one. If the sock has a pattern match in the hash table, take the sock out of the table and make a pair. If the sock does not have a match, put it into the table.

The problem of sorting your n pairs of socks is O(n) . Before you throw them in the laundry basket , you thread the left one to the right one. On taking them out, you cut the thread and put each pair into your drawer – 2 operations on n pairs, so O(n).

Now the next question is simply whether you do your own laundry and your wife does hers. That is a problem likely in an entirely different domain of problems . 🙂

I’ve finished pairing my socks just right now, and I found that the best way to do it is the following:

  • Choose one of the socks and put it away (create a ‘bucket’ for that pair)
  • If the next one is the pair of the previous one, then put it to the existing bucket, otherwise create a new one.

In the worst case it means that you will have n/2 different buckets, and you will have n-2 determinations about that which bucket contains the pair of the current sock. Obviously, this algorithm works well if you have just a few pairs; I did it with 12 pairs.

It is not so scientific, but it works well:)

My solution does not exactly correspond to your requirements, as it formally requires O(n) “extra” space. However, considering my conditions it is very efficient in my practical application. Thus I think it should be interesting.

Combine with Other Task

The special condition in my case is that I don’t use drying machine, just hang my cloths on an ordinary cloth dryer. Hanging cloths requires O(n) operations (by the way, I always consider bin packing problem here) and the problem by its nature requires the linear “extra” space. When I take a new sock from the bucket I to try hang it next to its pair if the pair is already hung. If its a sock from a new pair I leave some space next to it.

Oracle Machine is Better 😉

It obviously requires some extra work to check if there is the matching sock already hanging somewhere and it would render solution O(n^2) with coefficient about 1/2 for a computer. But in this case the “human factor” is actually an advantage — I usually can very quickly (almost O(1) ) identify the matching sock if it was already hung (probably some imperceptible in-brain caching is involved) — consider it a kind of limited “oracle” as in Oracle Machine 😉 We, the humans have these advantages over digital machines in some cases 😉

Have it Almost O(n) !

Thus connecting the problem of pairing socks with the problem of hanging cloths I get O(n) “extra space” for free, and have a solution that is about O(n) in time, requires just a little more work than simple hanging cloths and allows to immediately access complete pair of socks even in a very bad Monday morning… 😉