部分订单排序？

Question

说，我们有一些项目，每个项目都定义了一些部分分类规则，例如：

我是 A 我想成为 B

我是 C 我想追随 A 但是以前 D

所以我们有项目 A,B,C,D 通过这些规则：

• A>B
• C<A, C>D
• 没有其他的！所以， B 和 D 没有秩序的“偏好”，被认为是平等的。

如您所见，在这里不起作用的传递关系规则。但是，如果 A>B 仍然意味着 B<A. 。因此，分类可能会有多个可能的结果：

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

如何实现处理这种情况的分类算法？

---

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

在模块A之前加载我

在模块B后加载我

在模块A之前加载我，但是在模块B之后

现在我需要以某种方式实施此订购.. :)

---

回答： 代码 帕迪·麦卡锡（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

您要构建一个 依赖图 （这只是定向图的味道），然后遵循 拓扑排序 订购。自从我参加Combinatorics课程以来已经有一段时间了，因此Wikipedia文章可能比我对拓扑排序算法更有帮助。我希望给您适当的术语有帮助。 :)

至于构造图形，您基本上只需要将每个模块带有该模块依赖项的列表即可。

您只需要稍微改写您的规则...“我是C，我想在A之后，但在D”之前将其表示为“ C取决于A”以及“ D依赖于C”，使一切都朝着标准方向流动。