如何将列表中连续关联的二元元组合并为更长元组？

给定一个由二元元组组成的列表：

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

需要高效找出所有首尾相连的元组，合并成更长的关联链，直到无法合并为止，预期结果为：

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

用字典构建首尾映射是最高效的处理方式，具体实现思路如下：

首先，我们需要两个字典：

• start_map：记录每个元组的首元素对应的尾元素
• end_map：记录每个元组的尾元素对应的首元素

同时收集所有出现过的元素，用来找出每条链的起点——也就是那些没有被任何元组当作尾元素的元素，因为这些元素就是一条链的开端。

然后从每个起点出发，顺着start_map一直往下找，把元素依次拼接起来，直到找不到下一个元素为止，这样就得到了完整的关联链。

代码实现如下：

def merge_tuples(tuples_list):
    start_map = {}
    end_map = {}
    all_elements = set()

    for t in tuples_list:
        s, e = t
        start_map[s] = e
        end_map[e] = s
        all_elements.update(t)

    # 筛选链的起点：不在end_map里的元素，说明没有元组以它结尾
    chain_starts = [elem for elem in all_elements if elem not in end_map]
    result = []

    for start in chain_starts:
        current = start
        chain = [current]
        # 沿着映射链一直走到底
        while current in start_map:
            current = start_map[current]
            chain.append(current)
        result.append(tuple(chain))

    return result

# 测试示例
my_tuples = [('black', 'grey'), ('red', 'orange'), ('blue', 'purple'), 
             ('orange', 'yellow'), ('grey', 'white'), ('yellow', 'cream')]
print(merge_tuples(my_tuples))

运行后输出：

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

效率说明 #

这个方法的时间复杂度是O(n)，n是元组的总数，每个元素和元组都只被遍历一次，处理大规模数据也能保持高效。如果你的数据里存在循环链（比如('a','b'), ('b','a')），需要额外加个访问标记避免无限循环，不过示例里没有这种情况，当前代码完全适用。

内容的提问来源于stack exchange，提问作者Vahid S. Bokharaie