根据字典中的“依赖项”对python列表进行排序

Question

假设我有以下列表foo要排序：

foo = [63,64,65]

为了通知排序，我有以下“依赖项”字典，其中如果某个值在key的列表中，则该值的排序必须高于list 中的键foo：

bar = {
    63: [64, 65],
    64: [65]
}

例如，查看 list foo，我们看到63index 处的值0。但是，检查字典bar，我们看到63具有“依赖关系” 64and 65，因此这两个值必须在foo.

我相信我可以拼凑出一些东西，但我对算法和/或其他方法来解决这种排序场景感兴趣。谢谢。

更新： 评论中的许多人指出这可能是图形/拓扑问题。谢谢你，因为这实际上是对图中节点进行排序的更大任务的一部分。

更新： 建议查看toposort，这正好符合要求。

Answer 1

所以，把所有的评论放在一起：

您的情况对应于有向图，其中每条边都是一个依赖项。对有向（非循环）图或短 DAG 进行排序的正确方法称为拓扑排序。

在 Python 中已经有一个包可以做到这一点，toposort. 但是，它要求您的值是集合，而不是列表，但这很容易修复：

from toposort import toposort_flatten

bar = {
    63: [64, 65],
    64: [65]
}

graph = dict(zip(bar.keys(), map(set, bar.values())))
sorted_graph = toposort_flatten(graph, sort=True)

由于听起来您的图表可能包含不在 中的条目foo，您可以这样排序foo：

foo = [63,64,65]
foo_set = set(foo)
foo_sorted = [x for x in sorted_graph if x in foo_set]
print(foo_sorted)
# [65, 64, 63]

或者，如果图形比您要排序的列表大很多（并且迭代它需要很多时间），请构建一个字典：

graph_sorted_lookup = {x: i for i, x in enumerate(sorted_graph)}
foo_sorted = sorted(foo, key=graph_sorted_lookup.get)