部分订单排序？

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. 交流数据库
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

您将需要构造一个依赖关系图（这只是有向图的一种形式），然后遵循拓扑排序的顺序。自从我参加组合类课程以来已经有一段时间了，因此Wikipedia文章可能比拓扑分类算法更有帮助。我希望给您适当的术语会有所帮助。:)

就构造图而言，基本上您只需要使每个模块具有该模块的依赖关系列表即可。

您只需要稍微改一下规则即可…“我是C，我想在A之后但在D之前”表示为“ C取决于A”以及“ D取决于C”，这样一切都朝着标准方向流动。