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?Ordinamento di un poset?
risposta
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.
Grazie per il link! Questo sembra molto promettente! – templatetypedef
Vorrei iniziare con lo scambio di selezione. Quello è O (n^2) e non penso che farai di meglio.
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
Non è solo questo genere topologico? –
@ jleedev- Potresti farlo con un ordinamento topologico solo se sapessi come ogni coppia di elementi in S è paragonata l'una all'altra a priori; altrimenti dovresti passare O (| S |^2) tempo facendo tutti i confronti. – templatetypedef