python - 从本地排序中查找全局排序

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']