Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
279 views
in Technique[技术] by (71.8m points)

python - 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.

For example:

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)    

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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))

Final value hold by new_list will be:

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

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...