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 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 me parece muy eficiente. La desventaja 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 dos cualquiera de ellos para hacer un par. Tiempo constante.

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

Use radix sort. Esto es solo 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 comparación para comprobar si dos calcetines vienen en pareja. 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ían bien. Podría tomar 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) deseche todos sus calcetines existentes

• Paso 2) ir a Walmart y comprarlos por paquetes de 10-n paquete de blanco y m paquetes de negro. No hay necesidad de otros colores en todos los días vida.

Sin embargo, de vez en cuando, tengo que hacer esto de nuevo (calcetines perdidos, calcetines dañados, etc.), y odio descartar calcetines perfectamente buenos demasiado a menudo (y me gustaría que siguieran vendiendo el misma referencia de calcetines!), así que recientemente tomé un enfoque diferente.

Respuesta algorítmica:

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

• Así que toma cinco de ellos al azar, y memoriza su forma o su longitud.

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

• Coge uno de la pila de 2n-5.

• Ahora busca una coincidencia (coincidencia de patrones visuales-los humanos son buenos en eso con una pila pequeña) dentro de los cinco que dibujaste, si no encuentras uno, entonces agrega eso a tus cinco.

• Sigue escogiendo calcetines al azar de la pila y compáralos con tus calcetines 5+1 para una coincidencia. A medida que su pila crece, reducirá su rendimiento, pero aumentar sus probabilidades. Mucho más rápido.

No dude en escribir la fórmula para calcular cuántas muestras tiene que dibujar para una probabilidad del 50% de un partido. IIRC es una ley hipergeométrica.

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

BTW , encontré que la suma de la los costos de transacción de clasificar todos los calcetines cada vez que necesitaba un par eran mucho menores que hacerlo una vez y atar los calcetines. Un just-in-time funciona mejor porque entonces no tienes que atar los calcetines, y también hay un rendimiento marginal decreciente (es decir, sigues buscando esos dos o tres calcetines que cuando estás en algún lugar de la lavandería y que necesitas terminar de emparejar tus calcetines y pierdes tiempo en eso).

Lo que hago es que cojo el primer calcetín y lo pongo en el suelo (digamos, en el borde del tazón de la colada). Luego cojo otro calcetín y compruebo si es el mismo que el primer calcetín. Si lo es, los quito a ambos. Si no lo es, lo pongo al lado del primer calcetín. Luego cojo el tercer calcetín y lo comparo con los dos primeros (si todavía están allí). Sucesivamente.

Este enfoque se puede implementar con bastante facilidad en una matriz, asumiendo que "quitar" calcetines es una opción. En realidad, ni siquiera necesitas "quitarte" los calcetines. Si no necesitas ordenar los calcetines (ver más abajo), entonces puedes moverlos y terminar con una matriz que tenga todos los calcetines dispuestos en pares en la matriz.

Suponiendo que la única operación para socks es comparar por igualdad, este algoritmo sigue siendo básicamente una n² algoritmo, 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 se puede "insertar" fácilmente un calcetín entre otros dos calcetines. En la 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 por 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 equivocada. La pregunta correcta es, ¿por qué estoy pasando tiempo clasificando calcetines? ¿Cuánto cuesta anualmente, cuando valora su tiempo libre por X unidades monetarias de su elección?

Y la mayoría de las veces, esto no es solo cualquier tiempo libre, es por la mañana tiempo libre, que podría pasar en la cama, o bebiendo su café, o salir un poco temprano y no quedar atrapado en el tráfico.

A menudo es bueno dar un paso atrás, y piensa una manera de solucionar 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 general y durabilidad, comodidad en diferentes condiciones climáticas y absorción de olores. También es importante, no deben perder elasticidad en el almacenamiento, por lo que las telas naturales son buenas, y deben estar disponibles en una envoltura de plástico.

Es mejor si no hay diferencia entre el pie izquierdo y el derecho calcetines, 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 ordenar los calcetines es una operación O(M) aproximada, donde M es el número de lugares en su casa, que ha sembrado con calcetines, idealmente un pequeño número constante.

Si eliges un par elegante con diferentes calcetines a la izquierda y a la derecha, haciendo una clasificación de cubo completo a los cubos de pie izquierdo y derecho 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 el la fórmula para las iteraciones promedio de encontrar el primer par, pero el peor caso para encontrar un par con búsqueda ciega es N / 2 + 1, que se convierte en un caso astronómicamente improbable para razonable N. Esto se puede acelerar mediante el uso de algoritmos avanzados de reconocimiento de imágenes y heurística, al escanear la pila de calcetines sin clasificar con Mk1 Eyeball.

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

1. Es necesario estimar cuántos pares de calcetines que necesitará para el resto de su vida, o tal vez hasta que se retire y se mude a climas más cálidos sin necesidad de usar calcetines nunca más. Si usted es joven, también podría estimar cuánto tiempo tarda 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 ordenar el calcetín seleccionado a granel, cuánto cuesta y si lo entregan.

3. Ordenar el calcetines!

4. 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 pocos pares a la vez a lo largo de los años y agregar el costo de clasificar los calcetines, pero confíe en mi palabra: ¡comprar a granel 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 tome mucho espacio en el estante superior de un armario.

Problema resuelto. Por lo tanto, solo consigue calcetines nuevos, tira/dona los viejos y vive feliz para siempre sabiendo que estás ahorrando dinero y tiempo todos los días por el resto 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 radix sort. Solo tiene que elegir algunos atributos para los cubos.

1. Primero puedes elegir (el suyo, el mío) - divídelos 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 pilas por color (recuerde mantener el orden inicial del paso 1 para todos calcetines en la misma pila),
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 manera única cada par, debe hacerlo en O(k * n), que es O(n) si podemos considerar que k es limitado.

Como solución práctica:

1. Haga rápidamente montones de calcetines fácilmente distinguibles. (Decir por color)
2. Agiliza cada pila y usa la longitud del calcetín para comparar. Como humano, puede tomar una decisión bastante rápida sobre qué calcetín usar para particionar que evite el peor de los casos. (Usted puede ver varios calcetines en paralelo, utilizar que a su ventaja!)
3. Deje de clasificar las pilas cuando alcancen un umbral en el que se sienta cómodo para encontrar pares de puntos y calcetines impairables instantáneamente

Si tienes 1000 calcetines, con 8 colores y una distribución promedio, puedes hacer 4 montones de cada 125 calcetines en tiempo c*n. Con un umbral de 5 calcetines puedes ordenar cada pila en 6 carreras. (Contando 2 segundos para lanzar un calcetín en la pila derecha le tomará poco menos de 4 horas.)

Si solo tienes 60 calcetines, 3 colores y 2 tipos de calcetines (los tuyos / los de tu esposa) puedes ordenar cada pila de 10 calcetines en 1 corridas (Nuevamente umbral = 5). (Contando 2 segundos te llevará 2 min).

La clasificación inicial del cubo acelerará su proceso, ya que divide sus n calcetines en k cubos en c*n tiempo para que solo tenga que hacer c*n*log(k) trabajo. (Sin tener en cuenta el umbral). Así que todo lo que haces sobre n*c*(1 + log(k)) trabajo, donde c es el tiempo para lanzar un calcetín en una pila.

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

En informática esto puede ser útil: Tenemos una colección de n cosas , un orden sobre 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 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 ordenar 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 pilas de color, que dentro de cada partición de pila en textura, que ordenar en longitud. Cualquier relación de equivalencia que crea una partición con más de 2 elementos que tienen aproximadamente un tamaño uniforme traerá una mejora de velocidad sobre la ordenación (siempre que podamos asignar directamente un calcetín a su pila), y la ordenación puede ocurrir muy rápidamente en conjuntos de datos más pequeños.

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 se puede lograr mediante algoritmos.

Un algoritmo obvio para ordenar 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 se trata de los pasos

1. "si s se empareja con un calcetín t en N". ¿Con qué rapidez podemos "recordar" lo que hemos visto hasta ahora?
2. "eliminar t de N" y "añadir s a N". ¿Qué tan caro es hacer un seguimiento de lo que hemos visto hasta ahora?

Los seres humanos utilizarán varias estrategias para efectuar estos. La memoria humana es asociativa, algo así como una tabla hash donde los conjuntos de características de 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 la mayoría de los demás). El mapa asociativo tiene una capacidad limitada. Las asignaciones pueden bleep fuera de la existencia en virtud de diversas circunstancias (una cerveza demasiados), se registrarán en el error ("yo, sin embargo, su nombre era Betty, no Nettie"), o nunca se pierde aunque se observa que la verdad ha cambiado ("el coche de papá" evoca "naranja pájaro de fuego", cuando en realidad sabía que él había negociado que en el Camaro rojo).

En el caso de los calcetines, el recuerdo perfecto significa que mirar un calcetín s siempre produce la memoria de su hermano t, incluyendo suficiente información (donde está en la tabla de planchar) para localizar t en tiempo constante. Una persona con memoria fotográfica logra 1 y 2 en tiempo constante sin falta.

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

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

Un fenómeno del orden podría usar etiquetas numéricas para los pares como alguien sugirió. Esto abre la puerta a un orden total, que permite al humano utilice exactamente los mismos algoritmos que podríamos usar con una CPU: búsqueda binaria, árboles, hashes, etc.

Así que el algoritmo "mejor" depende de las cualidades del wetware/hardware/software que lo está ejecutando y nuestra voluntad de "engañar" imponiendo un orden total en pares. Ciertamente, un "mejor" meta -algoritmo es contratar al mejor clasificador de calcetines del mundo: una persona o máquina que puede adquirir y almacenar rápidamente un enorme conjunto N de conjuntos de atributos de calcetines en una memoria asociativa 1-1 con búsqueda de tiempo constante, insertar y eliminar. Tanto las personas como las máquinas como esta pueden ser adquiridas. Si tiene uno, puede emparejar todos los calcetines en O (N) tiempo para N pares, lo cual es óptimo. Las etiquetas de orden total le permiten usar hashing estándar para obtener el mismo resultado con una computadora humana o de hardware.

Estás tratando de resolver el problema equivocado.

Solución 1: Cada vez que ponga calcetines sucios en su cesta de la ropa, átelos en un pequeño nudo. De esa manera no tendrá 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 saberlo, siempre y cuando obrar.

Solución 3: Difundir 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 mételos 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!

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

Supongamos que usted sabe que sus 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,...,y}. Saber esto no puede hacer que el problema sea más difícil. Hay n! posibles salidas (coincidencias entre primera y segunda mitad), lo que significa que necesita registro (n!) = Comparaciones Omega(n log n). Esto se puede obtener clasificando.

Dado que está interesado en las conexiones a la distinción de elementos problema: probar el Omega(n log n) enlazado 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 enlace decente. Sin embargo, hay una variante conectada a la distinción de elementos. Supongamos que se le dan calcetines 2n y me pregunto si pueden ser emparejados de forma única. Puede obtener una reducción de ED enviando (a₁, a₂, ..., un_n) a un₁, un₁, un₂, un₂, ..., un_n, a_n). (Entre paréntesis, la prueba de dureza de ED es muy interesante, a través de la topología .)

Creo que debería haber un Omega (n²) límite para el problema original si permite pruebas de igualdad solamente. Mi intuición es: Considere un gráfico donde se agrega un arista después de una prueba, y argumentan que si el gráfico no es denso, la salida no está determinada de forma única.

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

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 multithreded del Homo Sapiens para mantener más cosas en la caché de decision.

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.

Do hasta que A esté vacío.

Para cada línea X e Y

1. Elige el primer calcetín en la línea, busca a lo largo de la línea hasta que encuentre el calcetín correspondiente.

2. Pongan en la línea correspondiente acabada de los calcetines.

3. Opcional Mientras estás buscando la línea y el calcetín actual que estás mirando es idéntico al anterior, haz el paso 2 para estos calcetines.

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

Hazlo hasta que X e Y estén vacíos.

Hecho

Sin embargo, como esto tiene complejidad similar como clasificación de selección, el tiempo requerido es mucho menor debido a las velocidades de E / S (calcetines móviles) y buscar (buscando un calcetín en la línea).

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

• Toma un calcetín al azar de la pila.
• Para el primer calcetín, o si todos los calcetines previamente elegidos han sido emparejados, simplemente coloque el calcetín en la primera "ranura" de una "matriz" de calcetines no emparejados frente a usted.
• Si tiene uno o más calcetines no emparejados seleccionados, verifique su calcetín actual con todos los calcetines no emparejados en la matriz.
  • es posible separe los calcetines en clases o tipos generales (blanco/negro, tobillo/tripulación, atlético/vestido) al construir su matriz, y "profundice" para comparar solo como por como.
  • Si encuentra una coincidencia aceptable, junte ambos calcetines y elimínelos de la matriz.
  • Si no lo hace, ponga el calcetín actual en la primera ranura abierta en la matriz.
• Repetir con cada calcetín.

El peor escenario de este esquema es que cada par de calcetines es lo suficientemente diferente que debe coincidir exactamente, y que los primeros n/2 calcetines que elijas son todos diferentes. Este es su O (n²) escenario, y es extremadamente poco probable. Si el número de tipos únicos de calcetines 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) para que cualquier calcetín de ese tipo pueda emparejarse con cualquier otro, entonces, como deduje anteriormente, el número máximo de calcetines que para comparar es t , después de lo cual el siguiente que tire coincidirá con uno de los calcetines no emparejados. Este escenario es mucho más probable en el cajón de calcetines promedio que en el peor de los casos, y reduce la complejidad del peor de los casos a O(n*t) donde generalmente t .

Enfoque del mundo real:

Tan rápido como sea posible, retire los calcetines de la pila sin clasificar uno a la vez y colóquelos en pilas frente a usted. Las pilas deben estar dispuestas de manera eficiente en el 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 en la que poner un calcetín debe ser rapidly lo más rápido posible by poniendo un calcetín en una pila de calcetines aparentemente similares; el tipo ocasional I (poner un calcetín en una pila a la que no pertenece) o tipo II (poner un calcetín en su propia pila cuando hay una pila existente de calcetines similares) se puede tolerar el error the la consideración más importante es velocidad. Una vez que todos los calcetines están en pilas, vaya rápidamente a través de las pilas de múltiples calcetines creando pares y eliminándolos (estos se dirigen al cajón). Si hay calcetines que no coinciden en la pila, vuelva a apilarlos en su mejor pila (dentro de la restricción lo más rápido posible). Cuando todas las pilas de calcetines múltiples tienen se han procesado, emparejar los calcetines restantes pairable que no se emparejaron debido a errores de tipo II. Whoosh, has terminado have y tengo un montón de calcetines y no los lavo hasta que una gran fracción está sucia. Otra nota práctica: Volteo la parte superior de uno de un par de calcetines hacia abajo 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.

De su pregunta está claro que no tiene mucha experiencia real con la lavandería :). Necesitas un algoritmo que funcione bien con un pequeño número de calcetines no pairables.

Las respuestas hasta ahora no hacen buen uso de nuestras capacidades de reconocimiento de patrones humanos. El juego de Set proporciona una pista de cómo hacer esto bien: coloque todos los calcetines en un espacio bidimensional para que ambos puedan reconocerlos bien y alcanzarlos fácilmente con las manos. Esto lo limita a un área de aproximadamente 120 * 80 cm o tan. A partir de ahí, seleccione los pares que reconoce y eliminarlos. Ponga calcetines adicionales en el espacio libre y repita. Si lavas para personas con calcetines fácilmente reconocibles (los niños pequeños vienen a la mente), puedes hacer una clasificación radix seleccionando esos calcetines primero. Este algoritmo funciona bien solo cuando el número de calcetines individuales es bajo

Toma un primer calcetín y colócalo sobre una mesa. Ahora elige otro calcetín; si coincide con el primero elegido, colócalo encima del primero. Si no, colóquelo sobre la mesa a una pequeña distancia de la primera. Elige un tercer calcetín; si coincide con cualquiera de los dos anteriores, colócalo encima de ellos o bien colócalo a una pequeña distancia del tercero. Repite hasta que hayas recogido todos los calcetines.

Para decir lo eficiente que es emparejar calcetines de una pila, primero tenemos que definir la máquina, porque el emparejamiento no se realiza ni por un turing ni por una máquina de acceso aleatorio, que normalmente se utilizan como base para un 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 medio ambiente por usando 2 brazos. Las operaciones lógicas y aritméticas se calculan utilizando nuestro cerebro (con suerte; -)).

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

Sin embargo la física mecánica nos da algunas golosinas también. 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, dependiendo del análisis anterior, se deben usar las siguientes operaciones en orden descendente:

• operaciones lógicas y aritméticas
• ambiental lee
• modificaciones ambientales

También podemos hacer uso del hecho de que la gente solo tiene una muy cantidad limitada de calcetines. Por lo tanto, una modificación ambiental puede involucrar a todos los calcetines en la pila.

El algoritmo

Así que aquí está mi sugerencia:

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

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

El análisis

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 de emparejamiento n pares de calcetines, suponemos que al menos la mitad de los 2n calcetines no están ocultos después del paso 1. Así que en el caso promedio podemos encontrar pares n/2. Esto significa que el bucle es el paso 4 se ejecuta O(log n) veces. El paso 2 se ejecuta O(n^2) veces. Así que podemos concluir:

• El algoritmo implica O(ln n + n) modificaciones ambientales (paso 1 O(ln n) además de recoger cada par de calcetines del piso)
• El algoritmo implica O(n^2) lecturas ambientales del paso 2
• El algoritmo implica 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)) donde r y w son los factores para las operaciones ambientales de lectura y escritura, respectivamente, para una cantidad razonable de calcetines. Se omite el costo de las operaciones lógicas y aritméticas, 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.

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);
  }
}

Salí con otra solución que no prometía menos operaciones, ni menos consumo de tiempo, pero se debe intentar ver si puede ser una heurística lo suficientemente buena como para proporcionar menos consumo de tiempo en grandes series de emparejamiento 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 al azar. Puede haber un número impar de calcetines (algunos faltan, no sabemos cuántos). Prepárese para recordar una variable "index" y póngala en 0.

El resultado tendrá uno o dos montones: 1. "emparejado" y 2. "desaparecido"

Heurística:

1. Encuentra el calcetín más distintivo.
2. Encuentra su coincidencia.
3. Si no hay coincidencia, póngala en la pila "faltante".
4. Repetir desde 1. hasta que no haya más calcetines más distintivos.
5. Si hay menos de 6 calcetines, vaya a 11.
6. Par ciegamente todos los calcetines a su vecino (no empacar)
7. Encuentra todos los pares emparejados, empaca y mueve los pares empaquetados a la pila "emparejada" ; Si no hubo nuevas coincidencias-incrementar el "índice" en 1
8. Si "índice" es mayor que 2 (esto podría ser un valor dependiente del calcetín número porque con mayor número de calcetines hay menos posibilidades de emparejarlos ciegamente) ir a 11
9. Barajar el resto
10. Ir a 1
11. Olvida"índice"
12. Elige a sock
13. Encuentra su par
14. Si no hay pareja para el calcetín, muévalo a la pila "faltante"
15. Si se ha encontrado un emparejamiento, empaca el emparejamiento y muévelo a la pila "emparejada"
16. Si todavía hay más entonces uno calcetines ir a 12
17. Si solo queda uno ir a 14
18. Sonrisa satisfecha:)

También, podría añadirse la comprobación de calcetines dañados también, como si la eliminación de los mismos. Podría insertarse entre 2 y 3, y entre 13 y 14.

Estoy deseando escuchar cualquier experiencia o corrección.

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

La respuesta más simple es antes de permitir que el par se separe, una sola estructura de datos para el par debería haber sido inicializada que contuviera un puntero al calcetín izquierdo y derecho, permitiendo así que los calcetines sean referidos directamente o a través de su par. Un calcetín también se puede extender para contener un puntero a su pareja.

Esto resuelve cualquier problema de emparejamiento computacional eliminándolo con una capa de abstracción.

Aplicando la misma idea al problema práctico de emparejar calcetines, la respuesta aparente es: no permita que sus calcetines nunca estén despareados. Los calcetines se proporcionan como un par, se ponen en el cajón como un par (tal vez al juntarlos), se usan como un par. Pero el punto donde es posible desenchufar 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 de manera eficiente.

Hay dos físicos posibilidades:

Para un objeto 'pair' 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 que cada calcetín mantenga una referencia al otro, hay una solución ordenada: un popper (o un 'botón de presión' si eres estadounidense), como estos:

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

Entonces todo lo que haces es juntar tus calcetines justo después de ti quítatelos y colócalos en tu cesta de lavado, y de nuevo has eliminado el problema de tener que emparejar tus calcetines con una abstracción física del concepto de "par".

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

Casi todos los otros algoritmos (incluyendo la respuesta de mayor puntuación de usr) ordenan, luego eliminan pares. Me parece que, como humano, es mejor minimizar el número de calcetines que se consideran a la vez.

I haga esto por:

1. Elegir un calcetín distintivo (lo que me llame la atención primero en la pila).
2. Comenzando una clasificación radix desde esa ubicación conceptual tirando calcetines de la pila en función de la similitud con esa.
3. Coloque el nuevo calcetín cerca de la pila actual, con una distancia basada en lo diferente que es. Si te encuentras poniendo el calcetín encima de otro porque es idéntico, forma el par allí y quítalos. Esto significa que las comparaciones futuras toman menos esfuerzo para encontrar el lugar correcto.

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

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

Después de eliminar el color fluro, los calcetines con rayas y los tres pares de calcetines largos, puede terminar con mayormente blanco calcetines más o menos ordenados por lo desgastados que están.

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 se necesita ningún esfuerzo adicional para emparejar.

Cada vez que cojas un calcetín, colócalo en un solo lugar. Luego, el siguiente calcetín que recojas, si no coincide con el primer calcetín, colócalo 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 recojas has o tiene una coincidencia que ya está en tu matriz de calcetines, o no, lo que significa que lo agregas a un lugar en la matriz.

Esto también significa que casi ciertamente, nunca tenga todos sus calcetines en la matriz, porque los calcetines se eliminarán a medida que se emparejen.

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

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

Yo había derivado esto como parte de otro rompecabezas,pero estaría feliz de ser probado equivocado. Aquí está mi artículo de blog sobre el mismo

Vamos ' N ' corresponden a un límite superior aproximado en el número de número de colores únicos / patrón de calcetines que usted tener.

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

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

Encontré que integrar el proceso de clasificación en colgar para secar hace que sea muy fácil. Tengo que recoger cada calcetín de todos modos, y colgarlo (mover) y me cuesta casi nada colgarlo en un lugar específico en las cuerdas. Ahora solo para no forzar búsqueda de todo el búfer (las cuerdas) Elijo colocar los calcetines por color/sombra. Izquierda más oscura, derecha más brillante, frente más colorido, etc. Ahora, antes de colgar cada calcetín, miro en su " vecindad derecha "si ya hay uno que coincida - esto limita el" escaneo " a 2-3 otros calcetines - y si lo es, cuelgo el otro justo al lado de él. Luego los enrollo en pares mientras los quito de las cuerdas, cuando están secos.

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

Espero poder aportar algo nuevo a este problema. Me di cuenta de que todas las respuestas descuidan el hecho de que hay dos puntos donde se puede realizar preprocesamiento, sin ralentizar su rendimiento general de lavandería.

Además, no necesitamos asumir un gran número 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. Mientras yo no llamaría a said bin a LIFO-Stack, yo diría que es seguro asumir que

1. las personas tiran ambos calcetines aproximadamente en la misma área de la bin,
2. el bin no es aleatorio en ningún punto, y por lo tanto
3. cualquier subconjunto tomado de la parte superior de este bin generalmente contiene ambos calcetines de un par.

Dado que todas las lavadoras que conozco son limitadas en tamaño (independientemente de cuántos calcetines tenga que lavar), y la aleatorización real se produce en la lavadora, no importa cuántos calcetines que tenemos, 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", 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 supongo que tenemos toda la parte de la línea donde ponemos nuestros 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 pierdas el tiempo moviendo 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 grupos "buenos" (por ejemplo, si solo hay calcetines negros en el conjunto de calcetines, agruparse por colores no sería el camino a seguir)

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 simplemente poner los calcetines en la línea o en la cesta, lo que tenemos que hacer sin importar qué, por lo que esto debería mejorar en gran medida el rendimiento de la lavandería.

Después de esto, es fácil de 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 como para ser manejados a la vez, por lo que es posible tomar un grupo completo de la cesta.

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, solo quedan unos pocos calcetines. Aquí es donde introduzco calcetines previamente no emparejados 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 todavía están sin lavar y los guardo para la próxima iteración. Si registra un crecimiento de calcetines no emparejados con el tiempo (una " fuga de calcetines"), usted debe comprobar su compartimiento - puede ser que consiga al azar (usted 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 y cuando tires ambos calcetines en el mismo contenedor, puedes paralelizar fácilmente todos esos pasos.

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

Al reducir mis entradas a uno de los dos tipos de calcetines (calcetines blancos para recreación, calcetines negros para 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 para comprar en cantidad suficiente como para eliminar la necesidad de su existente calcetín. Como había hecho esto antes de mi necesidad de calcetines negros, mi esfuerzo era mínimo, pero el kilometraje puede variar.

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

Cree una tabla hash que se utilizará para calcetines sin igual, utilizando el patrón como hash. Itera 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 tabla y haga un par. Si el calcetín no tiene partido, póngalo en la mesa.

El problema de ordenar sus n pares de calcetines es O(n). Antes de tirarlos en la cesta de la colada , enhebra la izquierda a la derecha. Al sacarlos, corta el hilo y coloca cada par en tu cajón-2 operaciones en n pares, por lo que O(n).

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

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

• Elige uno de los calcetines y guárdalo (crea un 'cubo' para ese par)
• Si el siguiente es el par del anterior, entonces póngalo en el cubo 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 sobre qué cubo contiene el par de los calcetín actual. Obviamente, este algoritmo funciona bien si tienes solo unos pocos pares; lo hice con 12 pares.

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

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

Combinar con Otra Tarea

La condición especial en mi caso es que no uso secadora, solo cuelgue mis paños en una secadora de tela ordinaria. Los paños colgantes requieren O(n) operaciones (por cierto, siempre considero embalaje de contenedores problema aquí) y el problema por su naturaleza requiere el espacio lineal "extra". Cuando cojo un calcetín nuevo del cubo intento colgarlo junto a su par si el par ya está colgado. Si es un calcetín de un par nuevo dejo un poco de espacio al lado.

La máquina Oracle es mejor; -)

Obviamente requiere un poco de trabajo extra para comprobar si hay el calcetín correspondiente ya colgando en algún lugar y se renderizaría solución O(n^2) con coeficiente alrededor de 1/2 para un ordenador. Pero en este caso el" factor humano " es en realidad una ventaja usually Normalmente puedo muy rápidamente (casi O(1)) identificar el calcetín correspondiente si ya estaba colgado (probablemente algún almacenamiento en caché imperceptible en el cerebro está involucrado) consider considéralo una especie de "oráculo" limitado como en Oracle Machine ; -) Nosotros, los humanos tenemos estas ventajas sobre las máquinas digitales en algunos casos; -)

Tenlo casi O(n)!

Conectando así el problema de emparejar calcetines con el problema de colgar paños consigo O(n) " extra espacio " de forma gratuita, y tener una solución que se acerca O(n) en el tiempo, requiere solo un poco más de trabajo que simples paños colgantes y permite acceder inmediatamente a un par completo de calcetines, incluso en una muy mala mañana de lunes... ;-)