How to order list of integer tuples based on linking first and last values of each

I have a list of tuples containing a pair of integers. I want to order them so that each tuple is ordered relative to the tuple before and after it having the same corresponding value. The first number in the tuple is the second number in the tuple before it and the second number in the tuple is the first number in the tuple after it.

For example the following list

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

should be ordered

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

Edit: All input lists of tuples have exactly one possible ordering. There are no duplicate tuples and no value will ever show up more than once.

I have tried a few options but the most promising one so far has a big flaw which is illustrated below using a larger list of tuples.

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

sorted_result = pairs.copy()

for pair in correct_pairs:

    pair_to_insert = sorted_result.pop(sorted_result.index(pair))
    
    for index, comparison_pair in enumerate(sorted_result):
        
        # if last number of the tuple to insert matches the first number of the compared tuple insert the tuple before
        if pair_to_insert[1] == comparison_pair[0]:
            sorted_result.insert(index, pair_to_insert)
            break
            
        # if the first number of the tuple to insert matches the last number of the compared tuple insert the tuple after
        if  pair_to_insert[0] == comparison_pair[1]:
            sorted_result.insert(index+1, pair_to_insert)
            break

print(sorted_result)

output:

[(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)]

The sorted result contains chains of ordered tuples that are themselves out of order.

I think the approach I'm taking is flawed because any element that isn't first or last in the ordering can always be inserted before or after two respective elements and it depends on which of these shows up first as to where it gets inserted. ..If that makes sense.

Any ideas to solve this? Is there a simpler way to do this using inbuilt functions?



Read more here: https://stackoverflow.com/questions/64960368/how-to-order-list-of-integer-tuples-based-on-linking-first-and-last-values-of-ea

Content Attribution

This content was originally published by Danoram at Recent Questions - Stack Overflow, and is syndicated here via their RSS feed. You can read the original post over there.

%d bloggers like this: