偏序排序？

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之后加载我

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

---

答案: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

您将需要构建一个依赖图(这只是一个有向图的风格),然后按照拓扑排序的顺序.自从我参加组合学课程以来已经有一段时间了,因此维基百科的文章可能比拓扑排序算法更有帮助.我希望给你合适的术语是有帮助的.:)

至于构建图形,您基本上只需要让每个模块都包含该模块的依赖项列表.

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