部分订单排序？

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上“，这样一切都在标准方向流动。