Hier, je jumelais les chaussettes du linge propre et j'ai compris que ma façon de faire n'était pas très efficace. Je faisais une recherche naïve - en choisissant une chaussette et en "itérant" la pile afin de trouver sa paire. Cela nécessite itérer n / 2 * n / 4 = n ² /8 chaussettes en moyenne.

En tant qu'informaticien, je pensais à ce que je pouvais faire? Le tri (en fonction de la taille / couleur / ...) est bien entendu venu à l'esprit pour aboutir à une solution O (NlogN).

Le hachage ou d'autres solutions non en place ne sont pas une option, car je ne suis pas en mesure de dupliquer mes chaussettes (même si cela pourrait être bien si je le pouvais).

Donc, la question est essentiellement:

Étant donné un tas de npaires de chaussettes contenant des 2néléments (supposons que chaque chaussette a exactement une paire assortie), quelle est la meilleure façon de les associer efficacement avec un espace supplémentaire jusqu'à logarithmique? (Je crois que je peux me souvenir de cette quantité d'informations si nécessaire.)

J'apprécierai une réponse qui aborde les aspects suivants:

• Une solution théorique générale pour un grand nombre de chaussettes.
• Le nombre réel de chaussettes n'est pas si grand, je ne crois pas que mon conjoint et moi en ayons plus de 30 paires. (Et il est assez facile de faire la distinction entre mes chaussettes et les siennes; cela peut-il également être utilisé?)
• Est-il équivalent au problème de la distinction des éléments ?

Des solutions de tri ont été proposées, mais le tri est un peu trop : nous n'avons pas besoin de commande; nous avons juste besoin de groupes pour l'égalité .

Le hachage serait donc suffisant (et plus rapide).

1. Pour chaque couleur de chaussettes, formez un tas . Parcourez toutes les chaussettes de votre panier d'entrée et répartissez-les sur les piles de couleur .
2. Itérer sur chaque pile et la distribuer par une autre métrique (par exemple un motif) dans le deuxième ensemble de piles
3. Appliquer récursivement ce schéma jusqu'à ce que vous ayez réparti toutes les chaussettes sur de très petites piles que vous pouvez traiter visuellement immédiatement

Ce type de partitionnement de hachage récursif est en fait effectué par SQL Server lorsqu'il a besoin de joindre ou de regrouper des hachages sur d'énormes ensembles de données. Il distribue son flux d'entrée de génération dans de nombreuses partitions indépendantes. Ce schéma s'adapte à des quantités arbitraires de données et à plusieurs processeurs linéairement.

Vous n'avez pas besoin de partitionnement récursif si vous pouvez trouver une clé de distribution (clé de hachage) qui fournit suffisamment de compartiments pour que chaque compartiment soit suffisamment petit pour être traité très rapidement. Malheureusement, je ne pense pas que les chaussettes aient une telle propriété.

Si chaque chaussette avait un entier appelé "PairID", on pourrait facilement les répartir en 10 seaux selon PairID % 10(le dernier chiffre).

La meilleure partition du monde réel à laquelle je peux penser est de créer un rectangle de piles : une dimension est la couleur, l'autre est le motif. Pourquoi un rectangle? Parce que nous avons besoin d'un accès aléatoire O (1) aux piles. (Un cuboïde 3D fonctionnerait également, mais ce n'est pas très pratique.)

Mise à jour:

Et le parallélisme ? Plusieurs humains peuvent-ils assortir les chaussettes plus rapidement?

1. La stratégie de parallélisation la plus simple consiste à demander à plusieurs travailleurs de prendre le panier d'entrée et de mettre les chaussettes sur les piles. Cela ne fait que grandir - imaginez 100 personnes se battant sur 10 piles. Les coûts de synchronisation (se manifestant par des collisions avec les mains et la communication humaine) détruisent l'efficacité et l'accélération (voir la loi universelle sur l'évolutivité !). Est-ce sujet à des blocages ? Non, car chaque travailleur n'a besoin d'accéder qu'à une seule pile à la fois. Avec un seul "verrou", il ne peut pas y avoir d'impasse. Les livelocks pourraient être possibles selon la façon dont les humains coordonnent l'accès aux piles. Ils pourraient simplement utiliser une interruption aléatoirecomme les cartes réseau, faites cela au niveau physique pour déterminer quelle carte peut accéder exclusivement au câble réseau. Si cela fonctionne pour les cartes réseau , il devrait également fonctionner pour les humains.
2. Il évolue presque indéfiniment si chaque travailleur a son propre jeu de piles . Les travailleurs peuvent ensuite prendre de gros morceaux de chaussettes dans le panier d'entrée (très peu de conflits car ils le font rarement) et ils n'ont pas du tout besoin de se synchroniser lors de la distribution des chaussettes (car ils ont des piles locales). À la fin, tous les travailleurs doivent syndiquer leurs ensembles de pieux. Je crois que cela peut être fait en O (log (nombre de travailleurs * piles par travailleur)) si les travailleurs forment un arbre d'agrégation .

Qu'en est-il du problème de distinction des éléments ? Comme l'indique l'article, le problème de la distinction des éléments peut être résolu O(N). C'est la même chose pour le problème des chaussettes (aussi O(N), si vous n'avez besoin que d'une seule étape de distribution (j'ai proposé plusieurs étapes uniquement parce que les humains sont mauvais dans les calculs - une étape suffit si vous distribuez md5(color, length, pattern, ...), c'est-à-dire un hachage parfait de tous les attributs)).

De toute évidence, on ne peut pas aller plus vite que O(N), donc nous avons atteint la limite inférieure optimale .

Bien que les sorties ne soient pas exactement les mêmes (dans un cas, juste un booléen. Dans l'autre cas, les paires de chaussettes), les complexités asymptotiques sont les mêmes.

L'architecture du cerveau humain étant complètement différente d'un processeur moderne, cette question n'a aucun sens pratique.

Les humains peuvent gagner les algorithmes CPU en utilisant le fait que "trouver une paire correspondante" peut être une opération pour un ensemble qui n'est pas trop grand.

Mon algorithme:

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

C'est du moins ce que j'utilise dans la vraie vie, et je le trouve très efficace. L'inconvénient est qu'il nécessite une surface plane, mais il est généralement abondant.

Cas 1 : Toutes les chaussettes sont identiques (c'est ce que je fais dans la vraie vie d'ailleurs).

Choisissez-en deux pour en faire une paire. Temps constant.

Cas 2 : Il existe un nombre constant de combinaisons (propriété, couleur, taille, texture, etc.).

Utilisez le tri radix . Il s'agit uniquement d'un temps linéaire car aucune comparaison n'est requise.

Cas 3 : Le nombre de combinaisons n'est pas connu à l'avance (cas général).

Nous devons faire une comparaison pour vérifier si deux chaussettes viennent par paire. Choisissez l'un des O(n log n)algorithmes de tri basés sur la comparaison.

Cependant, dans la vraie vie, lorsque le nombre de chaussettes est relativement petit (constant), ces algorithmes théoriquement optimaux ne fonctionneraient pas bien. Cela pourrait prendre encore plus de temps que la recherche séquentielle, qui nécessite théoriquement un temps quadratique.

Réponse non algorithmique, mais "efficace" quand je le fais:

• étape 1) jetez toutes vos chaussettes existantes

• étape 2) allez chez Walmart et achetez-les par paquets de 10 - n paquets de blanc et m paquets de noir. Pas besoin d'autres couleurs dans la vie de tous les jours.

Pourtant, de temps en temps, je dois recommencer (chaussettes perdues, chaussettes endommagées, etc.), et je déteste jeter trop souvent de bonnes chaussettes (et j'aurais souhaité qu'ils continuent à vendre la même référence de chaussettes!), Alors j'ai récemment pris une approche différente.

Réponse algorithmique:

Considérez que si vous ne dessinez qu'une seule chaussette pour la deuxième pile de chaussettes, comme vous le faites, vos chances de trouver la chaussette correspondante dans une recherche naïve sont assez faibles.

• Alors, prenez-en cinq au hasard et mémorisez leur forme ou leur longueur.

Pourquoi cinq? Habituellement, les humains sont bons se souviennent de cinq à sept éléments différents dans la mémoire de travail - un peu comme l'équivalent humain d'une pile RPN - cinq est un défaut sûr.

• Prenez-en un dans la pile de 2n-5.

• Recherchez maintenant une correspondance (correspondance des motifs visuels - les humains sont bons avec une petite pile) à l'intérieur des cinq que vous avez dessinés, si vous n'en trouvez pas, puis ajoutez-la à vos cinq.

• Continuez à choisir des chaussettes au hasard dans la pile et comparez-les à vos chaussettes 5 + 1 pour un match. À mesure que votre pile augmente, cela réduira vos performances mais augmentera vos chances. Plus vite.

N'hésitez pas à noter la formule pour calculer le nombre d'échantillons à prélever pour une chance de correspondance de 50%. IIRC c'est une loi hypergéométrique.

Je fais cela tous les matins et j'ai rarement besoin de plus de trois tirages - mais j'ai ndes paires similaires (environ 10, donnez ou prenez les perdues) de mchaussettes blanches en forme. Vous pouvez maintenant estimer la taille de ma pile de stocks :-)

BTW , j'ai trouvé que la somme des coûts de transaction du tri de toutes les chaussettes à chaque fois que j'avais besoin d'une paire était beaucoup moins que de le faire une fois et de lier les chaussettes. Un juste à temps fonctionne mieux parce que vous n'avez pas à lier les chaussettes, et il y a aussi un retour marginal décroissant (c'est-à-dire que vous continuez à chercher ces deux ou trois chaussettes qui se trouvent quelque part dans le linge et dont vous avez besoin pour finir de faire correspondre vos chaussettes et vous perdez du temps là-dessus).

Ce que je fais, c'est que je prends la première chaussette et que je la pose (disons, sur le bord du bol à linge). Ensuite, je prends une autre chaussette et vérifie si c'est la même chose que la première chaussette. Si c'est le cas, je les supprime tous les deux. Si ce n'est pas le cas, je la pose à côté de la première chaussette. Ensuite, je prends la troisième chaussette et la compare aux deux premières (si elles sont toujours là). Etc.

Cette approche peut être assez facilement implémentée dans un tableau, en supposant que "retirer" les chaussettes est une option. En fait, vous n'avez même pas besoin de "retirer" les chaussettes. Si vous n'avez pas besoin de trier les chaussettes (voir ci-dessous), vous pouvez simplement les déplacer et vous retrouver avec un tableau qui a toutes les chaussettes disposées par paires dans le tableau.

En supposant que la seule opération pour les chaussettes est de comparer pour l'égalité, cet algorithme est fondamentalement toujours un algorithme n ² , bien que je ne connaisse pas le cas moyen (jamais appris à calculer cela).

Le tri améliore bien sûr l'efficacité, en particulier dans la vie réelle où vous pouvez facilement "insérer" une chaussette entre deux autres chaussettes. En informatique, la même chose pourrait être obtenue par un arbre, mais c'est un espace supplémentaire. Et, bien sûr, nous sommes de retour à NlogN (ou un peu plus, s'il y a plusieurs chaussettes qui sont les mêmes en fonction des critères de tri, mais pas de la même paire).

En dehors de cela, je ne peux penser à rien, mais cette méthode semble être assez efficace dans la vie réelle. :)

Cela pose la mauvaise question. La bonne question à poser est la suivante: pourquoi passe-je du temps à trier les chaussettes? Combien cela coûte-t-il chaque année, lorsque vous appréciez votre temps libre pour X unités monétaires de votre choix?

Et plus souvent qu'autrement, ce n'est pas seulement tout temps libre, il est matin temps libre, que vous pourriez dépenser au lit, ou en sirotant votre café, ou en laissant un peu plus tôt et ne pas être pris dans le trafic.

Il est souvent bon de prendre du recul et de réfléchir à un moyen de contourner le problème.

Et il y a un moyen!

Trouvez une chaussette que vous aimez. Tenez compte de toutes les caractéristiques pertinentes: couleur dans différentes conditions d'éclairage, qualité globale et durabilité, confort dans différentes conditions climatiques et absorption des odeurs. Il est également important qu'ils ne perdent pas leur élasticité au stockage, les tissus naturels sont donc bons et doivent être disponibles dans un emballage plastique.

C'est mieux s'il n'y a pas de différence entre les chaussettes du pied gauche et du pied droit, mais ce n'est pas critique. Si les chaussettes sont symétriques gauche-droite, trouver une paire est une opération O (1), et trier les chaussettes est une opération approximative O (M), où M est le nombre de places dans votre maison, que vous avez jonchées de chaussettes, idéalement certaines petit nombre constant.

Si vous avez choisi une paire fantaisie avec des chaussettes gauche et droite différentes, faire un tri complet du seau vers les seaux du pied gauche et droit prend O (N + M), où N est le nombre de chaussettes et M est le même que ci-dessus. Quelqu'un d'autre peut donner la formule des itérations moyennes pour trouver la première paire, mais le pire des cas pour trouver une paire avec recherche aveugle est N / 2 + 1, ce qui devient un cas astronomiquement improbable pour un N raisonnable. Cela peut être accéléré en utilisant une image avancée algorithmes de reconnaissance et heuristique, lors de la numérisation de la pile de chaussettes non triées avec Mk1 Eyeball .

Ainsi, un algorithme pour atteindre l'efficacité d'appariement des chaussettes O (1) (en supposant une chaussette symétrique) est:

1. Vous devez estimer le nombre de paires de chaussettes dont vous aurez besoin pour le reste de votre vie, ou peut-être jusqu'à ce que vous preniez votre retraite et que vous vous dirigiez vers des climats plus chauds sans avoir à porter de chaussettes. Si vous êtes jeune, vous pouvez également estimer le temps qu'il faudra avant que nous ayons tous des robots de tri des chaussettes dans nos maisons, et tout le problème devient sans importance.

2. Vous devez savoir comment vous pouvez commander votre chaussette sélectionnée en vrac, combien cela coûte et livrent-ils.

3. Commandez les chaussettes!

4. Débarrassez-vous de vos vieilles chaussettes.

Une autre étape 3 consisterait à comparer les coûts d'achat de la même quantité de chaussettes peut-être moins chères quelques paires à la fois au fil des ans et à ajouter le coût du tri des chaussettes, mais croyez-moi sur parole: acheter en vrac est moins cher! De plus, les chaussettes dans le stockage augmentent en valeur au rythme de l'inflation du cours des actions, ce qui est plus que ce que vous obtiendriez sur de nombreux investissements. Là encore, il y a aussi des frais de stockage, mais les chaussettes ne prennent vraiment pas beaucoup de place sur l'étagère supérieure d'un placard.

Problème résolu. Alors, procurez-vous de nouvelles chaussettes, jetez / donnez vos anciennes et vivez heureux pour toujours en sachant que vous économisez de l'argent et du temps chaque jour pour le reste de votre vie.

La limite théorique est O (n) car vous devez toucher chaque chaussette (sauf si certaines sont déjà appariées d'une manière ou d'une autre).

Vous pouvez obtenir O (n) avec le tri radix . Il vous suffit de choisir des attributs pour les compartiments.

1. Vous pouvez d'abord choisir (le sien, le mien) - les diviser en 2 piles,
2. puis utilisez des couleurs (peut avoir n'importe quel ordre pour les couleurs, par exemple par ordre alphabétique par nom de couleur) - divisez-les en piles par couleur (n'oubliez pas de conserver l'ordre initial de l'étape 1 pour toutes les chaussettes dans la même pile),
3. puis la longueur de la chaussette,
4. puis texture, ....

Si vous pouvez choisir un nombre limité d'attributs, mais suffisamment d'attributs qui peuvent identifier de manière unique chaque paire, vous devez le faire dans O (k * n), qui est O (n) si nous pouvons considérer que k est limité.

Comme solution pratique:

1. Faites rapidement des tas de chaussettes facilement reconnaissables. (Dites par couleur)
2. Triez rapidement chaque pile et utilisez la longueur de la chaussette pour comparer. En tant qu'humain, vous pouvez prendre une décision assez rapide quelle chaussette utiliser pour partitionner ce qui évite le pire des cas. (Vous pouvez voir plusieurs chaussettes en parallèle, utilisez-les à votre avantage!)
3. Arrêtez de trier les piles lorsqu'elles ont atteint un seuil auquel vous êtes à l'aise pour trouver instantanément des paires de points et des chaussettes impairables

Si vous avez 1000 chaussettes, avec 8 couleurs et une distribution moyenne, vous pouvez faire 4 piles de 125 chaussettes en c * n temps. Avec un seuil de 5 chaussettes, vous pouvez trier chaque pile en 6 manches. (Compter 2 secondes pour jeter une chaussette sur la pile droite, cela vous prendra un peu moins de 4 heures.)

Si vous n'avez que 60 chaussettes, 3 couleurs et 2 sortes de chaussettes (la vôtre / celle de votre femme), vous pouvez trier chaque pile de 10 chaussettes en 1 fois (seuil de nouveau = 5). (Compter 2 secondes cela vous prendra 2 min).

Le tri initial des seaux accélérera votre processus, car il divise vos n chaussettes en k seaux dans le c*ntemps, de sorte que vous n'aurez plus qu'à c*n*log(k)travailler. (Ne tenant pas compte du seuil). Donc, dans l'ensemble, vous faites du n*c*(1 + log(k))travail, où c est le moment de jeter une chaussette sur une pile.

Cette approche sera favorable par rapport à n'importe quelle c*x*n + O(1)méthode à peu près aussi longtemps que log(k) < x - 1.

En informatique, cela peut être utile: nous avons une collection de n choses , un ordre sur elles (longueur) et aussi une relation d'équivalence (informations supplémentaires, par exemple la couleur des chaussettes). La relation d'équivalence nous permet de faire une partition de la collection d'origine, et dans chaque classe d'équivalence, notre ordre est toujours maintenu. Le mappage d'une chose à sa classe d'équivalence peut être effectué dans O (1), donc seul O (n) est nécessaire pour affecter chaque élément à une classe. Nous avons maintenant utilisé nos informations supplémentaires et pouvons procéder de n'importe quelle manière pour trier chaque classe. L'avantage est que les ensembles de données sont déjà considérablement plus petits.

La méthode peut également être imbriquée, si nous avons plusieurs relations d'équivalence -> faire des piles de couleurs, que dans chaque partition de pile sur la texture, que trier sur la longueur. Toute relation d'équivalence qui crée une partition avec plus de 2 éléments de même taille apportera une amélioration de la vitesse par rapport au tri (à condition que nous puissions directement affecter une chaussette à sa pile), et le tri peut se produire très rapidement sur des ensembles de données plus petits.

Vous essayez de résoudre le mauvais problème.

Solution 1: Chaque fois que vous mettez des chaussettes sales dans votre panier à linge, attachez-les en un petit nœud. De cette façon, vous n'aurez pas à faire de tri après le lavage. Pensez-y comme enregistrer un index dans une base de données Mongo. Un peu de travail à venir pour des économies de CPU à l'avenir.

Solution 2: Si c'est l'hiver, vous n'avez pas à porter de chaussettes assorties. Nous sommes programmeurs. Personne n'a besoin de savoir, tant que cela fonctionne.

Solution 3: répartissez le travail. Vous souhaitez effectuer un processus CPU aussi complexe de manière asynchrone, sans bloquer l'interface utilisateur. Prenez ce tas de chaussettes et mettez-les dans un sac. Ne cherchez une paire que lorsque vous en avez besoin. De cette façon, la quantité de travail qu'il faut est beaucoup moins perceptible.

J'espère que cela t'aides!

Cette question est en réalité profondément philosophique. Au fond, il s'agit de savoir si le pouvoir des gens de résoudre des problèmes (le «wetware» de notre cerveau) est équivalent à ce qui peut être accompli par des algorithmes.

Un algorithme évident pour le tri des chaussettes est:

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

Maintenant, l'informatique dans ce problème concerne les étapes

1. "si s s'associe avec une chaussette t en N". À quelle vitesse pouvons-nous nous «souvenir» de ce que nous avons vu jusqu'à présent?
2. "supprimer t de N" et "ajouter s à N". Combien coûte le suivi de ce que nous avons vu jusqu'à présent?

Les êtres humains utiliseront diverses stratégies pour les réaliser. La mémoire humaine est associative , quelque chose comme une table de hachage où les ensembles de caractéristiques des valeurs stockées sont associés aux valeurs correspondantes elles-mêmes. Par exemple, le concept de «voiture rouge» correspond à toutes les voitures rouges dont une personne est capable de se souvenir. Quelqu'un avec une mémoire parfaite a une cartographie parfaite. La plupart des gens sont imparfaits à cet égard (et la plupart des autres). La carte associative a une capacité limitée. Les mappages peuvent biper exister dans diverses circonstances (une bière de trop), être enregistré par erreur ("Je pensais que son nom était Betty, pas Nettie"), ou ne jamais être écrasé même si nous observons que la vérité a changé ("la voiture de papa" évoque "Orange Firebird" alors que nous savions qu'il l'avait échangé contre la Camaro rouge).

Dans le cas des chaussettes, un rappel parfait signifie que regarder une chaussette sproduit toujours la mémoire de son frère t, y compris suffisamment d'informations (où elle se trouve sur la planche à repasser) pour la localiser ten temps constant. Une personne ayant une mémoire photographique accomplit à la fois 1 et 2 en un temps constant sans faute.

Quelqu'un dont la mémoire n'est pas parfaite peut utiliser quelques classes d'équivalence de bon sens basées sur des fonctionnalités à sa disposition pour suivre: taille (papa, maman, bébé), couleur (verdâtre, rougeâtre, etc.), motif (argyle, uni, etc.) , style (foot, genou, etc.). Ainsi, la planche à repasser serait divisée en sections pour les catégories. Cela permet généralement de localiser la catégorie en temps constant par la mémoire, mais une recherche linéaire dans la catégorie "bucket" est alors nécessaire.

Quelqu'un sans mémoire ni imagination (désolé) gardera simplement les chaussettes dans une pile et fera une recherche linéaire de la pile entière.

Un monstre ordonné pourrait utiliser des étiquettes numériques pour les paires comme quelqu'un l'a suggéré. Cela ouvre la porte à un ordre total, qui permet à l'humain d'utiliser exactement les mêmes algorithmes que nous pourrions utiliser avec un CPU: recherche binaire, arbres, hachages, etc.

Le "meilleur" algorithme dépend donc des qualités du logiciel / matériel / logiciel qui le fait fonctionner et de notre volonté de "tricher" en imposant un ordre total aux paires. Un «meilleur» méta- algorithme consiste certainement à embaucher le meilleur trieur de chaussettes au monde: une personne ou une machine qui peut acquérir et stocker rapidement un énorme ensemble N d’ensembles d’attributs de chaussette dans une mémoire associative 1-1 avec recherche en temps constant, insérer, et supprimez. Des personnes et des machines comme celle-ci peuvent être achetées. Si vous en avez une, vous pouvez associer toutes les chaussettes en temps O (N) pour N paires, ce qui est optimal. Les balises de commande totales vous permettent d'utiliser le hachage standard pour obtenir le même résultat avec un ordinateur humain ou matériel.

Coût: Déplacement des chaussettes -> élevé, recherche / recherche de chaussettes en ligne -> petit

Ce que nous voulons faire, c'est réduire le nombre de déplacements et compenser avec le nombre de recherches. En outre, nous pouvons utiliser l'environnement multithrédé de l'Homo Sapiens pour contenir plus de choses dans le cache de descision.

X = vôtre, Y = vos conjoints

De la pile A de toutes les chaussettes:

Choisissez deux chaussettes, placez la chaussette X correspondante sur la ligne X et la chaussette Y sur la ligne Y à la prochaine position disponible.

Faites jusqu'à ce que A soit vide.

Pour chaque ligne X et Y

1. Choisissez la première chaussette en ligne, recherchez le long de la ligne jusqu'à ce qu'elle trouve la chaussette correspondante.

2. Mettez dans la ligne de chaussettes finie correspondante.

3. Facultatif Pendant que vous recherchez la ligne et que la chaussette actuelle que vous regardez est identique à la précédente, effectuez l'étape 2 pour ces chaussettes.

Facultativement, à l'étape 1, vous prenez deux chaussettes de cette ligne au lieu de deux, car la mémoire cache est suffisamment grande, nous pouvons rapidement identifier si l'une des chaussettes correspond à la chaussette actuelle sur la ligne que vous observez. Si vous avez la chance d'avoir trois bras, vous pouvez éventuellement analyser trois chaussettes en même temps étant donné que la mémoire du sujet est suffisamment grande.

Faites jusqu'à ce que X et Y soient vides.

Terminé

Cependant, comme cela a une complexité similaire à celle du tri par sélection, le temps nécessaire est beaucoup moins important en raison des vitesses d'E / S (déplacement des chaussettes) et de la recherche (recherche de la ligne pour une chaussette).

Voici une limite inférieure Omega (n log n) dans un modèle basé sur la comparaison. (La seule opération valide consiste à comparer deux chaussettes.)

Supposons que vous sachiez que vos chaussettes 2n sont disposées de cette façon:

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

où f est une permutation inconnue de l'ensemble {1,2, ..., n}. Le savoir ne peut pas rendre le problème plus difficile. Il y en a n! sorties possibles (correspondances entre la première et la seconde moitié), ce qui signifie que vous avez besoin de comparaisons log (n!) = Omega (n log n). Ceci peut être obtenu par tri.

Étant donné que vous êtes intéressé par les connexions au problème de distinction des éléments: prouver la liaison Omega (n log n) pour la distinction des éléments est plus difficile, car la sortie est binaire oui / non. Ici, la sortie doit être une correspondance et le nombre de sorties possibles suffit pour obtenir une borne décente. Cependant, il existe une variante liée à la distinction des éléments. Supposons que l'on vous donne des chaussettes 2n et demandez-vous si elles peuvent être associées de manière unique. Vous pouvez obtenir une réduction de ED en envoyant (a ₁ , a ₂ , ..., a _n ) à (a ₁ , a ₁ , a ₂ , a ₂ , ..., a _n , a _n ). (Entre parenthèses, la preuve de la dureté de la DE est très intéressante, via la topologie.)

Je pense qu'il devrait y avoir un Omega (n ² ) lié au problème d'origine si vous autorisez uniquement les tests d'égalité. Mon intuition est la suivante: considérons un graphique dans lequel vous ajoutez un bord après un test, et faites valoir que si le graphique n'est pas dense, la sortie n'est pas déterminée de manière unique.

Voici comment je le fais, pour p paires de chaussettes ( n = 2p chaussettes individuelles):

• Prenez une chaussette au hasard dans la pile.
• Pour la première chaussette, ou si toutes les chaussettes choisies précédemment ont été jumelées, placez simplement la chaussette dans la première "fente" d'un "tableau" de chaussettes non appariées devant vous.
• Si vous avez une ou plusieurs chaussettes non appariées sélectionnées, comparez votre chaussette actuelle à toutes les chaussettes non appariées de la matrice.
  • Il est possible de séparer les chaussettes en classes ou types généraux (blanc / noir, cheville / équipage, athlétique / robe) lors de la construction de votre gamme, et "drill-down" pour comparer uniquement à données comparables.
  • Si vous trouvez une correspondance acceptable, assemblez les deux chaussettes et retirez-les du tableau.
  • Si vous ne le faites pas, placez la chaussette actuelle dans le premier emplacement ouvert de la baie.
• Répétez avec chaque chaussette.

Le pire des cas de ce schéma est que chaque paire de chaussettes est suffisamment différente pour qu'elle corresponde exactement et que les n / 2 premières chaussettes que vous choisissez sont toutes différentes. Ceci est votre scénario O (n ² ), et il est extrêmement improbable. Si le nombre de types uniques de chaussettes t est inférieur au nombre de paires p = n / 2 et que les chaussettes de chaque type sont suffisamment semblables (généralement en termes liés à l'usure) pour que toute chaussette de ce type puisse être associée à n'importe quelle autre, alors comme je l'ai déduit ci-dessus, le nombre maximum de chaussettes que vous devrez comparer est t , après quoi la prochaine que vous tirerez seracorrespondre à l'une des chaussettes non appariées. Ce scénario est beaucoup plus probable dans le tiroir à chaussettes moyen que dans le pire des cas et réduit la complexité du pire cas à O (n * t) où généralement t << n .

Approche du monde réel:

Le plus rapidement possible, retirez les chaussettes de la pile non triée une par une et placez-les en piles devant vous. Les piles doivent être disposées dans un espace peu efficace, toutes les chaussettes pointant dans la même direction; le nombre de piles est limité par la distance que vous pouvez facilement atteindre. La sélection d'une pile sur laquelle mettre une chaussette devrait être - aussi rapidement que possible - en mettant une chaussette sur une pile de chaussettes apparemment semblables; l'erreur occasionnelle de type I (mettre une chaussette sur une pile à laquelle elle n'appartient pas) ou de type II (mettre une chaussette dans sa propre pile lorsqu'il y a un tas de chaussettes similaires) peut être tolérée - la considération la plus importante est la vitesse .

Une fois que toutes les chaussettes sont empilées, parcourez rapidement les piles multi-chaussettes en créant des paires et en les retirant (elles se dirigent vers le tiroir). S'il y a des chaussettes non assorties dans la pile, empilez-les à leur meilleur (dans la contrainte la plus rapide possible). Lorsque toutes les piles multi-chaussettes ont été traitées, faites correspondre les chaussettes restantes qui n'ont pas été appariées en raison d'erreurs de type II. Whoosh, vous avez terminé - et j'ai beaucoup de chaussettes et je ne les lave pas tant qu'une grande partie n'est pas sale. Autre remarque pratique: je retourne le haut d'une paire de chaussettes sur l'autre, profitant de leurs propriétés élastiques, pour qu'elles restent ensemble tout en étant transportées dans le tiroir et dans le tiroir.

D'après votre question, il est clair que vous n'avez pas beaucoup d'expérience réelle avec la lessive :). Vous avez besoin d'un algorithme qui fonctionne bien avec un petit nombre de chaussettes non appariables.

Jusqu'à présent, les réponses ne font pas bon usage de nos capacités de reconnaissance des formes humaines. Le jeu de Set fournit un indice sur la façon de bien faire: mettez toutes les chaussettes dans un espace à deux dimensions afin que vous puissiez à la fois bien les reconnaître et les atteindre facilement avec vos mains. Cela vous limite à une zone d'environ 120 * 80 cm environ. De là, sélectionnez les paires que vous reconnaissez et supprimez-les. Mettez des chaussettes supplémentaires dans l'espace libre et répétez. Si vous vous lavez pour les gens avec des chaussettes facilement reconnaissables (les petits enfants viennent à l'esprit), vous pouvez faire un tri radical en sélectionnant d'abord ces chaussettes. Cet algorithme ne fonctionne bien que lorsque le nombre de chaussettes simples est faible

Prenez une première chaussette et placez-la sur une table. Maintenant, choisissez une autre chaussette; s'il correspond au premier sélectionné, placez-le au-dessus du premier. Sinon, placez-le sur la table à une petite distance du premier. Choisissez une troisième chaussette; s'il correspond à l'un des deux précédents, placez-le au-dessus d'eux ou bien placez-le à une petite distance du troisième. Répétez jusqu'à ce que vous ayez ramassé toutes les chaussettes.

Afin de dire à quel point il est efficace d'appairer des chaussettes à partir d'une pile, nous devons d'abord définir la machine, car l'appariement ne se fait ni par une turing ni par une machine à accès aléatoire, qui sont normalement utilisées comme base pour une analyse algorithmique.

La machine

La machine est l'abstraction d'un élément du monde réel appelé être humain. Il est capable de lire depuis l'environnement via une paire d'yeux. Et notre modèle de machine est capable de manipuler l'environnement en utilisant 2 bras. Les opérations logiques et arithmétiques sont calculées à l'aide de notre cerveau (espérons-le ;-)).

Nous devons également considérer le temps d'exécution intrinsèque des opérations atomiques qui peuvent être effectuées avec ces instruments. En raison de contraintes physiques, les opérations qui sont effectuées par un bras ou un œil ont une complexité temporelle non constante. En effet, nous ne pouvons pas déplacer un tas de chaussettes sans fin avec un bras, ni un œil voir la chaussette supérieure sur un tas de chaussettes sans fin.

Cependant, la physique mécanique nous donne aussi quelques goodies. Nous ne sommes pas limités à déplacer au plus une chaussette avec un bras. Nous pouvons déplacer un couple entier d'entre eux à la fois.

Ainsi, selon l'analyse précédente, les opérations suivantes doivent être utilisées dans l'ordre décroissant:

• opérations logiques et arithmétiques
• lecture de l'environnement
• modifications environnementales

Nous pouvons également utiliser le fait que les gens n'ont qu'une quantité très limitée de chaussettes. Une modification environnementale peut donc concerner toutes les chaussettes du velours.

L'algorithme

Voici donc ma suggestion:

1. Répartissez toutes les chaussettes dans la pile sur le sol.
2. Trouvez une paire en regardant les chaussettes au sol.
3. Répétez de 2 jusqu'à ce qu'aucune paire ne puisse être faite.
4. Répétez de 1 jusqu'à ce qu'il n'y ait plus de chaussettes sur le sol.

L'opération 4 est nécessaire, car lors de la répartition des chaussettes sur le sol, certaines chaussettes peuvent en cacher d'autres. Voici l'analyse de l'algorithme:

L'analyse

L'algorithme se termine avec une forte probabilité. Cela est dû au fait que l'on ne trouve pas de paires de chaussettes à l'étape numéro 2.

Pour l'analyse d'exécution suivante de l'association de npaires de chaussettes, nous supposons qu'au moins la moitié des 2nchaussettes ne sont pas masquées après l'étape 1. Dans le cas moyen, nous pouvons trouver des n/2paires. Cela signifie que la boucle de l'étape 4 est exécutée O(log n)fois. L'étape 2 est exécutée O(n^2)fois. On peut donc conclure:

• L'algorithme implique O(ln n + n)des modifications environnementales (étape 1 O(ln n)plus la cueillette de chaque paire de chaussettes du sol)
• L'algorithme implique O(n^2)des lectures environnementales de l'étape 2
• L'algorithme implique O(n^2)des opérations logiques et arithmétiques pour comparer une chaussette avec une autre à l'étape 2

Nous avons donc une complexité d'exécution totale de l' O(r*n^2 + w*(ln n + n))endroit ret wdes facteurs pour les opérations de lecture et d'écriture environnementales respectivement pour une quantité raisonnable de chaussettes. Le coût des opérations logiques et arithmétiques est omis, car nous supposons qu'il faut une quantité constante d'opérations logiques et arithmétiques pour décider si 2 chaussettes appartiennent à la même paire. Cela peut ne pas être possible dans tous les scénarios.

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

Je suis sorti avec une autre solution qui ne promettrait pas moins d'opérations, ni moins de consommation de temps, mais il faudrait essayer de voir si cela peut être une bonne heuristique suffisante pour fournir moins de temps dans une énorme série de paires de chaussettes.

Conditions préalables: Il n'y a aucune garantie qu'il existe les mêmes chaussettes. S'ils sont de la même couleur, cela ne signifie pas qu'ils ont la même taille ou le même motif. Les chaussettes sont mélangées au hasard. Il peut y avoir un nombre impair de chaussettes (certaines manquent, nous ne savons pas combien). Préparez-vous à mémoriser une variable "index" et mettez-la à 0.

Le résultat aura une ou deux piles: 1. "appariées" et 2. "manquantes"

Heuristique:

1. Trouvez la chaussette la plus distinctive.
2. Trouvez sa correspondance.
3. S'il n'y a pas de correspondance, mettez-le sur la pile "manquante".
4. Répétez de 1. jusqu'à ce qu'il n'y ait plus de chaussettes distinctives.
5. S'il y a moins de 6 chaussettes, passez à 11.
6. Associez aveuglément toutes les chaussettes à son voisin (ne les emballez pas)
7. Trouvez toutes les paires appariées, emballez-les et déplacez les paires emballées vers la pile "appariée"; S'il n'y avait pas de nouvelles correspondances - incrémenter "index" de 1
8. Si "indice" est supérieur à 2 (cela peut dépendre de la valeur du nombre de chaussettes car avec un plus grand nombre de chaussettes, il y a moins de chance de les coupler à l'aveugle) passez à 11
9. Mélangez le reste
10. Allez à 1
11. Oubliez "index"
12. Choisissez une chaussette
13. Trouvez sa paire
14. S'il n'y a pas de paire pour la chaussette, déplacez-la sur la pile "manquante"
15. Si une correspondance a été trouvée, associez-la, placez-la dans la pile "correspondante"
16. S'il y a encore plus d'une chaussette, passez à 12
17. S'il n'en reste qu'un, passez au 14
18. Sourire satisfait :)

En outre, il pourrait être ajouté une vérification des chaussettes endommagées également, comme si la suppression de celles-ci. Il pourrait être inséré entre 2 et 3, et entre 13 et 14.

J'ai hâte d'entendre parler de toute expérience ou correction.

Lorsque je trie les chaussettes, je fais un tri approximatif par radix , en déposant des chaussettes à proximité d'autres chaussettes du même type de couleur / motif. Sauf dans le cas où je peux voir une correspondance exacte à / près de l'endroit où je suis sur le point de laisser tomber la chaussette, j'extrais la paire à ce moment-là.

Presque tous les autres algorithmes (y compris la réponse la mieux notée par usr ) trient, puis suppriment les paires. Je trouve qu'en tant qu'humain, il vaut mieux minimiser le nombre de chaussettes envisagées à la fois.

Je le fais en:

1. Choisir une chaussette distinctive (tout ce qui attire mon attention en premier dans la pile).
2. Commencer un tri radix à partir de cet emplacement conceptuel en tirant des chaussettes de la pile en fonction de la similitude avec celle-ci.
3. Placez la nouvelle chaussette près de la pile actuelle, avec une distance basée sur la différence. Si vous vous retrouvez à mettre la chaussette sur une autre parce qu'elle est identique, formez-y la paire et retirez-la. Cela signifie que les comparaisons futures nécessitent moins d'efforts pour trouver le bon endroit.

Cela profite de la capacité humaine de correspondance floue en temps O (1), ce qui équivaut quelque peu à l'établissement d'une carte de hachage sur un appareil informatique.

En tirant d'abord sur les chaussettes distinctives, vous laissez un espace pour «zoomer» sur les caractéristiques qui sont moins distinctives, pour commencer.

Après avoir éliminé la couleur fluro, les chaussettes à rayures et les trois paires de chaussettes longues, vous pourriez vous retrouver avec des chaussettes principalement blanches grossièrement triées en fonction de leur port.

À un moment donné, les différences entre les chaussettes sont suffisamment petites pour que d'autres personnes ne remarquent pas la différence, et aucun effort supplémentaire n'est nécessaire.

Chaque fois que vous prenez une chaussette, placez-la au même endroit. Ensuite, la prochaine chaussette que vous prenez, si elle ne correspond pas à la première chaussette, placez-la à côté de la première. Si c'est le cas, il y a une paire. De cette façon, le nombre de combinaisons n'a pas vraiment d'importance, et il n'y a que deux possibilités pour chaque chaussette que vous prenez - soit elle a une correspondance qui est déjà dans votre gamme de chaussettes, soit elle ne l'est pas, ce qui signifie que vous ajoutez-le à une place dans le tableau.

Cela signifie également que vous n'aurez presque certainement jamais toutes vos chaussettes dans le tableau, car les chaussettes seront retirées au fur et à mesure de leur correspondance.

Considérons une table de hachage de taille «N».

Si nous supposons une distribution normale, alors le nombre estimé d'insertions pour avoir au moins une chaussette mappée sur un seau est NlogN (c'est-à-dire que tous les seaux sont pleins)

Je l'avais dérivé dans le cadre d'un autre casse-tête, mais je serais heureux d'avoir tort. Voici mon article de blog sur le même

Laissez 'N' correspondre à une limite supérieure approximative du nombre de couleurs / motifs uniques de chaussettes que vous avez.

Une fois que vous avez une collision (alias: une allumette), retirez simplement cette paire de chaussettes. Répétez la même expérience avec le prochain lot de chaussettes NlogN. La beauté de cela est que vous pourriez faire des comparaisons parallèles NlogN (résolution de collision) en raison de la façon dont fonctionne l'esprit humain. :-)

Les chaussettes, qu'elles soient réelles ou une structure de données analogue, seraient fournies par paires.

La réponse la plus simple est avant de permettre à la paire d'être séparée, une structure de données unique pour la paire aurait dû être initialisée qui contenait un pointeur vers la chaussette gauche et droite, permettant ainsi aux chaussettes d'être référencées directement ou via leur paire. Une chaussette peut également être étendue pour contenir un pointeur sur son partenaire.

Cela résout tout problème d'appariement informatique en le supprimant avec une couche d'abstraction.

Appliquant la même idée au problème pratique de l'appariement des chaussettes, la réponse apparente est: ne laissez jamais vos chaussettes être dissociées. Les chaussettes sont fournies par paire, placées dans le tiroir par paire (peut-être en les ballant ensemble), portées par paire. Mais le point où la dissociation est possible est dans la laveuse, donc tout ce qui est requis est un mécanisme physique qui permet aux chaussettes de rester ensemble et d'être lavées efficacement.

Il existe deux possibilités physiques:

Pour un objet «paire» qui garde un pointeur sur chaque chaussette, nous pourrions avoir un sac en tissu que nous utilisons pour garder les chaussettes ensemble. Cela semble être une surcharge énorme.

Mais pour que chaque chaussette garde une référence à l'autre, il existe une solution intéressante: un popper (ou un 'bouton pression' si vous êtes américain), comme ceux-ci:

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

Ensuite, tout ce que vous faites est de mettre vos chaussettes en place juste après les avoir retirées et les mettre dans votre panier à linge, et encore une fois vous avez éliminé le problème de devoir associer vos chaussettes avec une abstraction physique du concept de `` paire ''.

Si l'opération "déplacer" est assez coûteuse, et l'opération "comparer" est bon marché, et vous devez quand même déplacer l'ensemble dans un tampon où la recherche est beaucoup plus rapide que dans le stockage d'origine ... intégrez simplement le tri dans le champ obligatoire bouge toi.

J'ai trouvé que l'intégration du processus de tri en suspension pour sécher en fait un jeu d'enfant. Je dois quand même ramasser chaque chaussette, la suspendre (bouger) et cela ne me coûte rien de la suspendre à un endroit précis sur les cordes. Maintenant, juste pour ne pas forcer la recherche de tout le tampon (les cordes), je choisis de placer les chaussettes par couleur / nuance. Plus sombre à gauche, plus clair à droite, devant plus coloré, etc. Maintenant, avant de suspendre chaque chaussette, je regarde dans son "voisinage droit" si une assortie est déjà là - cela limite le "scan" à 2-3 autres chaussettes - et si c'est le cas , J'accroche l'autre juste à côté. Ensuite, je les roule en paires tout en les retirant des cordes, une fois sèches.

Maintenant, cela peut ne pas sembler très différent de la "formation de piles par couleur" suggérée par les meilleures réponses, mais d'abord, en ne choisissant pas des piles discrètes mais des plages, je n'ai aucun problème à classer si "violet" passe à "rouge" ou "bleu"; ça va juste entre. Et puis, en intégrant deux opérations (suspendre pour sécher et trier), le surcoût du tri pendant la suspension équivaut à 10% de ce que serait le tri séparé.

J'ai fini d'appairer mes chaussettes en ce moment, et j'ai trouvé que la meilleure façon de le faire est la suivante:

• Choisissez l'une des chaussettes et rangez-la (créez un `` seau '' pour cette paire)
• Si le suivant est la paire du précédent, placez-le dans le compartiment existant, sinon créez-en un nouveau.

Dans le pire des cas, cela signifie que vous aurez n / 2 seaux différents, et vous aurez n-2 déterminations sur ce que le seau contient la paire de la chaussette actuelle. Évidemment, cet algorithme fonctionne bien si vous n'avez que quelques paires; Je l'ai fait avec 12 paires.

Ce n'est pas si scientifique, mais ça marche bien :)

Ma solution ne correspond pas exactement à vos besoins, car elle nécessite formellement O(n) un espace "supplémentaire". Cependant, compte tenu de mes conditions, il est très efficace dans mon application pratique. Je pense donc que cela devrait être intéressant.

Combiner avec une autre tâche

La condition spéciale dans mon cas est que je n'utilise pas de sèche-linge, accrochez simplement mes chiffons sur un sèche-linge ordinaire. Suspendre des chiffons nécessite des O(n)opérations (au fait, je considère toujours l' emballage des poubelles problème d' bacs ici) et le problème de par sa nature nécessite un espace "supplémentaire" linéaire. Lorsque je prends une nouvelle chaussette dans le seau, j'essaie de l'accrocher à côté de sa paire si la paire est déjà accrochée. Si c'est une chaussette d'une nouvelle paire, je laisse un peu d'espace à côté.

Oracle Machine is Better ;-)

Cela nécessite évidemment un travail supplémentaire pour vérifier si la chaussette correspondante est déjà suspendue quelque part et cela rendrait la solution O(n^2)avec le coefficient environ 1/2pour un ordinateur. Mais dans ce cas, le «facteur humain» est en fait un avantage - je peux généralement très rapidement (presque O(1)) identifier la chaussette assortie si elle était déjà accrochée (probablement une mise en cache imperceptible dans le cerveau est impliquée) - considérez-la comme une sorte de "oracle" limité comme dans Oracle Machine ;-) Nous, les humains ont ces avantages sur les machines numériques dans certains cas ;-)

Je l'ai presque O(n)!

Reliant ainsi le problème de l'appariement des chaussettes au problème des tissus suspendus, j'obtiens O(n)gratuitement "de l'espace supplémentaire", et j'ai une solution qui est à peu près O(n)dans le temps, nécessite juste un peu plus de travail que les simples tissus suspendus et permet d'accéder immédiatement à une paire complète de chaussettes même dans un très mauvais lundi matin ... ;-)

J'espère pouvoir apporter quelque chose de nouveau à ce problème. J'ai remarqué que toutes les réponses négligent le fait qu'il existe deux points où vous pouvez effectuer un prétraitement , sans ralentir vos performances globales de lessive.

De plus, nous n'avons pas besoin d'assumer un grand nombre de chaussettes, même pour les familles nombreuses. Les chaussettes sont retirées du tiroir et sont portées, puis jetées dans un endroit (peut-être une poubelle) où elles restent avant d'être lavées. Bien que je n'appellerais pas ledit bac une pile LIFO, je dirais qu'il est sûr de supposer que

1. les gens jettent leurs deux chaussettes à peu près dans la même zone de la poubelle,
2. le bac n'est pas randomisé à aucun moment, et donc
3. tout sous-ensemble pris du haut de ce bac contient généralement les deux chaussettes d'une paire.

Étant donné que toutes les machines à laver que je connais sont de taille limitée (quel que soit le nombre de chaussettes que vous devez laver), et la randomisation réelle se produit dans la machine à laver, peu importe le nombre de chaussettes que nous avons, nous avons toujours de petits sous-ensembles qui ne contiennent presque pas de singletons.

Nos deux étapes de prétraitement sont «mettre les chaussettes sur la corde à linge» et «retirer les chaussettes de la corde à linge», ce que nous devons faire, afin d'obtenir des chaussettes non seulement propres mais aussi sèches. Comme pour les machines à laver, les cordes à linge sont finies, et je suppose que nous avons toute la partie de la ligne où nous mettons nos chaussettes en vue.

Voici l'algorithme pour 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 
 }
}

Ne perdez pas votre temps à déplacer des chaussettes ou à chercher la meilleure combinaison, tout cela devrait être fait en O (n), dont nous aurions également besoin pour les mettre sur la ligne sans tri. Les chaussettes ne sont pas encore appariées, nous n'avons que plusieurs groupes de similitudes sur la ligne. Il est utile que nous ayons un ensemble limité de chaussettes ici, car cela nous aide à créer de "bons" clusters (par exemple, s'il n'y a que des chaussettes noires dans l'ensemble de chaussettes, le regroupement par couleurs ne serait pas la voie à suivre)

Voici l'algorithme pour 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
 }

Je dois souligner que pour améliorer la vitesse des étapes restantes, il est sage de ne pas choisir aléatoirement la prochaine chaussette, mais de prendre séquentiellement chaussette après chaussette de chaque cluster. Les deux étapes de prétraitement ne prennent pas plus de temps que de simplement mettre les chaussettes sur la ligne ou dans le panier, ce que nous devons faire quoi qu'il arrive, cela devrait donc améliorer considérablement les performances du linge.

Après cela, il est facile de faire l'algorithme de partitionnement de hachage. Habituellement, environ 75% des chaussettes sont déjà appariées, me laissant avec un très petit sous-ensemble de chaussettes, et ce sous-ensemble est déjà (quelque peu) groupé (je n'introduis pas beaucoup d'entropie dans mon panier après les étapes de prétraitement). Une autre chose est que les grappes restantes ont tendance à être suffisamment petites pour être manipulées en même temps, il est donc possible de retirer une grappe entière du panier.

Voici l'algorithme pour sort_remaining_clusters ():

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

Après cela, il ne reste plus que quelques chaussettes. C'est là que j'introduis des chaussettes non appariées dans le système et traite les chaussettes restantes sans algorithme spécial - les chaussettes restantes sont très peu nombreuses et peuvent être traitées visuellement très rapidement.

Pour toutes les chaussettes restantes, je suppose que leurs homologues ne sont toujours pas lavés et les range pour la prochaine itération. Si vous enregistrez une croissance de chaussettes non appariées au fil du temps (une "fuite de chaussette"), vous devriez vérifier votre poubelle - elle pourrait être randomisée (avez-vous des chats qui dorment là-dedans?)

Je sais que ces algorithmes prennent beaucoup d'hypothèses: une poubelle qui agit comme une sorte de pile LIFO, une machine à laver normale limitée et une corde à linge normale limitée - mais cela fonctionne toujours avec un très grand nombre de chaussettes.

À propos du parallélisme: Tant que vous jetez les deux chaussettes dans le même bac, vous pouvez facilement paralléliser toutes ces étapes.

J'ai pris des mesures simples pour réduire mes efforts en un processus prenant du temps O (1).

En réduisant mes entrées à l'un des deux types de chaussettes (chaussettes blanches pour les loisirs, chaussettes noires pour le travail), je n'ai qu'à déterminer laquelle des deux chaussettes j'ai en main. (Techniquement, comme ils ne sont jamais lavés ensemble, j'ai réduit le processus à O (0).)

Un effort initial est nécessaire pour trouver des chaussettes souhaitables et acheter en quantité suffisante pour éliminer le besoin de vos chaussettes existantes. Comme je l'avais fait avant mon besoin de chaussettes noires, mon effort était minime, mais le kilométrage peut varier.

Un tel effort initial a été vu à plusieurs reprises dans un code très populaire et efficace. Les exemples incluent # DEFINE'ing pi à plusieurs décimales (d'autres exemples existent, mais c'est celui qui me vient à l'esprit en ce moment).

Créez une table de hachage qui sera utilisée pour les chaussettes inégalées, en utilisant le motif comme hachage. Parcourez les chaussettes une par une. Si la chaussette a une correspondance de motif dans la table de hachage, retirez la chaussette de la table et faites une paire. Si la chaussette n'a pas de correspondance, mettez-la dans le tableau.

Le problème du tri de vos n paires de chaussettes est O (n) . Avant de les jeter dans le panier à linge , vous enfilez celui de gauche vers celui de droite. En les retirant, vous coupez le fil et mettez chaque paire dans votre tiroir - 2 opérations sur n paires, donc O (n).

Maintenant, la question suivante est simplement de savoir si vous faites votre propre lessive et si votre femme fait la sienne. Il s'agit probablement d'un problème dans un domaine de problèmes entièrement différent . :)