Sortieren einer poset?
-
25-09-2019 - |
Frage
Es gibt eine große Anzahl Algorithmen zum Sortieren gibt, aber die meisten von ihnen nur auf Arbeit völlig geordnete Mengen, weil sie davon ausgehen, dass zwei beliebige Elemente vergleichbar sind. Allerdings gibt es da draußen irgendwelche guten Algorithmen zum Sortieren posets, wo einige Elemente sind unvergleichbar? Das heißt, da eine Menge S von Elementen aus einer poset gezogen, was ist der beste Weg zur Ausgabe einer Ordnung x 1 x 2 , ..., x n , so dass, wenn x i ≤ x j , i ≤ j / p>
Lösung
Es gibt ein Papier mit dem Titel Sortierung und Auswahl in Posets verfügbar auf arxiv.org bespricht die Methoden der Ordnung O ((w ^ 2) nlog (n / w)), wobei w die "Breite" der poset Sortierung. Ich habe nicht die Zeitung lesen, aber es scheint, wie es bedeckt, was Sie suchen.
Andere Tipps
topologische Sortierung ist gut geeignet, um eine teilweise geordnete Menge zu sortieren. Die meisten Algorithmen sind O (n ^ 2). Hier ist ein Algorithmus aus Wikipedia:
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
add n to tail of L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
Es gibt eine hilfreich Video Beispiel . Die meisten Unix-ähnliche Systeme haben den tsort
Befehl. Sie könnten für das Video Brownie Beispiel mit tsort
lösen wie folgt:
$ cat brownies.txt
preheat bake
water mix
dry_ingredients mix
grease pour
mix pour
pour bake
$ tsort brownies.txt
grease
dry_ingredients
water
preheat
mix
pour
bake
würde ich mit Auswahl-Austausch Art starten. Das ist O (n ^ 2), und ich glaube nicht, dass Sie besser werden als das.