python - 按连续顺序对元组列表进行排序

Question

我想按连续顺序对元组列表进行排序，因此每个元组的第一个元素等于前一个元组的最后一个元素。

例如:

input = [(10, 7), (4, 9), (13, 4), (7, 13), (9, 10)]
output = [(10, 7), (7, 13), (13, 4), (4, 9), (9, 10)]

我开发了这样的搜索:

output=[]
given = [(10, 7), (4, 9), (13, 4), (7, 13), (9, 10)]
t = given[0][0]
for i in range(len(given)):
      # search tuples starting with element t
      output += [e for e in given if e[0] == t]
      t = output[-1][-1] # Get the next element to search

print(output)    

是否有 pythonic 方法来实现这样的顺序？ 以及“就地”执行此操作的方法(仅使用列表)？

在我的问题中，输入可以使用所有元组以循环方式重新排序，因此选择第一个元素并不重要。

Answer 1

假设 list 中的元组是循环的，您可以使用 dict 在 O(n) 的复杂度内实现它:

input = [(10, 7), (4, 9), (13, 4), (7, 13), (9, 10)]
input_dict = dict(input)  # Convert list of `tuples` to dict

elem = input[0][0]  # start point in the new list

new_list = []  # List of tuples for holding the values in required order

for _ in range(len(input)):
    new_list.append((elem, input_dict[elem]))
    elem = input_dict[elem]
    if elem not in input_dict:
        # Raise exception in case list of tuples is not circular
        raise Exception('key {} not found in dict'.format(elem))

new_list 持有的最终值将是:

>>> new_list
[(10, 7), (7, 13), (13, 4), (4, 9), (9, 10)]