基于传递关系合并元组：实现含共同元素元组的分组

问题描述 #

给定元组列表：

[(10,22), (10,20), (10,69), (34,18), (18,17), (89,990), (86,80), (174,175), (543,542)]

需要将所有至少包含一个共同元素的元组合并分组，期望得到结果：

[(10,22,20,69), (34,18,17), (89,990), (86, 80), (174,175), (543,542)]

解决方案 #

这个问题本质是查找图的连通分量：把每个数字看作节点，每个元组表示两个节点之间有连接，最终把同一连通分量里的所有节点合并成一个元组。这里用并查集（Union-Find）算法高效实现：

代码实现 #

def merge_tuples(tuples_list):
    # 初始化并查集父节点映射
    parent = {}

    def find(x):
        # 查找根节点，带路径压缩优化
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        # 合并两个节点的连通分量
        root_x = find(x)
        root_y = find(y)
        if root_x != root_y:
            parent[root_y] = root_x

    # 第一步：将所有元素加入并查集，并合并每个元组内的元素
    for tpl in tuples_list:
        for num in tpl:
            if num not in parent:
                parent[num] = num
        union(tpl[0], tpl[1])

    # 第二步：按根节点分组
    groups = {}
    for num in parent:
        root = find(num)
        groups.setdefault(root, []).append(num)

    # 第三步：转换为元组，并按原列表中分组首次出现的顺序排序
    def first_occurrence_idx(group):
        for idx, tpl in enumerate(tuples_list):
            if group[0] in tpl:
                return idx
        return float('inf')
    
    result = [tuple(group) for group in groups.values()]
    result.sort(key=first_occurrence_idx)
    return result

# 测试执行
input_list = [(10,22), (10,20), (10,69), (34,18), (18,17), (89,990), (86,80), (174,175), (543,542)]
print(merge_tuples(input_list))

输出结果 #

[(10, 22, 20, 69), (34, 18, 17), (89, 990), (86, 80), (174, 175), (543, 542)]

内容的提问来源于stack exchange，提问作者lorenzlorg