时间戳

首页 > 解决方案 > 在不知道它们的值的情况下对 Python 数字列表进行排序，而只知道它们之间的关系

python - 在不知道它们的值的情况下对 Python 数字列表进行排序，而只知道它们之间的关系

问题描述

我有一个数字列表，我无法真正知道它们的真实值。比方说list = [a,b,c,d]。但我有关于它们如何相互关联的信息：

a > b
b > d
d > c

因此我可以推断出按降序排序的列表是[ a, b, d, c].

另一个更复杂的例子

relationships =
 - g > b
 - d > c > a
 - d > g
 - f > e > a
 - f > e > d

在这种情况下，我们有多个可能的答案

            Result: 
  [ [f, e, d, c, a, g, b],
    [f, e, d, g, c, a, b],
    [f, e, d, g, c, b, a],
  ... ]

仅举几个

我希望该函数准确地返回我：所有可能答案的列表。关系是列表的列表，其中每个列表表示降序排序的关系。例如relationships = [[a,b],[b,c]]告诉我 "a > b" 和 "b > c" 。关系内部的内部列表不必具有相同的大小。如果输入无效/不可能，算法应该抛出错误。例如：

relationships = [[a,b],[b,c],[c,a]是不可能的情况

什么是最好的方法也是有效的？我正在考虑使用图论，其中图不能是非循环的。例如 A -> B 意味着节点 A 去 B 意味着 A > B ，因此 B -> A 不能存在。有点像二叉树，但在这种情况下，我们只能允许 1 个，而不是每个节点允许 2 个子节点。

这是一个好主意，还是有人对如何解决这个问题有更好的想法？

标签： pythonalgorithmsortingdata-structuresgraph

解决方案

你需要 3 个想法来理解这一点。

首先是通过卡恩算法进行拓扑排序。有关说明，请参阅https://en.wikipedia.org/wiki/Topological_sorting#Kahn 's_algorithm。我一路走来通过该算法生成拓扑排序，并为yield每一个排序。

第二个是基于堆栈的编程。Think Forth，或 RPN。这个想法是我有一堆动作。在每一步，我都会从todo列表中取出最重要的操作并执行它。如果我将项目添加到todo列表中，那就像进行递归调用一样。在我的情况下，操作是choose（尝试所有有意义的选择），add（将一个元素添加到排序列表并进行簿记），remove（从排序列表中删除一个元素并进行簿记）和try（安排操作添加/选择/删除 - 但放置在相反的顺序，因为堆栈）。

三是发电机。我只是yield多次，然后从我所在的地方继续。这可以循环，变成一个列表等。

这是代码。

def topological_sorts (descending_chains):
    arrive_to = {}
    outstanding_arrivals = {}
    for chain in descending_chains:
        for x in chain:
            if x not in arrive_to:
                arrive_to[x] = set([])
                outstanding_arrivals[x] = 0
        for i in range(1, len(chain)):
            arrive_to[chain[i-1]].add(chain[i])

    for item in arrive_to:
        for x in arrive_to[item]:
            outstanding_arrivals[x] += 1

    todo = [['choose', None]]
    sorted_items = []
    chosen = set([])
    items = [x for x in arrive_to]
    while len(todo):
        action, item = todo.pop()
        if action == 'choose':
            choices = []
            for x in outstanding_arrivals:
                if x not in chosen and 0 == outstanding_arrivals[x]:
                    choices.append(x)
            if 0 == len(choices):
                if len(sorted_items) == len(items):
                    yield sorted_items
                else:
                    print((choices, outstanding_arrivals, sorted_items))
                    break
            else:
                for item in choices:
                    todo.append(['try', item])
        elif action == 'try':
            chosen.add(item)
            sorted_items.append(item)
            todo.append(['remove', item])
            todo.append(['choose', None])
            todo.append(['add', item])
        elif action == 'add':
            chosen.add(item)
            for x in arrive_to[item]:
                outstanding_arrivals[x] -= 1
        elif action == 'remove':
            chosen.remove(item)
            sorted_items.pop()
            for x in arrive_to[item]:
                outstanding_arrivals[x] += 1
        else:
            yield ('todo:', action, item)

这是如何将它用于第二个示例。

for sort in topological_sorts([
        ['g', 'b'],
        ['d', 'c', 'a'],
        ['d', 'g'],
        ['f', 'e', 'a'],
        ['f', 'e', 'd']]):
    print(sort)

推荐阅读