从本地订购中查找全局订购

Question

假设您有一个元组列表

[(a,d), (a,c), (b,c), (a,b), (c,d)]

元组的第二元素大于第一

假设只有一个有序列表(包含至少一个元组中显示的所有元素(与所有元组一致。在这种情况下，列表

[a,b,c,d]

我们如何找到列表？

Answer 1

在最简单的情况下，对象是定义了方法__eq__、__hash__和__lt__的类的实例。前两种方法允许使用set，而第三种方法允许您使用sorted。这里有一个例子(lst是元组的初始列表(：

sorted_elements = sorted({el for t in lst for el in t})

您可以使用前面的数字和字符解决方案(这只是一个例子(：

>>> lst = [(3,4), (7,8), (7,9), (1,3)]
>>> sorted_elements = sorted({el for t in lst for el in t})
>>> sorted_elements
[1, 3, 4, 7, 8, 9]

>>> lst = [('a','b'), ('c','e'), ('c','z')]
>>> sorted_elements = sorted({el for t in lst for el in t})
>>> sorted_elements
['a', 'b', 'c', 'e', 'z']

在更常见的情况下，您可能希望使用拓扑排序(例如，通过使用networkx包(。在这种情况下，您的对象类型为A:

import networkx as nx
G = nx.DiGraph()
G.add_edges_from(lst)
sorted_elements = list(nx.topological_sort(G))

这里有一个例子：

import networkx as nx
class A:
def __init__(self, name):
self.name = name
a, b, c, d = A('a'), A('b'), A('c'), A('d')
lst = [(a,d), (a,c), (b,c), (a,b), (c,d)]
G = nx.DiGraph()
G.add_edges_from(lst)
sorted_elements = list(nx.topological_sort(G))
print([el.name for el in sorted_elements]) # ['a', 'b', 'c', 'd']

Answer 2

感谢Jason Harper，他指出这个问题被称为拓扑排序。

模块graphlib(需要python3(执行此操作。然而，您必须获得graphlib后台端口

pip3 uninstall graphlib
pip3 install graphlib-backport

在我做这件事之前，我有一个非常旧的graphlib 版本

from graphlib import TopologicalSorter

# creating an instance of TopologicalSorter
# initial graph is optional
ts = TopologicalSorter()

ts.add('d','a')
ts.add('c','a')
ts.add('c','b')
ts.add('b','a')
ts.add('d','c')
print([*ts.static_order()])

#Output
['a', 'b', 'c', 'd']