How to order tuples by matching the first and last values of each "(a, b), (b, c), (c, d)"

Question

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.

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

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

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.

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

Answer 1

Using an adjacency matrix seems to be a solution to your problem:

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