python - 偏序排序？

Question

比如说，我们有一些项目，每个项目都定义了一些部分排序规则，如下所示:

I'm A and I want to be before B

I'm C and I want to be after A but before 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 B
3. A C B D
4. A B C D

我怎样才能实现处理这种情况的排序算法？

---

原因:有多个可加载模块，其中一些在某种程度上“依赖”其他模块。每个模块都可以声明相对于其他模块的简单规则:

Load me before module A

Load me after module B

Load me before module A but after module B

现在我需要以某种方式实现这个排序......:)

---

答案:code作者:Paddy McCarthy(麻省理工学院)

## {{{ 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订购。我上组合数学课已经有一段时间了，所以维基百科的文章可能比我对拓扑排序算法更有帮助。我希望给你正确的术语是有帮助的。 :)

就构建图表而言，您基本上只需要让每个模块都包含该模块的依赖项列表。

你只需要稍微改写你的规则......“我是 C，我想在 A 之后但在 D 之前”将表示为“C 取决于 A”以及“D 取决于C”，这样一切都在一个标准的方向上流动。