Python大量多个列表(list)合并(合并有相同元素的列表)

示例：

[[1,2],[3,4,5],[0,4]]      合并后     [[1,2],[0,3,4,5]
[[1],[1,2],[0,2]]             合并后     [[0,1,2]]
[[1, 2], [2, 3], [3, 4]]    合并后     [[1,2,3,4]]

1、使用networkx合并

使用 networkx 库来合并有相同元素的列表是一个很好的方法，因为 networkx 处理图结构非常方便。

import networkx as nx
l = [[1,2],[3,4,5],[0,4]]
#l = [[1],[1,2],[0,2]]
#l = [[1, 2], [2, 3], [3, 4]]
G = nx.Graph()
#将节点添加到Graph    
G.add_nodes_from(sum(l, []))
#从节点列表创建边
q = [[(s[i],s[i+1]) for i in range(len(s)-1)] for s in l]
for i in q:
    #向Graph添加边
    G.add_edges_from(i)
#查找每个组件的图形和列表节点中的所有连接组件
[list(i) for i in nx.connected_components(G)]

输出：

[[1, 2], [0, 3, 4, 5]]

2、使用itertools中combinations合并

使用 itertools.combinations 来合并多个列表中具有相同元素的列表是一个常见的方法。该方法利用 itertools.combinations 和集合操作来高效地检测和合并相交的集合。代码清晰易懂，便于维护和修改。

from itertools import combinations

def bfs(graph, start):
    """
    广度优先搜索（BFS）算法，用于遍历图的一个连通分量。
    
    参数:
    - graph: 图的邻接表表示（字典形式）。
    - start: 起始节点。
    
    返回:
    - visited: 从起始节点开始的所有已访问节点的集合。
    """
    visited, queue = set(), [start]  # 初始化已访问节点集合和队列
    while queue:
        vertex = queue.pop(0)  # 从队列中弹出第一个节点
        if vertex not in visited:
            visited.add(vertex)  # 如果节点未访问，则将其标记为已访问
            queue.extend(graph[vertex] - visited)  # 将所有邻接节点加入队列
    return visited

def connected_components(G):
    """
    查找图中的所有连通分量。
    
    参数:
    - G: 图的邻接表表示（字典形式）。
    
    生成器:
    - 每次迭代返回一个连通分量的集合。
    """
    seen = set()  # 初始化已见节点集合
    for v in G:
        if v not in seen:
            c = set(bfs(G, v))  # 对未见过的节点进行BFS搜索
            yield c  # 生成当前连通分量
            seen.update(c)  # 更新已见节点集合

def graph(edge_list):
    """
    根据边列表创建图的邻接表表示。
    
    参数:
    - edge_list: 边列表，边由节点对（source, target）表示。
    
    返回:
    - result: 图的邻接表表示（字典形式）。
    """
    result = {}
    for source, target in edge_list:
        result.setdefault(source, set()).add(target)  # 为source添加target
        result.setdefault(target, set()).add(source)  # 为target添加source
    return result

def concat(l):
    """
    合并有相同元素的列表。
    
    参数:
    - l: 包含多个列表的列表。
    
    返回:
    - result: 合并后的列表，包含所有互相连通的元素集合。
    """
    edges = []
    s = list(map(set, l))  # 将列表中的每个子列表转换为集合
    for i, j in combinations(range(len(s)), r=2):
        if s[i].intersection(s[j]):  # 如果两个集合有交集，则认为它们相连
            edges.append((i, j))  # 记录集合的索引对
    
    G = graph(edges)  # 创建图的邻接表表示
    result = []
    unassigned = list(range(len(s)))  # 初始化未分配的集合索引
    for component in connected_components(G):
        union = set().union(*(s[i] for i in component))  # 合并当前连通分量中的所有集合
        result.append(sorted(union))  # 将合并后的集合加入结果，并排序
        unassigned = [i for i in unassigned if i not in component]  # 更新未分配的集合索引
    
    result.extend(map(sorted, (s[i] for i in unassigned)))  # 处理剩余的未合并集合
    return result

# 测试用例
print(concat([[1, 2], [3, 4, 5], [0, 4]]))  # 输出: [[0, 3, 4, 5], [1, 2]]
print(concat([[1], [1, 2], [0, 2]]))  # 输出: [[0, 1, 2]]
print(concat([[1, 2], [2, 3], [3, 4]]))  # 输出: [[1, 2, 3, 4]]

输出：

[[0, 3, 4, 5], [1, 2]]
[[0, 1, 2]]
[[1, 2, 3, 4]]