Ordinamento parziale dell'ordine?

Question

Dire, abbiamo alcuni elementi, e ciascuno definisce alcune regole di ordinamento parziali, in questo modo:

Sono A e voglio essere prima B

Sono C e voglio essere dopo A ma prima D

Così abbiamo elementi A,B,C,D con queste regole:

• A>B
• C<A, C>D
• nient'altro! Quindi, B e D non hanno 'preferenze' nell'ordinare e sono considerati uguali.

Come vedete, le regole di relazione transitiva non funzionano qui. Tuttavia, se A>B significa ancora che B<A. Quindi, ci possono essere molteplici possibili risultati di smistamento:

1. A B C D
2. A C D B
3. A C B D
4. A B C D

Come posso implementare un algoritmo di ordinamento che gestisce una situazione del genere?

---

Il motivo: ci sei più moduli caricabili, e alcuni di loro 'dipendono' su altri in un modo. Ciascun modulo può dichiarare semplici regole, rispetto ad altri moduli:

me carico prima di modulo A

mi carico dopo modulo B

me carico prima di modulo A ma dopo il modulo B

ora ho bisogno di implementare questo ordinamento in qualche modo .. :)

---

Risposta: code da Paddy McCarthy (MIT)

## {{{ http://code.activestate.com/recipes/577413/ (r1) 
try: 
    from functools import reduce 
except: 
    pass 

data = { 
    'des_system_lib': set('std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee'.split()), 
    'dw01':    set('ieee dw01 dware gtech'.split()), 
    'dw02':    set('ieee dw02 dware'.split()), 
    'dw03':    set('std synopsys dware dw03 dw02 dw01 ieee gtech'.split()), 
    'dw04':    set('dw04 ieee dw01 dware gtech'.split()), 
    'dw05':    set('dw05 ieee dware'.split()), 
    'dw06':    set('dw06 ieee dware'.split()), 
    'dw07':    set('ieee dware'.split()), 
    'dware':   set('ieee dware'.split()), 
    'gtech':   set('ieee gtech'.split()), 
    'ramlib':   set('std ieee'.split()), 
    'std_cell_lib':  set('ieee std_cell_lib'.split()), 
    'synopsys':   set(), 
    } 

def toposort2(data): 
    for k, v in data.items(): 
     v.discard(k) # Ignore self dependencies 
    extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys()) 
    data.update({item:set() for item in extra_items_in_deps}) 
    while True: 
     ordered = set(item for item,dep in data.items() if not dep) 
     if not ordered: 
      break 
     yield ' '.join(sorted(ordered)) 
     data = {item: (dep - ordered) for item,dep in data.items() 
       if item not in ordered} 
    assert not data, "A cyclic dependency exists amongst %r" % data 

print ('\n'.join(toposort2(data))) 
## end of http://code.activestate.com/recipes/577413/ }}} 

Answer 1

Avrai voglia di costruire un dependency graph (che è solo un sapore di grafo orientato), quindi seguire un ordinamento topologically sorted. È passato un po 'di tempo da quando ho preso una lezione di combinatoria, quindi l'articolo di Wikipedia sarà probabilmente più utile di me per un algoritmo di ordinamento topologico. Spero di darti la terminologia corretta è utile. :)

Per quanto riguarda la costruzione del grafico, basterà semplicemente avere ciascun modulo con un elenco delle dipendenze di quel modulo.

Avrai solo bisogno di riformulare le tue regole un po '... "Io sono C e voglio essere dopo A ma prima D" sarebbe espresso come "C dipende da A" e "D dipende" su C ", tale che tutto scorre in una direzione standard.