部分订单排序？ [英] Partial order sorting?

问题描述

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

Say, we have some items, and each defines some partial sorting rules, like this:

我是 A ，我想成为 B

我是 C ，我想在 A 之后但在 D 之前p>

I'm C and I want to be after A but before D

因此我们有 A，B，C，D 项，其规则如下：

So we have items A,B,C,D with these rules:

• A> B


• C< A ， C> D


• 没什么！因此， B 和 D 在排序时没有首选项，并且被认为是相等的。

• A>B
• C<A, C>D
• nothing else! So, B and D have no 'preferences' in ordering and are considered equal.

如您所见，传递关系规则在这里不起作用。但是，如果 A> B 仍表示 B< A 。因此，可能会有多种排序结果：

As you see, transitive relation rules are not working here. However, if A>B it still means that B<A. So, there can be multiple possible results of sorting:

1. ABCD


2. ACDB


3. ACBD


4. ABCD

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

如何实现排序算法

原因：存在多个可加载模块，其中一些模块依赖其他方式。每个模块都可以声明相对于其他模块的简单规则：

The reason: there're multiple loadable modules, and some of them 'depend' on others in a way. Each module can declare simple rules, relative to other modules:

在模块A之前加载我

Load me before module A

在模块B之后加载我

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

Load me before module A but after module B

现在我需要以某种方式实现此排序。：）

now I need to implement this ordering somehow.. :)

答案：代码作者：帕迪·麦卡锡（MIT）

Answer: code by Paddy McCarthy (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/ }}}

推荐答案

您将要构建依赖图（这只是有向图的一种），然后按照按拓扑排序排序。自从我参加组合类课程以来已经有一段时间了，因此Wikipedia文章可能比我的拓扑排序算法更有用。我希望给您适当的术语会有所帮助。 ：）

You'll want to construct a dependency graph (which is just a flavor of directed graph), and then follow a topologically sorted ordering. It's been a while since I took a combinatorics class, so the Wikipedia article will probably be more helpful than I am for a topological sort algorithm. I'm hoping giving you the proper terminology is helpful. :)

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

As far as constructing the graph, you'll basically just need to have each module with a list of that module's dependencies.

您只需要稍微改写一下规则即可……我是C，我想成为A之后但D之前，表示为 C取决于A以及 D取决于C，因此所有内容都沿标准方向流动。

You'll just need to rephrase your rules a bit... "I'm C and I want to be after A but before D" would be expressed as "C depends on A" as well as "D depends on C", such that everything is flowing in a standard direction.

这篇关于部分订单排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！