Sortieren einer Pose?

Question

Es gibt eine große Anzahl von dort Sortieralgorithmen, aber die meisten von ihnen nur völlig geordnete Mengen an arbeiten, weil sie davon ausgehen, dass zwei beliebige Elemente vergleichbar sind. Gibt es jedoch gute Algorithmen für das Sortieren von Posets, bei denen einige Elemente nicht vergleichbar sind? Das heißt, da eine Menge S von Elementen aus einer poset gezogen, was ist der beste Weg, eine Ordnung x , bis der Ausgang x , ..., x _n so dass, wenn x _i ≤ x _j, i ≤ j?

Answer 1

Es gibt ein Papier mit dem Titel Sorting and Selection in Posets, das auf arxiv.org verfügbar ist. Es behandelt Sortiermethoden der Ordnung O ((w^2) nlog (n/w)), wobei w die "Breite" des Posets ist. Ich habe das Papier nicht gelesen, aber es scheint, als ob es deckt, was Sie suchen.

Answer 2

Ich würde mit Auswahl-Austausch-Sortierung beginnen. Das ist O (n^2) und ich denke nicht, dass du es besser machst.

Answer 3

Topological sort 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 helpful video example. Die meisten Unix-ähnlichen 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