Ordinamento di un poset?

Question

Esiste un enorme numero di algoritmi di ordinamento, ma la maggior parte di essi funziona solo su insiemi totalmente ordinati perché presuppone che due elementi siano comparabili. Tuttavia, ci sono dei buoni algoritmi là fuori per ordinare i posets, dove alcuni elementi sono incomparabili? Cioè, dato un insieme S di elementi che parte da un poset, qual è il modo migliore per produrre un ordinamento x , x 2 , ..., x n tale che se x _i ≤ x _j, i ≤ j?

Answer 1

C'è un documento intitolato Sorting and Selection in Posets disponibile su arxiv.org che descrive i metodi di ordinamento di ordine O ((w^2) nlog (n/w)), dove w è la "larghezza" del poset. Non ho letto il documento, ma sembra che copra quello che stai cercando.

Answer 2

Vorrei iniziare con lo scambio di selezione. Quello è O (n^2) e non penso che farai di meglio.

Answer 3

Topological sort è adatto per l'ordinamento di un set parzialmente ordinato. La maggior parte degli algoritmi è O (n^2). Ecco un algoritmo da 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) 

C'è un helpful video example. La maggior parte dei sistemi Unix ha il comando tsort. Si potrebbe risolvere esempio brownie del video con tsort come segue:

$ 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