Einige sortierte Listen mit unbekannter Reihenfolge zusammenführen
Ich habe einige Listen mit variabler Anzahl von Elementen. Jede Liste ist sortiert, aber der Sortieralgorithmus ist nicht bekannt. Ich möchte die Listen in eine große Liste zusammenführen, die alle Listen in der gleichen Reihenfolge ohne Duplikate enthält.
Beispieleingabe:
- XS, M, L, XL
- S, M, XXL
- XXS, XS, S, L
Erwartetes Ergebnis:
- XXS, XS, S, M, L, XL, XXL
Das erwartete Ergebnis wird erhalten, indem die Eingabesequenzen zusammengeführt werden, um ein zusammengefügtes Ergebnis zu erhalten, das die Elemente jeder Eingabefolge in der richtigen Reihenfolge enthält:
%Vor%Die Funktion sollte benachrichtigen, wenn Elemente mit mehrdeutigen Positionen vorhanden sind. Hier wäre es XXL (es könnte nach M, L oder XL bleiben) und ich muss seine Position manuell nach XL angeben (weil ich hier den Sortieralgorithmus kenne und helfen kann). Ich dachte darüber nach, Paare aus je zwei Elementen zu definieren, jedes Paar in der Reihenfolge wie in der ursprünglichen Liste. Daraus könnte man die komplette Liste aufbauen.
4 Antworten
Dies kann mit einem Algorithmus Topologische Sortierung gelöst werden.
Wenn Sie jede Ihrer Eingabesequenzen als einen Pfad durch ein gerichtetes Diagramm betrachten, ordnet eine topologische Sortierung Ihre Knotenmenge so von links nach rechts an, dass jede gerichtete Kante nach rechts zeigt.
Die Wikipedia-Seite auf Topologische Sortierung enthält diesen Algorithmus, der erstmals 1962 von Arthur Kahn beschrieben wurde:
%Vor%Dieser Algorithmus schlägt, wie geschrieben, nicht wirklich fehl, wenn er mehrdeutige Sequenzen findet, aber das ist einfach hinzuzufügen, indem man am Anfang der Schleife einen Haken setzt, wie folgt:
%Vor%Ich weiß nicht, in welcher Sprache Sie arbeiten, aber ich habe diese PHP-Implementierung als Beweis für das Konzept zusammengestellt:
%Vor%Sie können die Funktion wie folgt aufrufen:
%Vor%Um die folgende Ausgabe zu erhalten:
%Vor%Sie versuchen, teilweise geordnete Mengen oder Posets zusammenzuführen. Die mehrdeutigen Teile der Zusammenführung werden Antiketten genannt. Also, Sie wollen einen Algorithmus, der Posets zusammenfasst und Ihnen sagt, was die Antichains sind.
Hier ist ein Papier, das einen Algorithmus zum Zusammenführen von Posets und zum Erkennen von Antiketten beschreibt , sowie ein Link zur Startseite des Autors , falls Sie ihn kontaktieren möchten, um zu sehen, ob Quellcode verfügbar ist.
Folgendes würde ich tun:
- Die Listen vorverarbeiten: Ausrechnen, dass XXS kleiner als XS ist kleiner als S ist kleiner als ... XXL ist ein [Constraint-Zufriedenheitsproblem] (http://en.wikipedia.org/wiki/Constraint_satisfaction_problem). Diese Art von Problem beinhaltet die Suche nach einer korrekten Reihenfolge zwischen allen Elementen unter Berücksichtigung der in den ursprünglichen Listen definierten Einschränkungen.
- Erstellen Sie ein bidirektionales Mapping von der Menge {XXS, ..., XXL} zur Menge {1, ..., 6}, nachdem Sie Schritt 1 durchgeführt haben.
- Erstellen Sie für jede Liste eine andere Liste, indem Sie das in 2 definierte Mapping verwenden.
- Verwenden Sie eine modifizierte [merge sort] (http://en.wikipedia.org/wiki/Merge_sort), um zwei Listen zu kombinieren. Ändern Sie den Zusammenführungsalgorithmus so, dass er meldet, wenn zwei verglichene Elemente identisch sind (und eines der zusammenzuführenden Elemente ignoriert).
- Führen Sie Schritt 4 für jedes Listenpaar durch, bis es eine Liste gibt.
- Erstellen Sie mit dem in 2 definierten Mapping die Textversion der Liste.
Für das Sortieren von Teilen denke ich, dass Merge Sort gemäß Ihrer Beschreibung ausreicht. Eine Sache, die geändert werden muss, ist während der Zusammenführung, wir sollten Elemente am Eingabearray überspringen, wenn das erste Element des Eingabearrays mit dem Ergebnisarray übereinstimmt.
Wenn ich es richtig verstehe, möchten Sie eine Gesamtordnung aller möglichen Eingabeelemente erstellen. Einige Teilaufträge sind bereits in den Eingabefeldern definiert (da sie bereits sortiert sind), während andere von Benutzern angegeben werden müssen. Zum Beispiel in der Frage, order
'S' & lt; 'M' & lt; 'XXL'
'XS' & lt; 'M' & lt; 'L' & lt; 'XL'
'XXS' & lt; 'XS' & lt; 'S' & lt; 'L'
ist gut definiert. Aber der Algorithmus weiß immer noch nicht, ob 'XXL' größer oder kleiner als 'XL', 'L' ist.
Nun, da die drei Eingabearrays sortiert sind, muss eine vollständige Reihenfolge der Eingabeelemente existieren. Daher ist mein Vorschlag, Ihren Datenanbieter nach einer geordneten Liste aller möglichen Datenelemente zu fragen. Klingt dumm, aber es ist ein einfacher Weg.
Wenn diese Liste nicht verfügbar ist, besteht eine einfache Möglichkeit darin, nach einer Paarsortierung für den Benutzer zu fragen, dann zu prüfen, ob der Konflikt mit der vorhandenen Eingabesequenz besteht und sich daran erinnert, wenn der Algorithmus auf ein mehrdeutiges Paar trifft. Ich denke, Topologie Sortierung ist mächtiger als diese Anwendung. Da wir uns mit einzelnen Datenelementen befassen, muss eine Gesamtbestellung beendet werden. Während die Topologiesortierung mit der partiellen Ordnung umgehen soll.
Tags und Links algorithm merge directed-graph sortedlist poset