如何通过匹配每个“(a, b), (b, c), (c, d)”的第一个和最后一个值来对元组进行排序

Question

我有一个包含一对整数的元组列表。我想对它们进行排序，以便每个元组相对于其前后具有相同对应值的元组进行排序。元组中的第一个数字是它之前的元组中的第二个数字，元组中的第二个数字是它之后的元组中的第一个数字。

(a, b), (b, c), (c, d)

例如下面的列表

[(8,7),(2,8),(3,5),(11,2),(5,11)]

应该订购

[(3,5),(5,11),(11,2),(2,8),(8,7)]

元组的所有输入列表都只有一种可能的排序。没有重复的元组，也没有值会出现多次。

我尝试了几个选项，但迄今为止最有前途的一个有一个很大的缺陷，下面使用更大的元组列表进行说明。

(a, b), (b, c), (c, d)

输出

[(12, 4), (4, 8), (8, 16), (16, 32), (32, 64), (64, 128), (128, 256), (4096, 8192), (8192, 16384), (16384, 32768), (32768, 65536), (256, 512), (512, 1024), (1024, 2048), (2048, 4096), (27, 9), (9, 18), (18, 36), (36, 12)]

排序结果包含本身无序的有序元组链。

我认为我采用的方法是有缺陷的，因为任何不在排序中的第一个或最后一个元素总是可以在两个相应元素之前或之后插入，这取决于这些元素中的哪一个首先出现在它被插入的位置。

有什么想法可以解决这个问题吗？有没有更简单的方法来使用内置函数来做到这一点？

Answer 1

使用邻接矩阵似乎可以解决您的问题：

# Create an adjacency matrix to find the next value fast 
adjacency_matrix = {pair[0]: pair for pair in pairs}
# The first element can be found being the first element of the pair not 
# present in the second elements
first_key = set(pair[0] for pair in pairs).difference(pair[1] for pair in pairs)

# Simply pop the elements from the adjacency matrix
sorted_pairs = [adjacency_matrix.pop(first_key.pop())]
while adjacency_matrix:
    # sorted_pairs[-1][1] takes the second element of 
    # the last pair inserted
    sorted_pairs.append(adjacency_matrix.pop(sorted_pairs[-1][1]))

print(sorted_pairs)