I have a list of tuples, each having two elements. Example:

my_tuples = [('black', 'grey'), ('red', 'orange'), ('blue', 'purple'), 
             ('orange', 'yellow'), ('grey', 'white'), ('yellow', 'cream')]

I am looking for an efficient way to find all the tuples whose first values are identical to second value of another one, make a triple of them, and continue adding values in this manner until all such chains are found. In this example, it should give the following list back:

my_tuples_processed = [('black', 'grey', 'white'), ('blue', 'purple'), 
                       ('red', 'orange', 'yellow', 'cream')]

Any help on this would be appreciated.

CodePudding user response：

Using a dictionary to efficiently find the starting values and the connections, and using lists to efficiently concatenate the values (Try it online!):

my_tuples_processed = []
d = dict(my_tuples)
for x in d.keys() - d.values():
    path = [x]
    while x in d:
        path.append(x := d[x])
    my_tuples_processed.append(tuple(path))

This assumes that no value appears twice as first or twice as second value (as discussed in the question's comments).

An iterator alternative mostly because I love iterators (Try it online!):

my_tuples_processed = []
d = dict(my_tuples)
def get():
    global x
    return (x := d.get(x))
for x in d.keys() - d.values():
    path = x, *iter(get, None)
    my_tuples_processed.append(path)

CodePudding user response：

I add my own original solution before posting this question, simply for the sake of completelness. But it is not really an efficient solution and the accepted answer is much preferable.

def sort_merge_tuples(list_tuples):
    my_tuples = list_tuples.copy()
    cc1 = 0
    while cc1 < len(my_tuples):
        my_t = my_tuples[cc1]
        cc2 = 0
        while cc2 < len(my_tuples):
            my_t2 = my_tuples[cc2]
            if my_t[-1] == my_t2[0]:
                new_tuple = my_t   my_t2[1:]
                my_tuples.remove(my_t)
                my_tuples.remove(my_t2)
                my_tuples.append(new_tuple)
                cc1 = 0
                break
            elif my_t2[-1] == my_t[0]:
                new_tuple = my_t2   my_t[1:]
                my_tuples.remove(my_t)
                my_tuples.remove(my_t2)
                my_tuples.append(new_tuple)
                cc1 = 0
                break
            cc2 = cc2   1
        cc1 = cc1   1
    return my_tuples