poset

Fragen
___ qstntxt ___

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:

  1. XS, M, L, XL
  2. S, M, XXL
  3. 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.

    
___ answer17218866 ___

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.

    
___ answer17202968 ___

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%     
___ qstnhdr ___ Einige sortierte Listen mit unbekannter Reihenfolge zusammenführen ___ tag123algorithm ___ Ein Algorithmus ist eine Folge wohldefinierter Schritte, die eine abstrakte Lösung für ein Problem definieren. Verwenden Sie dieses Tag, wenn sich Ihr Problem auf den Algorithmusentwurf bezieht. ___ answer4651490 ___

Folgendes würde ich tun:

  1. 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.
  2. Erstellen Sie ein bidirektionales Mapping von der Menge {XXS, ..., XXL} zur Menge {1, ..., 6}, nachdem Sie Schritt 1 durchgeführt haben.
  3. Erstellen Sie für jede Liste eine andere Liste, indem Sie das in 2 definierte Mapping verwenden.
  4. 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).
  5. Führen Sie Schritt 4 für jedes Listenpaar durch, bis es eine Liste gibt.
  6. Erstellen Sie mit dem in 2 definierten Mapping die Textversion der Liste.
___ tag123directedgraph ___ Ein gerichteter Graph ist ein Graph, d. h. eine Menge von Objekten (als Knoten oder Knoten bezeichnet), die miteinander verbunden sind, wobei alle Kanten von einem Knoten zum anderen gerichtet sind. Ein gerichteter Graph wird manchmal als Digraph oder gerichtetes Netzwerk bezeichnet. ___ tag123merge ___ Zusammenführen ist ein allgemeiner Begriff zum Kombinieren von zwei oder mehr zusammenhängenden Datensätzen. Es wird häufig mit Revisionskontrollsystemen in Verbindung gebracht, wenn mehrere Änderungen an einer revisionsgesteuerten Sammlung von Dateien abgeglichen werden. Das Zusammenführen mehrerer Datensätze ist eine weitere Verwendung dieses Tags. ___ tag123posset ___ POSet in einer Kurzschrift für teilweise geordnete Menge, das ist ein Set mit einer partiellen Reihenfolge. ___ answer17330932 ___

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.

    
___ tag123sortedlist ___ SortedList Repräsentiert eine Sammlung von Schlüssel / Wert-Paaren, die nach Schlüsseln sortiert sind und nach Schlüssel und Index zugänglich sind. Die Kapazität eines SortedList-Objekts ist die Anzahl der Elemente, die die SortedList enthalten kann. Verwenden Sie dieses Tag für Fragen zu SortedList. ___
4
Antworten

Effizienter Algorithmus, um die maximalen Elemente einer partiell geordneten Menge zu finden

Ich habe eine teilweise geordnete Menge, sagen wir A = [x1, x2, ...] , was bedeutet, dass für jede xi und xj in der Menge (genau) eine von vier Möglichkeiten zutrifft: xi < xj , xi == xj , xi > xj , oder xi und xj sind...
04.02.2014, 18:38
4
Antworten

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 Duplika...
10.01.2011, 10:37