如何在Python中递归合并有公共元素的子集列表？

方法一：并查集（Union-Find）算法 #

这是处理这类连通性问题最高效的方案，核心思路是把每个元素看作节点，有公共元素的子集对应节点间的连通关系，最终将所有连通的元素归为一组：

def merge_subsets(subsets):
    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 subset in subsets:
        for num in subset:
            if num not in parent:
                parent[num] = num
        # 将当前子集内的所有元素与第一个元素合并
        if subset:
            first_num = subset[0]
            for num in subset[1:]:
                union(first_num, num)
    
    # 按根节点分组
    groups = {}
    for num in parent:
        root = find(num)
        groups.setdefault(root, []).append(num)
    
    # 返回排序后的结果（可选，按需调整）
    return [sorted(group) for group in groups.values()]

# 测试
my_set = [[1, 2, 3], [1, 5], [4, 5, 6], [7, 8]]
my_final_set = merge_subsets(my_set)
print(my_final_set)  # 输出 [[1, 2, 3, 4, 5, 6], [7, 8]]

方法二：递归实现 #

递归逻辑更直观：每次取一个子集，合并所有与它有公共元素的子集，再递归处理剩余无交集的子集：

def merge_subsets_recursive(subsets):
    if not subsets:
        return []
    
    # 以第一个子集为基础，合并所有有交集的子集
    current = set(subsets[0])
    remaining = []
    for subset in subsets[1:]:
        subset_set = set(subset)
        if current & subset_set:
            current.update(subset_set)
        else:
            remaining.append(subset)
    
    # 递归处理剩余子集，拼接结果
    return [sorted(current)] + merge_subsets_recursive(remaining)

# 测试
my_set = [[1, 2, 3], [1, 5], [4, 5, 6], [7, 8]]
my_final_set = merge_subsets_recursive(my_set)
print(my_final_set)  # 输出 [[1, 2, 3, 4, 5, 6], [7, 8]]

说明 #

• 递归方法逻辑简单，但面对大规模数据时效率较低，因为每次都要遍历剩余子集查找交集。
• 并查集的时间复杂度接近O(n)（n为所有元素总数），更适合处理大量数据的场景。

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