部分訂單排序？

Question

說，我們有一些項目，每個定義了一些局部的排序規則是這樣的：

我A，我想我C前B

，我想成爲A之後，但在D

因此，我們必須與這些規則的項目A,B,C,D：

• A>B
• C<A，C>D
• 沒有別的！因此，B和D在排序中沒有「偏好」，並且被認爲是相等的。

如您所見，傳遞關係規則在這裏不起作用。但是，如果A>B仍然表示B<A。因此，可以有排序的多種可能的結果：

1. A B C d
2. A C d乙
3. A C B d
4. A B C d

我如何能實現排序算法來處理這種情況呢？

---

原因：有多個可加載的模塊，其中一些以某種方式「依賴於」他人。每個模塊都可以聲明簡單的規則，相對於其它模塊：

裝入箱模塊之前甲

模塊B後裝入箱

模塊A之前，但模塊B後裝入箱

現在我需要以某種方式實現這個順序.. :)

---

答：code由帕迪·麥卡錫（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

你要構建一個dependency graph（這僅僅是一個向圖的味道），然後按照一個topologically sorted排序。自從我選了一個combinatorics類以來，這已經有一段時間了，所以維基百科的文章可能比我更喜歡拓撲排序算法。我希望給你適當的術語是有幫助的。 :)

就構建圖形而言，基本上只需要讓每個模塊都具有該模塊依賴關係的列表。

你只需要重新修改一下你的規則......「我是C，我想在A之後但在D之前」將被表達爲「C取決於A」以及「D取決於在C上「，這樣一切都在標準方向流動。