Gestern habe ich die Socken aus der sauberen Wäsche gepaart und herausgefunden, dass meine Arbeitsweise nicht sehr effizient ist. Ich machte eine naive Suche - nahm eine Socke und "iterierte" den Stapel, um sein Paar zu finden. Dies erfordert Iterieren über n / 2 * n / 4 = n ² /8 Socken im Durchschnitt.

Als Informatiker dachte ich, was ich tun könnte? Das Sortieren (nach Größe / Farbe / ...) kam natürlich in den Sinn, um eine O (NlogN) -Lösung zu erhalten.

Hashing oder andere nicht vorhandene Lösungen sind keine Option, da ich meine Socken nicht duplizieren kann (obwohl es schön sein könnte, wenn ich könnte).

Die Frage ist also im Grunde:

Was ist bei einem Stapel von nSockenpaaren, die 2nElemente enthalten (vorausgesetzt, jede Socke hat genau ein passendes Paar), der beste Weg, um sie effizient mit bis zu logarithmischem zusätzlichen Platz zu verbinden? (Ich glaube, ich kann mich bei Bedarf an diese Menge an Informationen erinnern.)

Ich freue mich über eine Antwort, die folgende Aspekte behandelt:

• Eine allgemeine theoretische Lösung für eine Vielzahl von Socken.
• Die tatsächliche Anzahl der Socken ist nicht so groß, ich glaube meinem Ehepartner nicht und ich habe mehr als 30 Paare. (Und es ist ziemlich einfach, zwischen meinen und ihren Socken zu unterscheiden; kann dies auch verwendet werden?)
• Entspricht es dem Problem der Elementunterscheidbarkeit ?

Es wurden Sortierlösungen vorgeschlagen, aber das Sortieren ist etwas zu viel : Wir brauchen keine Ordnung; Wir brauchen nur Gleichstellungsgruppen .

So Hashing würde ausreichen , um (und schneller).

1. Bilden Sie für jede Sockenfarbe einen Stapel . Iterieren Sie über alle Socken in Ihrem Eingabekorb und verteilen Sie sie auf den Farbstapeln .
2. Iterieren Sie über jeden Stapel und verteilen Sie ihn nach einer anderen Metrik (z. B. Muster) auf den zweiten Stapelsatz
3. Wenden Sie dieses Schema rekursiv an, bis Sie alle Socken auf sehr kleine Stapel verteilt haben, die Sie sofort visuell verarbeiten können

Diese Art der rekursiven Hash-Partitionierung wird tatsächlich von SQL Server durchgeführt, wenn ein Hash-Join oder eine Hash-Aggregation über große Datenmengen erforderlich ist. Es verteilt seinen Build-Eingabestream auf viele Partitionen, die unabhängig sind. Dieses Schema skaliert linear auf beliebige Datenmengen und mehrere CPUs.

Sie benötigen keine rekursive Partitionierung, wenn Sie einen Verteilungsschlüssel (Hash-Schlüssel) finden, der genügend Buckets bereitstellt, sodass jeder Bucket klein genug ist, um sehr schnell verarbeitet zu werden. Leider glaube ich nicht, dass Socken eine solche Eigenschaft haben.

Wenn jede Socke eine Ganzzahl namens "PairID" hätte, könnte man sie leicht in 10 Eimer gemäß PairID % 10(der letzten Ziffer) verteilen .

Die beste Partitionierung in der realen Welt, die ich mir vorstellen kann, ist das Erstellen eines Rechtecks ​​aus Stapeln : Eine Dimension ist Farbe, die andere ist das Muster. Warum ein Rechteck? Weil wir O (1) zufälligen Zugriff auf Pfähle brauchen. (Ein 3D- Quader würde auch funktionieren, aber das ist nicht sehr praktisch.)

Aktualisieren:

Was ist mit Parallelität ? Können mehrere Menschen schneller zu den Socken passen?

1. Die einfachste Parallelisierungsstrategie besteht darin, dass mehrere Arbeiter aus dem Eingabekorb nehmen und die Socken auf die Stapel legen. Das vergrößert sich nur so sehr - stellen Sie sich 100 Menschen vor, die über 10 Stapel kämpfen. Die Synchronisationskosten (die sich in Handkollisionen und menschlicher Kommunikation äußern) zerstören die Effizienz und die Beschleunigung (siehe das Gesetz über die universelle Skalierbarkeit !). Ist dies anfällig für Deadlocks ? Nein, da jeder Arbeiter jeweils nur auf einen Stapel zugreifen muss. Mit nur einem "Schloss" kann es keinen Deadlock geben. Livelocks können möglich sein, je nachdem, wie die Menschen den Zugang zu Pfählen koordinieren. Sie könnten nur zufälliges Backoff verwendenWie Netzwerkkarten tun Sie dies auf physischer Ebene, um zu bestimmen, welche Karte ausschließlich auf das Netzwerkkabel zugreifen kann. Wenn es für Netzwerkkarten funktioniert , sollte es auch für Menschen funktionieren.
2. Es skaliert fast unbegrenzt, wenn jeder Arbeiter seine eigenen Stapel hat . Arbeiter können dann große Stücke Socken aus dem Eingabekorb nehmen (sehr wenig Streit, da sie dies selten tun) und müssen beim Verteilen der Socken überhaupt nicht synchronisieren (weil sie fadenlokale Stapel haben). Am Ende müssen alle Arbeiter ihre Stapelsätze zusammenschließen. Ich glaube, dass dies in O (Protokoll (Anzahl der Arbeiter * Stapel pro Arbeiter)) erfolgen kann, wenn die Arbeiter einen Aggregationsbaum bilden .

Was ist mit dem Problem der Elementunterscheidbarkeit ? Wie im Artikel angegeben, kann das Problem der Elementunterscheidbarkeit in gelöst werden O(N). Dies gilt auch für das Sockenproblem (auch O(N)wenn Sie nur einen Verteilungsschritt benötigen (ich habe mehrere Schritte nur vorgeschlagen, weil Menschen schlecht in Berechnungen sind - ein Schritt reicht aus, wenn Sie weiterverteilen md5(color, length, pattern, ...), dh einen perfekten Hash aller Attribute)).

Natürlich kann man nicht schneller fahren als O(N), also haben wir die optimale Untergrenze erreicht .

Obwohl die Ausgänge nicht genau gleich sind (in einem Fall nur ein Boolescher Wert. In dem anderen Fall die Sockenpaare), sind die asymptotischen Komplexitäten gleich.

Da sich die Architektur des menschlichen Gehirns völlig von einer modernen CPU unterscheidet, ist diese Frage praktisch nicht sinnvoll.

Menschen können CPU-Algorithmen für sich gewinnen, indem sie "ein passendes Paar finden" eine Operation für einen Satz sein können, der nicht zu groß ist.

Mein Algorithmus:

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

Zumindest verwende ich das im wirklichen Leben und finde es sehr effizient. Der Nachteil ist, dass es eine flache Oberfläche erfordert, aber normalerweise reichlich vorhanden ist.

Fall 1 : Alle Socken sind identisch (das mache ich übrigens im wirklichen Leben).

Wählen Sie zwei davon aus, um ein Paar zu bilden. Ständige Zeit.

Fall 2 : Es gibt eine konstante Anzahl von Kombinationen (Besitz, Farbe, Größe, Textur usw.).

Verwenden Sie die Radix-Sortierung . Dies ist nur eine lineare Zeit, da kein Vergleich erforderlich ist.

Fall 3 : Die Anzahl der Kombinationen ist nicht im Voraus bekannt (allgemeiner Fall).

Wir müssen einen Vergleich durchführen, um zu überprüfen, ob zwei Socken paarweise geliefert werden. Wählen Sie einen der O(n log n)vergleichsbasierten Sortieralgorithmen.

Im wirklichen Leben, wenn die Anzahl der Socken relativ klein (konstant) ist, würden diese theoretisch optimalen Algorithmen jedoch nicht gut funktionieren. Es kann sogar noch länger dauern als die sequentielle Suche, die theoretisch eine quadratische Zeit erfordert.

Nicht algorithmische Antwort, aber "effizient", wenn ich es tue:

• Schritt 1) ​​Entsorgen Sie alle vorhandenen Socken

• Schritt 2) Gehen Sie zu Walmart und kaufen Sie sie in Paketen mit 10 - n Päckchen Weiß und m Päckchen Schwarz. Keine Notwendigkeit für andere Farben im Alltag.

Aber von Zeit zu Zeit muss ich das noch einmal machen (verlorene Socken, beschädigte Socken usw.), und ich hasse es, perfekt gute Socken zu oft wegzuwerfen (und ich wünschte, sie verkaufen immer die gleiche Sockenreferenz!), Also habe ich kürzlich genommen Ein anderer Versuch.

Algorithmische Antwort:

Bedenken Sie, dass Ihre Wahrscheinlichkeit, bei einer naiven Suche die passende Socke zu finden, sehr gering ist, wenn Sie nur eine Socke für den zweiten Sockenstapel ziehen.

• Nehmen Sie also fünf davon zufällig auf und merken Sie sich ihre Form oder Länge.

Warum fünf? Normalerweise sind Menschen gut darin, sich an fünf bis sieben verschiedene Elemente im Arbeitsspeicher zu erinnern - ein bisschen wie das menschliche Äquivalent eines RPN- Stapels - fünf ist ein sicherer Standard.

• Nimm einen vom Stapel 2n-5.

• Suchen Sie nun nach einer Übereinstimmung (visuelle Musterübereinstimmung - Menschen können das gut mit einem kleinen Stapel) innerhalb der fünf, die Sie gezeichnet haben. Wenn Sie keine finden, fügen Sie diese zu Ihren fünf hinzu.

• Wähle weiterhin zufällig Socken vom Stapel und vergleiche sie mit deinen 5 + 1-Socken für ein Match. Wenn Ihr Stack wächst, wird dies Ihre Leistung verringern, aber Ihre Chancen erhöhen. Viel schneller.

Schreiben Sie die Formel auf, um zu berechnen, wie viele Stichproben Sie für eine 50% ige Gewinnchance ziehen müssen. IIRC ist ein hypergeometrisches Gesetz.

Ich mache das jeden Morgen und brauche selten mehr als drei Draws - aber ich habe nähnliche Paare (ungefähr 10, gib oder nimm die verlorenen) mgeformter weißer Socken. Jetzt können Sie die Größe meines Lagerstapels schätzen :-)

Übrigens stellte ich fest, dass die Summe der Transaktionskosten für das Sortieren aller Socken jedes Mal, wenn ich ein Paar benötigte, weitaus geringer war als einmal und das Binden der Socken. Ein Just-in-Time funktioniert besser, weil Sie dann die Socken nicht binden müssen und es auch eine abnehmende marginale Rendite gibt (das heißt, Sie suchen immer nach den zwei oder drei Socken, die Sie irgendwo in der Wäsche haben und die Sie brauchen um das Matching Ihrer Socken zu beenden und Sie verlieren Zeit dafür).

Ich nehme die erste Socke und lege sie hin (z. B. am Rand der Wäscheschale). Dann nehme ich eine andere Socke und überprüfe, ob sie mit der ersten Socke identisch ist. Wenn ja, entferne ich beide. Wenn nicht, lege ich es neben die erste Socke. Dann nehme ich die dritte Socke und vergleiche sie mit den ersten beiden (wenn sie noch da sind). Usw.

Dieser Ansatz kann ziemlich einfach in einem Array implementiert werden, vorausgesetzt, dass das "Entfernen" von Socken eine Option ist. Eigentlich müssen Sie nicht einmal Socken "entfernen". Wenn Sie die Socken nicht sortieren müssen (siehe unten), können Sie sie einfach verschieben und erhalten ein Array, in dem alle Socken paarweise im Array angeordnet sind.

Unter der Annahme, dass die einzige Operation für Socken darin besteht, die Gleichheit zu vergleichen, ist dieser Algorithmus im Grunde immer noch ein n ² -Algorithmus, obwohl ich nichts über den Durchschnittsfall weiß (ich habe nie gelernt, das zu berechnen).

Das Sortieren verbessert natürlich die Effizienz, insbesondere im wirklichen Leben, wo Sie leicht eine Socke zwischen zwei andere Socken "einführen" können. Bei der Berechnung könnte das gleiche durch einen Baum erreicht werden, aber das ist zusätzlicher Platz. Und natürlich sind wir wieder bei NlogN (oder ein bisschen mehr, wenn es mehrere Socken gibt, die nach Sortierkriterien gleich sind, aber nicht aus demselben Paar).

Davon abgesehen fällt mir nichts ein, aber diese Methode scheint im wirklichen Leben ziemlich effizient zu sein. :) :)

Dies stellt die falsche Frage. Die richtige Frage ist, warum ich Zeit damit verbringe, Socken zu sortieren. Wie viel kostet es jährlich, wenn Sie Ihre Freizeit für X Geldeinheiten Ihrer Wahl bewerten?

Und meistens ist dies nicht irgendeine Freizeit, sondern eine morgendliche Freizeit, die Sie im Bett verbringen, an Ihrem Kaffee nippen oder etwas früher abreisen und nicht im Verkehr gefangen werden können.

Es ist oft gut, einen Schritt zurückzutreten und das Problem zu umgehen.

Und es gibt einen Weg!

Finde eine Socke, die du magst. Berücksichtigen Sie alle relevanten Merkmale: Farbe bei unterschiedlichen Lichtverhältnissen, Gesamtqualität und Haltbarkeit, Komfort bei unterschiedlichen Klimabedingungen und Geruchsabsorption. Wichtig ist auch, dass sie bei der Lagerung nicht an Elastizität verlieren, sodass natürliche Stoffe gut sind und in einer Plastikverpackung erhältlich sein sollten.

Es ist besser, wenn es keinen Unterschied zwischen linken und rechten Fußsocken gibt, aber es ist nicht kritisch. Wenn die Socken von links nach rechts symmetrisch sind, ist das Finden eines Paares eine O (1) -Operation, und das Sortieren der Socken ist eine ungefähre O (M) -Operation, wobei M die Anzahl der Stellen in Ihrem Haus ist, die Sie mit Socken übersät haben, idealerweise einige kleine konstante Zahl.

Wenn Sie sich für ein ausgefallenes Paar mit unterschiedlichen linken und rechten Socken entschieden haben, nehmen Sie O (N + M), wobei N die Anzahl der Socken und M die gleiche wie oben ist. Jemand anderes kann die Formel für durchschnittliche Iterationen des Findens des ersten Paares angeben, aber der schlechteste Fall für das Finden eines Paares mit blinder Suche ist N / 2 + 1, was für vernünftiges N astronomisch unwahrscheinlich wird. Dies kann durch Verwendung eines erweiterten Bildes beschleunigt werden Erkennungsalgorithmen und Heuristiken beim Scannen des Stapels unsortierter Socken mit Mk1 Eyeball .

Ein Algorithmus zum Erreichen der Effizienz der O (1) -Sockenpaarung (unter der Annahme einer symmetrischen Socke) lautet also:

1. Sie müssen abschätzen, wie viele Paar Socken Sie für den Rest Ihres Lebens benötigen, oder vielleicht bis Sie in Rente gehen und in ein wärmeres Klima ziehen, ohne jemals wieder Socken tragen zu müssen. Wenn Sie jung sind, können Sie auch abschätzen, wie lange es dauert, bis wir alle Socken-Sortierroboter in unseren Häusern haben, und das ganze Problem wird irrelevant.

2. Sie müssen herausfinden, wie Sie Ihre ausgewählte Socke in loser Schüttung bestellen können, wie viel sie kostet und wie sie geliefert wird.

3. Bestellen Sie die Socken!

4. Werde deine alten Socken los.

Ein alternativer Schritt 3 würde darin bestehen, die Kosten für den Kauf der gleichen Menge vielleicht billigerer Socken über die Jahre hinweg paarweise zu vergleichen und die Kosten für das Sortieren von Socken zu addieren, aber nehmen Sie mein Wort: Der Kauf in loser Schüttung ist billiger! Außerdem erhöhen Socken im Lager mit der Inflationsrate des Aktienkurses an Wert, was mehr ist, als Sie bei vielen Investitionen erhalten würden. Andererseits gibt es auch Lagerkosten, aber Socken nehmen im obersten Regal eines Schranks wirklich nicht viel Platz ein.

Problem gelöst. Holen Sie sich einfach neue Socken, werfen / spenden Sie Ihre alten weg und leben Sie glücklich, nachdem Sie wissen, dass Sie für den Rest Ihres Lebens jeden Tag Geld und Zeit sparen.

Die theoretische Grenze ist O (n), da Sie jede Socke berühren müssen (es sei denn, einige sind bereits irgendwie gepaart).

Sie können O (n) mit Radix-Sortierung erreichen . Sie müssen nur einige Attribute für die Eimer auswählen.

1. Zuerst kannst du wählen (ihre, meine) - teile sie in 2 Stapel auf,
2. Verwenden Sie dann Farben (kann eine beliebige Reihenfolge für die Farben haben, z. B. alphabetisch nach Farbnamen) - teilen Sie sie nach Farbe in Stapel auf (denken Sie daran, die ursprüngliche Reihenfolge ab Schritt 1 für alle Socken im selben Stapel beizubehalten).
3. dann Länge der Socke,
4. dann Textur, ....

Wenn Sie eine begrenzte Anzahl von Attributen auswählen können, aber genügend Attribute, die jedes Paar eindeutig identifizieren können, sollten Sie in O (k * n) arbeiten, was O (n) ist, wenn wir berücksichtigen können, dass k begrenzt ist.

Als praktische Lösung:

1. Machen Sie schnell Stapel von leicht unterscheidbaren Socken. (Sprich nach Farbe)
2. Quicksortieren Sie jeden Stapel und verwenden Sie zum Vergleich die Länge der Socke. Als Mensch können Sie ziemlich schnell entscheiden, welche Socke zum Partitionieren verwendet werden soll, um den schlimmsten Fall zu vermeiden. (Sie können mehrere Socken parallel sehen, nutzen Sie das zu Ihrem Vorteil!)
3. Hören Sie auf, Stapel zu sortieren, wenn sie eine Schwelle erreicht haben, bei der Sie bequem sofort Paare und ungepaarte Socken finden können

Wenn Sie 1000 Socken mit 8 Farben und einer durchschnittlichen Verteilung haben, können Sie 4 Stapel von jeweils 125 Socken in c * n-Zeit herstellen. Mit einer Schwelle von 5 Socken können Sie jeden Stapel in 6 Läufen sortieren. (Wenn Sie 2 Sekunden zählen, um eine Socke auf den richtigen Stapel zu werfen, benötigen Sie weniger als 4 Stunden.)

Wenn Sie nur 60 Socken, 3 Farben und 2 Arten von Socken (Ihre / die Ihrer Frau) haben, können Sie jeden Stapel von 10 Socken in 1 Durchläufen sortieren (erneut Schwelle = 5). (Nach 2 Sekunden dauert es 2 Minuten).

Die anfängliche Sortierung der Eimer beschleunigt Ihren Prozess, da Ihre n Socken c*nrechtzeitig in k Eimer aufgeteilt werden, sodass Sie nur noch c*n*log(k)arbeiten müssen. (Ohne Berücksichtigung der Schwelle). Alles in allem erledigen Sie also Ihre n*c*(1 + log(k))Arbeit, wobei c die Zeit ist, eine Socke auf einen Stapel zu werfen.

Dieser Ansatz ist im Vergleich zu jeder c*x*n + O(1)Methode ungefähr so ​​lange günstig wie log(k) < x - 1.

In der Informatik kann dies hilfreich sein: Wir haben eine Sammlung von n Dingen , eine Reihenfolge (Länge) und auch eine Äquivalenzbeziehung (zusätzliche Informationen, zum Beispiel die Farbe von Socken). Die Äquivalenzbeziehung ermöglicht es uns, eine Partition der ursprünglichen Sammlung zu erstellen, und in jeder Äquivalenzklasse wird unsere Reihenfolge weiterhin beibehalten. Die Zuordnung eines Objekts zu seiner Äquivalenzklasse kann in O (1) erfolgen, sodass nur O (n) erforderlich ist, um jedes Element einer Klasse zuzuweisen. Jetzt haben wir unsere zusätzlichen Informationen verwendet und können jede Klasse auf beliebige Weise sortieren. Der Vorteil ist, dass die Datensätze bereits deutlich kleiner sind.

Die Methode kann auch verschachtelt werden, wenn wir mehrere Äquivalenzbeziehungen haben -> Farbstapel erstellen, als innerhalb jeder Stapelpartition auf Textur, als nach Länge sortieren. Jede Äquivalenzbeziehung, die eine Partition mit mehr als 2 Elementen mit ungefähr gleicher Größe erstellt, führt zu einer Geschwindigkeitsverbesserung gegenüber dem Sortieren (vorausgesetzt, wir können dem Stapel direkt eine Socke zuweisen), und das Sortieren kann bei kleineren Datensätzen sehr schnell erfolgen.

Sie versuchen, das falsche Problem zu lösen.

Lösung 1: Binden Sie schmutzige Socken jedes Mal, wenn Sie sie in Ihren Wäschekorb legen, zu einem kleinen Knoten zusammen. Auf diese Weise müssen Sie nach dem Waschen keine Sortierung mehr durchführen. Stellen Sie sich vor, Sie registrieren einen Index in einer Mongo-Datenbank. Ein wenig Arbeit voraus für einige CPU-Einsparungen in der Zukunft.

Lösung 2: Wenn es Winter ist, müssen Sie keine passenden Socken tragen. Wir sind Programmierer. Niemand muss es wissen, solange es funktioniert.

Lösung 3: Verteilen Sie die Arbeit. Sie möchten einen so komplexen CPU-Prozess asynchron ausführen, ohne die Benutzeroberfläche zu blockieren. Nehmen Sie diesen Stapel Socken und stopfen Sie sie in eine Tasche. Suchen Sie nur dann nach einem Paar, wenn Sie es brauchen. Auf diese Weise fällt der Arbeitsaufwand viel weniger auf.

Hoffe das hilft!

Diese Frage ist eigentlich zutiefst philosophisch. Im Kern geht es darum, ob die Fähigkeit der Menschen, Probleme zu lösen (die "Wetware" unseres Gehirns), dem entspricht, was mit Algorithmen erreicht werden kann.

Ein offensichtlicher Algorithmus zum Sortieren von Socken ist:

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

Jetzt dreht sich in der Informatik in diesem Problem alles um die Schritte

1. "wenn s mit einer Socke t in N paart". Wie schnell können wir uns an das "erinnern", was wir bisher gesehen haben?
2. "entferne t von N" und "füge s zu N hinzu". Wie teuer ist es, den Überblick über das zu behalten, was wir bisher gesehen haben?

Menschen werden verschiedene Strategien anwenden, um diese zu bewirken. Das menschliche Gedächtnis ist assoziativ , so etwas wie eine Hash-Tabelle, in der Feature-Sets gespeicherter Werte mit den entsprechenden Werten selbst gepaart werden. Zum Beispiel wird das Konzept des "roten Autos" allen roten Autos zugeordnet, an die sich eine Person erinnern kann. Jemand mit einem perfekten Gedächtnis hat eine perfekte Zuordnung. Die meisten Menschen sind in dieser Hinsicht unvollkommen (und die meisten anderen). Die assoziative Karte hat eine begrenzte Kapazität. Zuordnungen können piepen unter verschiedenen Umständen nicht mehr existieren (ein Bier zu viel), irrtümlich aufgezeichnet werden ("Ich dachte, ihr Name war Betty, nicht Nettie") oder niemals überschrieben werden, obwohl wir beobachten, dass sich die Wahrheit geändert hat ("Papas Auto" ruft hervor "orange Firebird", als wir tatsächlich wussten, dass er das gegen den roten Camaro eingetauscht hatte).

Im Fall von Socken bedeutet perfekter Rückruf, dass das Betrachten einer Socke simmer die Erinnerung an ihr Geschwister erzeugt t, einschließlich genügend Informationen (wo sie sich auf dem Bügelbrett befindet), um sie tin konstanter Zeit zu lokalisieren . Eine Person mit fotografischem Gedächtnis erreicht sowohl 1 als auch 2 in konstanter Zeit ohne Fehler.

Jemand mit weniger als perfektem Gedächtnis könnte einige Commonsense-Äquivalenzklassen verwenden, die auf Merkmalen innerhalb seiner Fähigkeit basieren, zu verfolgen: Größe (Papa, Mama, Baby), Farbe (grünlich, rötlich usw.), Muster (Argyle, Plain usw.) , Stil (Footie, kniehoch usw.). Das Bügelbrett würde also in Abschnitte für die Kategorien unterteilt. Dies ermöglicht normalerweise, dass die Kategorie in konstanter Zeit nach Speicher lokalisiert wird, dann ist jedoch eine lineare Suche durch die Kategorie "Bucket" erforderlich.

Jemand ohne Gedächtnis oder Vorstellungskraft (sorry) wird nur die Socken auf einem Stapel behalten und eine lineare Suche des gesamten Stapels durchführen.

Ein ordentlicher Freak könnte numerische Bezeichnungen für Paare verwenden, wie jemand vorgeschlagen hat. Dies öffnet die Tür zu einer vollständigen Reihenfolge, die es dem Menschen ermöglicht, genau die gleichen Algorithmen zu verwenden, die wir mit einer CPU verwenden könnten: binäre Suche, Bäume, Hashes usw.

Der "beste" Algorithmus hängt also von den Eigenschaften der Wetware / Hardware / Software ab, auf der er ausgeführt wird, und von unserer Bereitschaft, zu "schummeln", indem wir Paaren eine Gesamtreihenfolge auferlegen. Sicherlich ist es ein "bester" Meta- Algorithmus, den weltbesten Socken-Sortierer einzustellen: eine Person oder Maschine, die eine große Menge N von Sockenattribut-Sets in einem 1-1-assoziativen Speicher mit konstanter Zeitsuche, Einfügen, Einfügen, schnell erwerben und speichern kann. und löschen. Sowohl Menschen als auch Maschinen wie diese können beschafft werden. Wenn Sie eine haben, können Sie alle Socken in O (N) Zeit für N Paare koppeln, was optimal ist. Mit den Gesamtauftrags-Tags können Sie Standard-Hashing verwenden, um das gleiche Ergebnis mit einem menschlichen oder einem Hardware-Computer zu erzielen.

Kosten: Socken bewegen -> hoch, Socken in der Schlange finden / suchen -> klein

Wir möchten die Anzahl der Züge reduzieren und durch die Anzahl der Suchvorgänge kompensieren. Außerdem können wir die Multithred-Umgebung des Homo Sapiens nutzen, um mehr Dinge im Entscheidungscache zu speichern.

X = Ihre, Y = Ihre Ehepartner

Von Stapel A aller Socken:

Wählen Sie zwei Socken aus, platzieren Sie die entsprechende X-Socke in der X-Linie und die Y-Socke in der Y-Linie an der nächsten verfügbaren Position.

Tun Sie, bis A leer ist.

Für jede Zeile X und Y.

1. Wählen Sie die erste Socke in der Reihe aus und suchen Sie entlang der Linie, bis die entsprechende Socke gefunden wird.

2. In die entsprechende fertige Sockenreihe legen.

3. Optional Führen Sie Schritt 2 für diese Socken aus, während Sie die Linie durchsuchen und die aktuelle Socke, die Sie betrachten, mit der vorherigen identisch ist.

Optional zu Schritt eins nehmen Sie zwei Socken von dieser Zeile anstelle von zwei, da der Caching-Speicher groß genug ist, können wir schnell feststellen, ob eine der Socken mit der aktuellen in der beobachteten Zeile übereinstimmt. Wenn Sie das Glück haben, drei Arme zu haben, können Sie möglicherweise drei Socken gleichzeitig analysieren, da die Erinnerung an das Motiv groß genug ist.

Tun Sie dies, bis sowohl X als auch Y leer sind.

Erledigt

Da dies jedoch eine ähnliche Komplexität als Auswahlsortierung aufweist, ist die benötigte Zeit aufgrund der Geschwindigkeit von E / A (sich bewegende Socken) und Suchen (Durchsuchen der Linie nach einer Socke) weitaus geringer.

Hier ist eine Omega (n log n) -Untergrenze im vergleichsbasierten Modell. (Die einzig gültige Operation ist der Vergleich zweier Socken.)

Angenommen, Sie wissen, dass Ihre 2n-Socken folgendermaßen angeordnet sind:

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

Dabei ist f eine unbekannte Permutation der Menge {1,2, ..., n}. Das zu wissen kann das Problem nicht erschweren. Es gibt n! Mögliche Ausgaben (Übereinstimmungen zwischen der ersten und der zweiten Hälfte), was bedeutet, dass Sie log (n!) = Omega (n log n) Vergleiche benötigen. Dies ist durch Sortieren möglich.

Da Sie an Verbindungen zum Problem der Elementunterscheidbarkeit interessiert sind, ist es schwieriger zu beweisen, dass Omega (n log n) für die Elementunterscheidbarkeit gebunden ist, da die Ausgabe binär Ja / Nein ist. Hier muss die Ausgabe übereinstimmen und die Anzahl der möglichen Ausgaben reicht aus, um eine anständige Grenze zu erhalten. Es gibt jedoch eine Variante, die mit der Unterscheidbarkeit von Elementen verbunden ist. Angenommen, Sie erhalten 2n Socken und fragen sich, ob sie eindeutig gepaart werden können. Sie können eine Reduzierung von ED erhalten, indem Sie (a ₁ , a ₂ , ..., a _n ) an (a ₁ , a ₁ , a ₂ , a ) senden ₂ , ..., a _n , a _n ) . (In Klammern ist der Nachweis der Härte von ED über die Topologie sehr interessant.)

Ich denke, dass es ein Omega (n ² ) für das ursprüngliche Problem geben sollte, wenn Sie nur Gleichheitstests zulassen. Meine Intuition lautet: Betrachten Sie ein Diagramm, in dem Sie nach einem Test eine Kante hinzufügen, und argumentieren Sie, dass die Ausgabe nicht eindeutig bestimmt wird, wenn das Diagramm nicht dicht ist.

So mache ich das eigentlich für p Paar Socken ( n = 2p einzelne Socken):

• Nimm zufällig eine Socke vom Stapel.
• Für die erste Socke oder wenn alle zuvor ausgewählten Socken gepaart wurden, legen Sie die Socke einfach in den ersten "Schlitz" eines "Arrays" ungepaarter Socken vor Ihnen.
• Wenn Sie eine oder mehrere ungepaarte Socken ausgewählt haben, vergleichen Sie Ihre aktuelle Socke mit allen ungepaarten Socken im Array.
  • Es ist möglich, Socken beim Aufbau Ihres Arrays in allgemeine Klassen oder Typen (weiß / schwarz, Knöchel / Crew, Sport / Kleidung) zu unterteilen und "Drilldown" durchzuführen, um nur vergleichbare Vergleiche durchzuführen.
  • Wenn Sie eine akzeptable Übereinstimmung finden, setzen Sie beide Socken zusammen und entfernen Sie sie aus dem Array.
  • Wenn Sie dies nicht tun, stecken Sie die aktuelle Socke in den ersten offenen Steckplatz im Array.
• Wiederholen Sie mit jeder Socke.

Das schlimmste Szenario dieses Schemas ist, dass jedes Sockenpaar so unterschiedlich ist, dass es genau übereinstimmen muss und dass die ersten n / 2 Socken, die Sie auswählen, alle unterschiedlich sind. Dies ist Ihr O (n ² ) -Szenario und äußerst unwahrscheinlich. Wenn die Anzahl der eindeutigen Sockentypen t geringer ist als die Anzahl der Paare p = n / 2 und die Socken in jedem Typ gleich genug sind (normalerweise in Bezug auf den Verschleiß), kann jede Socke dieses Typs mit jeder gepaart werden andere, dann, wie ich oben gefolgert habe, ist die maximale Anzahl von Socken, mit denen Sie jemals vergleichen müssen, t , wonach die nächste, die Sie ziehen, wirdpassen Sie zu einer der ungepaarten Socken. Dieses Szenario ist in der durchschnittlichen Sockenschublade viel wahrscheinlicher als im schlimmsten Fall und reduziert die Komplexität im schlimmsten Fall auf O (n * t), wobei normalerweise t << n ist .

Realer Ansatz:

Entfernen Sie so schnell wie möglich die Socken einzeln vom unsortierten Stapel und legen Sie sie in Stapel vor sich. Die Stapel sollten etwas platzsparend angeordnet sein, wobei alle Socken in die gleiche Richtung zeigen. Die Anzahl der Stapel ist durch die Entfernung begrenzt, die Sie leicht erreichen können. Die Auswahl eines Stapels, auf den eine Socke gelegt werden soll, sollte - so schnell wie möglich - erfolgen, indem eine Socke auf einen Stapel scheinbar ähnlicher Socken gelegt wird. Der gelegentliche Fehler vom Typ I (eine Socke auf einen Stapel legen, zu dem er nicht gehört) oder vom Typ II (eine Socke in einen eigenen Stapel legen, wenn ein Stapel ähnlicher Socken vorhanden ist) kann toleriert werden - die wichtigste Überlegung ist die Geschwindigkeit .

Sobald sich alle Socken in Stapeln befinden, gehen Sie schnell durch die Stapel mit mehreren Socken, bilden Paare und entfernen sie (diese gehen in Richtung Schublade). Wenn sich nicht passende Socken auf dem Stapel befinden, stapeln Sie sie wieder auf den besten Stapel (innerhalb der möglichst schnellen Beschränkung). Wenn alle Stapel mit mehreren Socken verarbeitet wurden, stimmen Sie die verbleibenden paarweisen Socken ab, die aufgrund von Typ-II-Fehlern nicht gepaart wurden. Wusch, du bist fertig - und ich habe viele Socken und wasche sie erst, wenn ein großer Teil schmutzig ist. Noch ein praktischer Hinweis: Ich klappe die Oberseite eines Paares Socken über das andere und nutze dabei ihre elastischen Eigenschaften, damit sie beim Transport zur Schublade und in der Schublade zusammen bleiben.

Aus Ihrer Frage geht hervor, dass Sie nicht viel Erfahrung mit Wäsche haben :). Sie benötigen einen Algorithmus, der mit einer kleinen Anzahl nicht paarbarer Socken gut funktioniert.

Die bisherigen Antworten nutzen unsere Funktionen zur Erkennung menschlicher Muster nicht gut aus. Das Spiel Set bietet einen Hinweis darauf, wie man das gut macht: Legen Sie alle Socken in einen zweidimensionalen Raum, damit Sie sie gut erkennen und leicht mit Ihren Händen erreichen können. Dies beschränkt Sie auf eine Fläche von ca. 120 * 80 cm. Wählen Sie dort die Paare aus, die Sie erkennen, und entfernen Sie sie. Legen Sie zusätzliche Socken in den freien Raum und wiederholen Sie. Wenn Sie sich für Personen mit leicht erkennbaren Socken waschen (kleine Kinder kommen in den Sinn), können Sie eine Radix-Sortierung durchführen, indem Sie zuerst diese Socken auswählen. Dieser Algorithmus funktioniert nur dann gut, wenn die Anzahl der einzelnen Socken gering ist

Nimm eine erste Socke und lege sie auf einen Tisch. Wählen Sie jetzt eine andere Socke; Wenn es mit dem zuerst ausgewählten übereinstimmt, legen Sie es auf das erste. Wenn nicht, legen Sie es in geringem Abstand vom ersten auf den Tisch. Wählen Sie eine dritte Socke; Wenn es mit einem der beiden vorherigen übereinstimmt, legen Sie es darauf oder platzieren Sie es in geringem Abstand vom dritten. Wiederholen, bis Sie alle Socken aufgenommen haben.

Um zu sagen, wie effizient es ist, Socken von einem Stapel zu koppeln, müssen wir zuerst die Maschine definieren, da die Paarung weder durch eine Turing- noch durch eine Direktzugriffsmaschine erfolgt, die normalerweise als Grundlage für eine verwendet wird algorithmische Analyse.

Die Maschine

Die Maschine ist eine Abstraktion eines realen Elements namens Mensch. Es kann mit zwei Augen aus der Umgebung lesen. Und unser Maschinenmodell kann die Umgebung mit zwei Armen manipulieren. Logische und arithmetische Operationen werden mit unserem Gehirn berechnet (hoffentlich ;-)).

Wir müssen auch die intrinsische Laufzeit der atomaren Operationen berücksichtigen, die mit diesen Instrumenten ausgeführt werden können. Aufgrund physikalischer Einschränkungen weisen Operationen, die von einem Arm oder Auge ausgeführt werden, eine nicht konstante zeitliche Komplexität auf. Dies liegt daran, dass wir weder einen endlos großen Stapel Socken mit einem Arm bewegen können, noch ein Auge die obere Socke auf einem endlos großen Stapel Socken sehen kann.

Die mechanische Physik gibt uns jedoch auch einige Vorteile. Wir sind nicht darauf beschränkt, höchstens eine Socke mit einem Arm zu bewegen. Wir können ein paar von ihnen gleichzeitig bewegen.

Abhängig von der vorherigen Analyse sollten daher folgende Operationen in absteigender Reihenfolge verwendet werden:

• logische und arithmetische Operationen
• Umwelt liest
• Umweltveränderungen

Wir können auch die Tatsache nutzen, dass Menschen nur eine sehr begrenzte Anzahl von Socken haben. Eine Umgebungsänderung kann also alle Socken im Stapel betreffen.

Der Algorithmus

Also hier ist mein Vorschlag:

1. Verteilen Sie alle Socken im Stapel auf dem Boden.
2. Finde ein Paar, indem du dir die Socken auf dem Boden ansiehst.
3. Wiederholen Sie ab 2, bis kein Paar mehr hergestellt werden kann.
4. Wiederholen Sie von 1 bis keine Socken mehr auf dem Boden sind.

Operation 4 ist notwendig, da beim Verteilen von Socken auf dem Boden einige Socken andere verbergen können. Hier ist die Analyse des Algorithmus:

Die Analyse

Der Algorithmus endet mit hoher Wahrscheinlichkeit. Dies liegt an der Tatsache, dass man in Schritt 2 keine Sockenpaare finden kann.

Für die folgende Laufzeitanalyse der Paarung nvon Sockenpaaren nehmen wir an, dass mindestens die Hälfte der 2nSocken nach Schritt 1 nicht ausgeblendet ist. Im Durchschnitt können wir also n/2Paare finden . Dies bedeutet, dass die Schleife Schritt 4 O(log n)mal ausgeführt wird. Schritt 2 wird O(n^2)mal ausgeführt . Daraus können wir schließen:

• Der Algorithmus beinhaltet O(ln n + n)Umgebungsmodifikationen (Schritt 1 O(ln n)plus Aufnehmen jedes Paar Socken vom Boden)
• Der Algorithmus beinhaltet O(n^2)Umgebungslesungen aus Schritt 2
• Der Algorithmus beinhaltet O(n^2)logische und arithmetische Operationen zum Vergleichen einer Socke mit einer anderen in Schritt 2

Wir haben also eine Gesamtkomplexität der Laufzeit, O(r*n^2 + w*(ln n + n))wo rund wsind die Faktoren für Lese- und Schreibvorgänge in der Umgebung für eine angemessene Anzahl von Socken. Die Kosten für die logischen und arithmetischen Operationen entfallen, da wir davon ausgehen, dass eine konstante Anzahl logischer und arithmetischer Operationen erforderlich ist, um zu entscheiden, ob zwei Socken zu demselben Paar gehören. Dies ist möglicherweise nicht in jedem Szenario möglich.

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

Ich habe eine andere Lösung herausgebracht, die weder weniger Operationen noch weniger Zeitverbrauch verspricht, aber es sollte versucht werden, herauszufinden, ob sie eine ausreichend gute Heuristik ist, um bei großen Serien von Sockenpaarungen weniger Zeitverbrauch zu erzielen.

Voraussetzungen: Es gibt keine Garantie dafür, dass es die gleichen Socken gibt. Wenn sie dieselbe Farbe haben, bedeutet dies nicht, dass sie dieselbe Größe oder dasselbe Muster haben. Socken werden zufällig gemischt. Es kann eine ungerade Anzahl von Socken geben (einige fehlen, wir wissen nicht wie viele). Bereiten Sie sich darauf vor, sich eine Variable "index" zu merken, und setzen Sie sie auf 0.

Das Ergebnis enthält ein oder zwei Stapel: 1. "übereinstimmend" und 2. "fehlend"

Heuristik:

1. Finden Sie die markanteste Socke.
2. Finde seine Übereinstimmung.
3. Wenn es keine Übereinstimmung gibt, legen Sie sie auf den "fehlenden" Stapel.
4. Wiederholen Sie von 1. bis es keine markanteren Socken mehr gibt.
5. Wenn weniger als 6 Socken vorhanden sind, fahren Sie mit 11 fort.
6. Koppeln Sie blind alle Socken mit dem Nachbarn (packen Sie sie nicht ein)
7. Finde alle passenden Paare, packe sie und verschiebe die gepackten Paare auf den "passenden" Stapel. Wenn es keine neuen Übereinstimmungen gab - erhöhen Sie "Index" um 1
8. Wenn "Index" größer als 2 ist (dies kann ein Wert sein, der von der Sockenzahl abhängt, da bei einer größeren Anzahl von Socken die Wahrscheinlichkeit geringer ist, dass sie blind gekoppelt werden), gehen Sie zu 11
9. Mische den Rest
10. Gehe zu 1
11. Vergiss "Index"
12. Wähle eine Socke
13. Finde sein Paar
14. Wenn für die Socke kein Paar vorhanden ist, legen Sie sie auf den "fehlenden" Stapel
15. Wenn ein Match gefunden wurde, packe es, packe das Paar und verschiebe es auf den "passenden" Stapel
16. Wenn es noch mehr gibt, gehen die Socken auf 12
17. Wenn nur noch eine übrig ist, gehen Sie zu 14
18. Lächeln zufrieden :)

Es könnte auch eine Überprüfung auf beschädigte Socken hinzugefügt werden, als ob diese entfernt würden. Es könnte zwischen 2 und 3 und zwischen 13 und 14 eingefügt werden.

Ich freue mich auf Erfahrungen oder Korrekturen.

Wenn ich Socken sortiere, mache ich eine ungefähre Radix-Sortierung und lasse Socken in der Nähe anderer Socken des gleichen Farb- / Mustertyps fallen. Außer in dem Fall, in dem ich eine genaue Übereinstimmung an / in der Nähe des Ortes sehe, an dem ich die Socke fallen lassen werde, extrahiere ich das Paar an diesem Punkt.

Fast alle anderen Algorithmen (einschließlich der Antwort mit der höchsten Punktzahl von usr ) sortieren und entfernen dann Paare. Ich finde, dass es als Mensch besser ist, die Anzahl der Socken zu minimieren, die gleichzeitig in Betracht gezogen werden.

Ich mache das durch:

1. Eine unverwechselbare Socke auswählen (was auch immer mir zuerst im Stapel auffällt).
2. Starten einer Radix-Sortierung von diesem konzeptionellen Ort aus, indem Sie Socken aus dem Stapel ziehen, basierend auf der Ähnlichkeit mit diesem.
3. Platzieren Sie die neue Socke in der Nähe des aktuellen Stapels, wobei der Abstand davon abhängt, wie unterschiedlich sie ist. Wenn Sie feststellen, dass Sie die Socke über eine andere legen, weil sie identisch ist, bilden Sie dort das Paar und entfernen Sie sie. Dies bedeutet, dass zukünftige Vergleiche weniger Aufwand erfordern, um den richtigen Ort zu finden.

Dies nutzt die Fähigkeit des Menschen, in O (1) -Zeit Fuzzy-Matches durchzuführen, was in gewisser Weise der Erstellung einer Hash-Map auf einem Computergerät entspricht.

Wenn Sie zuerst an den markanten Socken ziehen, lassen Sie Platz, um die weniger markanten Merkmale zu "zoomen".

Nachdem Sie die Flurofarbe, die Socken mit Streifen und die drei Paar lange Socken entfernt haben, erhalten Sie möglicherweise überwiegend weiße Socken, die grob nach Abnutzung sortiert sind.

Irgendwann sind die Unterschiede zwischen den Socken so gering, dass andere Menschen den Unterschied nicht bemerken, und es sind keine weiteren Anpassungsbemühungen erforderlich.

Wenn Sie eine Socke aufheben, legen Sie sie an einen Ort. Wenn die nächste Socke, die Sie abholen, nicht zur ersten passt, legen Sie sie neben die erste. Wenn ja, gibt es ein Paar. Auf diese Weise spielt es keine Rolle, wie viele Kombinationen es gibt, und es gibt nur zwei Möglichkeiten für jede Socke, die Sie abholen - entweder hat es eine Übereinstimmung, die bereits in Ihrer Sockenreihe enthalten ist, oder es gibt keine, was bedeutet, dass Sie Fügen Sie es an einer Stelle im Array hinzu.

Dies bedeutet auch, dass Sie mit ziemlicher Sicherheit nie alle Ihre Socken im Array haben werden, da die Socken entfernt werden, wenn sie übereinstimmen.

Betrachten Sie eine Hash-Tabelle der Größe 'N'.

Wenn wir von einer Normalverteilung ausgehen, ist die geschätzte Anzahl von 'Einfügungen', bei denen mindestens eine Socke einem Eimer zugeordnet ist, NlogN (dh alle Eimer sind voll).

Ich hatte dies als Teil eines anderen Puzzles abgeleitet, würde mich aber freuen, wenn ich mich als falsch erweisen würde. Hier ist mein Blog-Artikel dazu

Lassen Sie 'N' einer ungefähren Obergrenze für die Anzahl der eindeutigen Farben / Muster der Socken entsprechen, die Sie haben.

Sobald Sie eine Kollision haben (auch bekannt als: ein Streichholz), ziehen Sie einfach dieses Paar Socken aus. Wiederholen Sie das gleiche Experiment mit der nächsten Charge von NlogN-Socken. Das Schöne daran ist, dass Sie aufgrund der Funktionsweise des menschlichen Geistes NlogN-Parallelvergleiche (Kollisionsauflösung) durchführen können. :-)

Socken, ob echte oder eine analoge Datenstruktur, würden paarweise geliefert.

Die einfachste Antwort ist, bevor das Paar getrennt werden kann, sollte eine einzelne Datenstruktur für das Paar initialisiert worden sein, die einen Zeiger auf die linke und rechte Socke enthält, sodass Socken direkt oder über ihr Paar referenziert werden können. Eine Socke kann auch erweitert werden, um einen Zeiger auf ihren Partner zu enthalten.

Dies löst jedes Problem der rechnerischen Paarung, indem es mit einer Abstraktionsebene entfernt wird.

Wenn Sie dieselbe Idee auf das praktische Problem der Paarung von Socken anwenden, lautet die offensichtliche Antwort: Lassen Sie nicht zu, dass Ihre Socken jemals ungepaart werden. Socken werden als Paar geliefert, als Paar in die Schublade gelegt (möglicherweise durch Zusammenballen) und als Paar getragen. Der Punkt, an dem eine Entkopplung möglich ist, befindet sich in der Waschmaschine. Alles, was erforderlich ist, ist ein physikalischer Mechanismus, der es den Socken ermöglicht, zusammen zu bleiben und effizient gewaschen zu werden.

Es gibt zwei physikalische Möglichkeiten:

Für ein 'Paar'-Objekt, das einen Zeiger auf jede Socke hält, könnten wir einen Stoffbeutel haben, mit dem wir die Socken zusammenhalten. Dies scheint ein massiver Overhead zu sein.

Aber damit jede Socke einen Bezug zur anderen hat, gibt es eine gute Lösung: einen Popper (oder einen Schnappknopf, wenn Sie Amerikaner sind), wie diese:

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

Dann schnappen Sie Ihre Socken nur noch zusammen, nachdem Sie sie ausgezogen und in Ihren Wäschekorb gelegt haben. Wiederum haben Sie das Problem beseitigt, dass Sie Ihre Socken mit einer physischen Abstraktion des "Paar" -Konzepts kombinieren müssen.

Wenn die "Verschieben" -Operation ziemlich teuer ist und die "Vergleichen" -Operation billig ist und Sie den gesamten Satz trotzdem in einen Puffer verschieben müssen, in dem die Suche viel schneller ist als im ursprünglichen Speicher ... integrieren Sie einfach die Sortierung in die obligatorische Bewegung.

Ich fand, dass die Integration des Sortierprozesses in das Aufhängen zum Trocknen ein Kinderspiel ist. Ich muss sowieso jede Socke aufheben und sie aufhängen (bewegen) und es kostet mich ungefähr nichts, sie an einer bestimmten Stelle an den Saiten aufzuhängen. Um die Suche nicht nach dem gesamten Puffer (den Zeichenfolgen) zu erzwingen, platziere ich Socken nach Farbe / Farbton. Links dunkler, rechts heller, bunter vorne usw. Bevor ich jetzt jede Socke aufhänge, schaue ich in ihre "rechte Umgebung", ob bereits eine passende vorhanden ist - dies beschränkt den "Scan" auf 2-3 andere Socken - und wenn ja Ich hänge den anderen direkt daneben. Dann rolle ich sie paarweise, während ich sie trocken von den Saiten entferne.

Nun scheint dies nicht allzu verschieden zu sein von "Bilden von Stapeln nach Farbe", wie es in den Top-Antworten vorgeschlagen wird, aber zuerst habe ich kein Problem damit, zu klassifizieren, ob "lila" zu "rotem" oder "blauem" Stapel wird, indem ich keine diskreten Stapel, sondern Bereiche auswähle. es geht einfach dazwischen. Durch die Integration von zwei Vorgängen (zum Trocknen und Sortieren aufhängen) beträgt der Aufwand für das Sortieren beim Aufhängen etwa 10% des separaten Sortieraufwands.

Ich habe gerade meine Socken gepaart und festgestellt, dass der beste Weg, dies zu tun, der folgende ist:

• Wählen Sie eine der Socken und legen Sie sie weg (erstellen Sie einen "Eimer" für dieses Paar)
• Wenn das nächste das Paar des vorherigen ist, legen Sie es in den vorhandenen Bucket, andernfalls erstellen Sie einen neuen.

Im schlimmsten Fall bedeutet dies, dass Sie n / 2 verschiedene Eimer haben und Sie n-2 Bestimmungen darüber haben, welcher Eimer das Paar der aktuellen Socke enthält. Offensichtlich funktioniert dieser Algorithmus gut, wenn Sie nur wenige Paare haben. Ich habe es mit 12 Paaren gemacht.

Es ist nicht so wissenschaftlich, aber es funktioniert gut :)

Meine Lösung entspricht nicht genau Ihren Anforderungen, wie es formal erforderlich ist O(n) "zusätzlichen" Speicherplatz benötigt. In Anbetracht meiner Bedingungen ist es jedoch in meiner praktischen Anwendung sehr effizient. Daher denke ich, dass es interessant sein sollte.

Mit anderer Aufgabe kombinieren

Die besondere Bedingung in meinem Fall ist, dass ich keine Trocknungsmaschine benutze, sondern meine Tücher einfach an einen normalen Wäschetrockner hänge. Das Aufhängen von Tüchern erfordert O(n)Operationen (ich denke übrigens immer an das Verpacken von Behältern hier das Problem der ), und das Problem erfordert naturgemäß den linearen "zusätzlichen" Raum. Wenn ich eine neue Socke aus dem Eimer nehme, versuche ich, sie neben das Paar zu hängen, wenn das Paar bereits aufgehängt ist. Wenn es eine Socke von einem neuen Paar ist, lasse ich etwas Platz daneben.

Oracle Machine ist besser ;-)

Es erfordert offensichtlich einige zusätzliche Arbeit, um zu überprüfen, ob die passende Socke bereits irgendwo hängt, und es würde eine Lösung O(n^2)mit einem Koeffizienten 1/2für einen Computer ergeben. Aber in diesem Fall ist der "menschliche Faktor" tatsächlich ein Vorteil - ich kann O(1)die passende Socke normalerweise sehr schnell (fast ) identifizieren, wenn sie bereits aufgehängt war (wahrscheinlich handelt es sich um ein nicht wahrnehmbares Caching im Gehirn) - betrachten Sie es als eine Art begrenztes "Orakel" wie bei Oracle Machine ;-) Wir, die Menschen, haben diese Vorteile in einigen Fällen gegenüber digitalen Maschinen ;-)

Habe es fast O(n)!

Wenn ich also das Problem des Paarens von Socken mit dem Problem des Aufhängens von Tüchern verbinde, bekomme ich O(n)"zusätzlichen Platz" kostenlos und habe eine Lösung, die ungefähr O(n)rechtzeitig ist, nur ein wenig mehr Arbeit erfordert als einfache Hängetücher und den sofortigen Zugriff auf ein komplettes Paar Stoff ermöglicht Socken auch an einem sehr schlechten Montagmorgen ... ;-)

Ich hoffe, ich kann etwas Neues zu diesem Problem beitragen. Mir ist aufgefallen, dass alle Antworten die Tatsache vernachlässigen, dass es zwei Punkte gibt, an denen Sie eine Vorverarbeitung durchführen können , ohne Ihre gesamte Wäscheleistung zu beeinträchtigen.

Auch für große Familien müssen wir keine große Anzahl von Socken annehmen. Socken werden aus der Schublade genommen und getragen, und dann werden sie an einen Ort (vielleicht einen Mülleimer) geworfen, an dem sie bleiben, bevor sie gewaschen werden. Obwohl ich besagten Behälter nicht als LIFO-Stapel bezeichnen würde, würde ich sagen, dass es sicher ist, dies anzunehmen

1. Leute werfen beide Socken ungefähr in den gleichen Bereich der Tonne,
2. Der Bin ist zu keinem Zeitpunkt randomisiert und daher
3. Jede Teilmenge, die oben in diesem Fach entnommen wird, enthält im Allgemeinen beide Socken eines Paares.

Da alle mir bekannten Waschmaschinen eine begrenzte Größe haben (unabhängig davon, wie viele Socken Sie waschen müssen) und die eigentliche Randomisierung in der Waschmaschine erfolgt, haben wir immer kleine Untergruppen, die fast keine enthalten Singletons.

Unsere beiden Vorverarbeitungsschritte sind "die Socken auf die Wäscheleine legen" und "die Socken von der Wäscheleine nehmen", was wir tun müssen, um Socken zu erhalten, die nicht nur sauber, sondern auch trocken sind. Wie bei Waschmaschinen sind Wäscheleinen endlich, und ich gehe davon aus, dass wir den gesamten Teil der Linie haben, in dem wir unsere Socken in Sichtweite bringen.

Hier ist der Algorithmus für 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 
 }
}

Verschwenden Sie nicht Ihre Zeit damit, Socken zu bewegen oder nach der besten Übereinstimmung zu suchen. Dies alles sollte in O (n) erfolgen, was wir auch benötigen würden, um sie einfach unsortiert auf die Linie zu bringen. Die Socken sind noch nicht gepaart, wir haben nur einige Ähnlichkeitscluster auf der Linie. Es ist hilfreich, dass wir hier nur eine begrenzte Anzahl von Socken haben, da dies uns hilft, "gute" Cluster zu erstellen (wenn sich beispielsweise nur schwarze Socken in der Gruppe der Socken befinden, ist das Clustering nach Farben nicht der richtige Weg).

Hier ist der Algorithmus für 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
 }

Ich sollte darauf hinweisen, dass es zur Verbesserung der Geschwindigkeit der verbleibenden Schritte ratsam ist, nicht zufällig die nächste Socke auszuwählen, sondern Socken nach Socken nacheinander aus jedem Cluster zu entnehmen. Beide Vorverarbeitungsschritte nehmen nicht mehr Zeit in Anspruch, als nur die Socken auf die Leine oder in den Korb zu legen, was wir auf jeden Fall tun müssen. Dies sollte die Wäscheleistung erheblich verbessern.

Danach ist es einfach, den Hash-Partitionierungsalgorithmus auszuführen. Normalerweise sind ungefähr 75% der Socken bereits gepaart, so dass ich eine sehr kleine Untergruppe von Socken habe, und diese Untergruppe ist bereits (etwas) gruppiert (ich füge nach den Vorverarbeitungsschritten nicht viel Entropie in meinen Korb ein). Eine andere Sache ist, dass die verbleibenden Cluster in der Regel klein genug sind, um sofort verarbeitet zu werden, sodass es möglich ist, einen ganzen Cluster aus dem Warenkorb zu nehmen.

Hier ist der Algorithmus für sort_remaining_clusters ():

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

Danach sind nur noch wenige Socken übrig. Hier füge ich zuvor ungepaarte Socken in das System ein und verarbeite die verbleibenden Socken ohne speziellen Algorithmus - die verbleibenden Socken sind sehr wenige und können visuell sehr schnell verarbeitet werden.

Für alle verbleibenden Socken gehe ich davon aus, dass ihre Gegenstücke noch ungewaschen sind, und lege sie für die nächste Iteration weg. Wenn Sie im Laufe der Zeit ein Wachstum von ungepaarten Socken feststellen (ein "Sockenleck"), sollten Sie Ihren Behälter überprüfen - er könnte zufällig werden (haben Sie Katzen, die dort schlafen?)

Ich weiß, dass diese Algorithmen viele Annahmen treffen: einen Behälter, der als eine Art LIFO-Stapel fungiert, eine begrenzte, normale Waschmaschine und eine begrenzte, normale Wäscheleine - aber dies funktioniert immer noch mit einer sehr großen Anzahl von Socken.

Informationen zur Parallelität: Solange Sie beide Socken in denselben Behälter werfen, können Sie alle diese Schritte problemlos parallelisieren.

Ich habe einfache Schritte unternommen, um meinen Aufwand auf einen Prozess zu reduzieren, der O (1) Zeit benötigt.

Indem ich meine Eingaben auf eine von zwei Arten von Socken reduziere (weiße Socken zur Erholung, schwarze Socken für die Arbeit), muss ich nur feststellen, welche von zwei Socken ich in der Hand habe. (Technisch gesehen habe ich den Prozess auf O (0) reduziert, da sie nie zusammen gewaschen werden.)

Es sind einige Vorarbeiten erforderlich, um die gewünschten Socken zu finden und in ausreichender Menge zu kaufen, damit Ihre vorhandenen Socken nicht mehr benötigt werden. Da ich dies getan hatte, bevor ich schwarze Socken brauchte, war mein Aufwand minimal, aber die Laufleistung kann variieren.

Eine solche Vorabanstrengung wurde schon oft in sehr populärem und effektivem Code gesehen. Beispiele sind # DEFINE'ing pi auf mehrere Dezimalstellen (es gibt andere Beispiele, aber das ist das, was mir gerade in den Sinn kommt).

Erstellen Sie eine Hash-Tabelle, die für nicht übereinstimmende Socken verwendet wird, wobei Sie das Muster als Hash verwenden. Iterieren Sie nacheinander über die Socken. Wenn die Socke eine Musterübereinstimmung in der Hash-Tabelle hat, nehmen Sie die Socke aus der Tabelle und machen Sie ein Paar. Wenn die Socke keine Übereinstimmung hat, legen Sie sie in den Tisch.

Das Problem beim Sortieren Ihrer n Paar Socken ist O (n) . Bevor Sie sie in der Wäsche werfen Korb , fädeln Sie die linke nach rechts ein. Beim Herausnehmen schneiden Sie den Faden ab und legen jedes Paar in Ihre Schublade - 2 Operationen an n Paaren, also O (n).

Jetzt ist die nächste Frage einfach, ob Sie Ihre eigene Wäsche machen und Ihre Frau ihre. Das ist ein Problem, das wahrscheinlich in einem ganz anderen Bereich von Problemen auftritt . :) :)