如何基于共有元素合并两个长度不同的Python嵌套列表

这个问题本质是求解元素的连通分量：只要两个元素出现在同一个子列表中就视为连通，最终将所有连通的元素汇总为同一个子列表即可。

实现逻辑 #

• 选用并查集（DSU）数据结构处理连通合并需求，不需要引入第三方依赖，也不受两个输入列表的长度差异影响
• 先把两个输入列表的所有子列表合并为一个总列表处理
• 为所有元素初始化连通关系，将同一个子列表内的所有元素做连通绑定
• 最后按连通分组汇总元素，得到合并后的嵌套列表

可运行代码 #

def merge_nested_lists(list1, list2):
    # 并查集基础实现
    parent = {}
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    def union(x, y):
        x_root, y_root = find(x), find(y)
        if x_root != y_root:
            parent[y_root] = x_root

    # 汇总两个输入的所有子列表
    all_sublists = list1 + list2
    # 初始化所有元素的父节点为自身
    for sublist in all_sublists:
        for item in sublist:
            if item not in parent:
                parent[item] = item
    # 同一子列表内的元素全部绑定连通关系
    for sublist in all_sublists:
        if len(sublist) < 2:
            continue
        first_item = sublist[0]
        for item in sublist[1:]:
            union(first_item, item)
    # 按连通根节点分组汇总元素
    merged_groups = {}
    for item in parent:
        root = find(item)
        merged_groups.setdefault(root, []).append(item)
    return list(merged_groups.values())

# 示例测试
list1 = [['a1', 'a2', 'b2'], ['h1', 'h2'], ['c1', 'd5']]
list2 = [['b5', 'a2'], ['d1', 'd2', 'c1', 'd3']]
combinedList = merge_nested_lists(list1, list2)
print(combinedList)

运行结果 #

输出和预期一致：[['a1', 'a2', 'b2', 'b5'], ['h1', 'h2'], ['c1', 'd5', 'd1', 'd2', 'd3']]，如果对元素顺序有要求，可在返回前对每个分组内的元素自定义排序规则即可。

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