按连续顺序对元组列表进行排序 [英] Sort a list of tuples in consecutive order
问题描述
我想按连续的顺序对元组列表进行排序,因此每个元组的第一个元素都等于前一个的最后一个元素.
I want to sort a list of tuples in a consecutive order, so the first element of each tuple is equal to the last element of the previous one.
例如:
input = [(10, 7), (4, 9), (13, 4), (7, 13), (9, 10)]
output = [(10, 7), (7, 13), (13, 4), (4, 9), (9, 10)]
我已经进行了这样的搜索:
I have developed a search like this:
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)
是否有实现这种命令的Python方式? 以及一种就地"(仅包含列表)的方法?
Is there a pythonic way to achieve such order? And a way to do it "in-place" (with only a list)?
在我的问题中,可以使用所有元组以循环方式对输入进行重新排序,因此选择第一个元素并不重要.
In my problem, the input can be reordered in a circular way using all the tuples, so it is not important the first element chosen.
推荐答案
假定list
中的元组是圆形的,则可以使用dict
在 O(n)复杂度内实现它em>为:
Assuming your tuples in the list
will be circular, you may use dict
to achieve it within complexity of O(n) as:
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)]
这篇关于按连续顺序对元组列表进行排序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!