我正在尝试确定我的问题是否可以使用内置的 sorted() 函数解决，或者我是否需要自己解决 - 使用 cmp 的老派会相对容易。

我的数据集如下所示:

x = [
('business', Set('fleet','address'))
('device', Set('business','model','status','pack'))
('txn', Set('device','business','operator'))
....

The sort rule should be basically for all value of N & Y where Y > N, x[N][0] not in x[Y][1]

Although I'm using Python 2.6 where the cmp argument is still available I'm trying to make this Python 3 safe.

So, can this be done using some lambda magic and the key argument?

-== UPDATE ==-

Thanks Eli & Winston! I didn't really think using key would work, or if it could I suspected it would be a shoe horn solution which isn't ideal.

Because my problem was for database table dependencies I had to make a minor addition to Eli's code to remove an item from its list of dependencies (in a well designed database this wouldn't happen, but who lives in that magical perfect world?)

My Solution:

def topological_sort(source):
    """perform topo sort on elements.

    :arg source: list of ``(name, set(names of dependancies))`` pairs
    :returns: list of names, with dependancies listed first
    """
    pending = [(name, set(deps)) for name, deps in source]        
    emitted = []
    while pending:
        next_pending = []
        next_emitted = []
        for entry in pending:
            name, deps = entry
            deps.difference_update(set((name,)), emitted) # <-- pop self from dep, req Py2.6
            if deps:
                next_pending.append(entry)
            else:
                yield name
                emitted.append(name) # <-- not required, but preserves original order
                next_emitted.append(name)
        if not next_emitted:
            raise ValueError("cyclic dependancy detected: %s %r" % (name, (next_pending,)))
        pending = next_pending
        emitted = next_emitted

最佳答案

你想要的是一个topological sort .虽然可以使用内置的 sort() 来实现，但它相当笨拙，最好直接在 python 中实现拓扑排序。

为什么会很尴尬？如果你在 wiki 页面上研究这两种算法，它们都依赖于一组运行的“标记节点”，这个概念很难扭曲成 sort() 可以使用的形式，因为 key=xxx(甚至 cmp=xxx)最适用于无状态比较函数，特别是因为 timsort 不保证检查元素的顺序。我(漂亮)确保 确实 使用 sort() 的任何解决方案最终都会为每次调用 key/cmp 函数冗余地计算一些信息，以解决无状态问题.

以下是我一直在使用的算法(对一些 javascript 库依赖项进行排序):

编辑:根据 Winston Ewert 的解决方案对此进行了极大的修改

def topological_sort(source):
    """perform topo sort on elements.

    :arg source: list of ``(name, [list of dependancies])`` pairs
    :returns: list of names, with dependancies listed first
    """
    pending = [(name, set(deps)) for name, deps in source] # copy deps so we can modify set in-place       
    emitted = []        
    while pending:
        next_pending = []
        next_emitted = []
        for entry in pending:
            name, deps = entry
            deps.difference_update(emitted) # remove deps we emitted last pass
            if deps: # still has deps? recheck during next pass
                next_pending.append(entry) 
            else: # no more deps? time to emit
                yield name 
                emitted.append(name) # <-- not required, but helps preserve original ordering
                next_emitted.append(name) # remember what we emitted for difference_update() in next pass
        if not next_emitted: # all entries have unmet deps, one of two things is wrong...
            raise ValueError("cyclic or missing dependancy detected: %r" % (next_pending,))
        pending = next_pending
        emitted = next_emitted

旁注:是可以将 cmp() 函数塞进 key=xxx 中，如 python 错误跟踪器中所述message .

关于Python:对依赖列表进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11557241/