前端之家

  1. 首页
  2. 问答

使用cmp_to_key的Python排序不会交换某些项目

• 问答

我的程序收到一个列表，该列表要使用以dict形式传递的“直接依赖项”进行排序。一个必须出现在它所依赖的其他项目之后。

当比较项相互依赖时，我使用functools.cmp_to_key返回1或-1，而当相互之间不相关时，则返回0：

这是我的MCVE：

依赖项定义：

def dependencies():
    return { "B" : ["A"],"C" : ["B","A"],"D" : ["C","B"] }

比较功能：

def dependency_cmp(module_left,module_right):
    if module_right in dependencies() and module_left in dependencies()[module_right]:
        print( module_right + " needs " + module_left )
        return -1
    elif module_left in dependencies() and module_right in dependencies()[module_left]:
        print( module_left + " needs " + module_right )
        return 1
    else:
        print( module_left + " and " + module_right + " are independent" )
        return 0

排序功能：

def doSort( the_list ):
    original = the_list[:]
    the_list.sort(key=cmp_to_key(lambda left,right: dependency_cmp(left,right)))
    print( "Dependencies [" + ",".join(original) + "] sorted to [" + ",".join(the_list) + "]" )

然后，当我打电话时：

doSort( ["C","D","B","A"] )
doSort( ["B","E","A"] )

它输出：

D needs C
D needs B
D needs B
C needs B
C needs A
B needs A
Dependencies [C,D,B,A] sorted to [A,C,D]

这是正确的，但是：

E and B are independent
A and E are independent
Dependencies [B,E,A] sorted to [B,A]

这是不正确的，我希望输出为[A,E]或[E,A,B]或[A,B]，因为B需要A和E不需要任何...

但是由于B，E和E，A的顺序是正确的，所以排序功能不会将B与A进行比较。这很有道理，但这绝对不是我想要的。该问题很可能是由于return 0造成的。我熟悉C ++，其中sort函数返回布尔值而不是整数...

正确排序这些列表的最佳策略是什么？

vancehgame 回答：使用cmp_to_key的Python排序不会交换某些项目

感谢Aran-Fey的评论，并使用Python: sorting a dependency list中的拓扑排序代码：

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

然后：

def doSort( the_list ):
    original = the_list[:]

    source = []
    for item in the_list:
        source.append( [ item,set( dependencies()[item] ) if item in dependencies() else set() ] )

    the_list = [x for x in topological_sort( source )]

    print( "Dependencies [" + ",".join(original) + "] sorted to [" + ",".join(the_list) + "]" )

最后我们得到了预期的输出：

Dependencies [C,D,B,A] sorted to [A,C,D]
Dependencies [B,E,A] sorted to [E,A,B]
sorting
本文链接：https://www.f2er.com/3159929.html

大家都在问