Python：对依赖项列表进行排序

小编典典

Python：对依赖项列表进行排序

python

我正在尝试使用内置的sorted（）函数解决我的问题，或者如果我需要自己解决问题-使用cmp的老派会比较容易。

我的数据集如下所示：

x = [
（“业务”，设置（“车队”，“地址”））
（“设备”，设置（“业务”，“模型”，“状态”，“包装”））
（'txn'，Set（'device'，'business'，'operator'））
....

排序规则基本上应该适用于N和Y的所有值，其中Y> N，x [N] [0]不在x [Y] [1]中

尽管我使用的Python 2.6中的cmp参数仍然可用，但我正在尝试使此Python 3安全。

那么，可以使用一些lambda魔术和key参数来完成此操作吗？

-==更新==-

感谢Eli＆Winston！我真的不认为使用钥匙会行得通，或者我是否怀疑这不是理想的鞋拔解决方案。

因为我的问题是关于数据库表的依赖关系，所以我不得不对Eli的代码进行少量补充，以从其依赖关系列表中删除一项（在一个精心设计的数据库中，这不会发生，但是谁住在这个神奇的完美世界中？）

我的解决方案：

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

阅读 214

2020-12-20

共1个答案

小编典典

您想要的就是所谓的拓扑排序。尽管可以使用内建函数实现sort()，但是这很尴尬，最好直接在python中实现拓扑排序。

为什么会很尴尬？如果您在Wiki页面上研究这两种算法，它们都依赖于运行中的一组“标记节点”，很难sort()使用这种概念来扭曲形式，因为key=xxx（甚至cmp=xxx）最适合与无状态比较函数一起使用，尤其是因为timsort不保证该元素将被检查的顺序。我（美丽的）肯定，任何解决方案
确实使用sort()将要结束了冗余计算每个呼叫键/ 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，如在本蟒错误跟踪概述消息。

2020-12-20