python3 加入列表列表中具有相同值的列表

Question

我有一个与几年前被问过的问题类似的问题，link 在下面。问题是所有答案都在 python 2 中并且对我有用。我的清单很大，所以时间很重要。如果有人能为 python3 解决这个问题，那真的很有帮助。

考虑这个列表列表：

l = [ [1], [1], [1,2,3], [4,1], [5], [5], [6], [7,8,9], [7,6], [8,5] ]

我想合并所有至少有一个共同数字的列表，这将迭代完成，直到完成并且不会有双字母。结果将是：

combine(l) = [ [1,2,3,4], [5,6,7,8,9] ]

有什么巧妙的方法可以做到这一点，也许可以使用 itertools？

Combine lists that have at least a number in common in a list of lists, Python

Answer 1

效率不高，但仍然有效。

l = [ [1], [1], [1,2,3], [4,1], [5], [5], [6], [7,8,9], [7,6], [8,5] ]

# simple merging
def once(l):
    mod = False
    subsets = []
    while len(l) > 0:
        item = set(l.pop(0))
        for i in range(len(subsets)):
            if subsets[i].intersection(item):
                subsets[i] = subsets[i].union(item)
                mod = True
                break
        else:
            subsets.append(item)
    return [list(s) for s in subsets], mod

# repeat merging until nothing changed
mod = True
while mod:
    l, mod = once(l)
print(l)

Answer 2

这可以看作是一个图问题，您在其中合并子图并需要找到连接的组件。

这是你的图表：

网络x

使用networkx你可以做到：

import networkx as nx
from itertools import chain, pairwise
# python < 3.10 use this recipe for pairwise instead
# from itertools import tee
# def pairwise(iterable):
#     a, b = tee(iterable)
#     next(b, None)
#     return zip(a, b)

G = nx.Graph()
G = nx.from_edgelist(chain.from_iterable(pairwise(e) for e in l))
G.add_nodes_from(set.union(*map(set, l))) # adding single items

list(nx.connected_components(G))

输出：

[{1, 2, 3, 4}, {5, 6, 7, 8, 9}]

python

现在，您可以使用纯 python 来执行相同的操作，找到连接的组件并合并它们。

示例代码在 this post (archive.org link 中有很好的描述。

总而言之，第一步是构建邻居列表，然后使用递归函数加入邻居的邻居，跟踪已经看到的邻居。

from collections import defaultdict 
  
#merge function to  merge all sublist having common elements. 
def merge_common(lists): 
    neigh = defaultdict(set) 
    visited = set() 
    for each in lists: 
        for item in each: 
            neigh[item].update(each) 
    def comp(node, neigh = neigh, visited = visited, vis = visited.add): 
        nodes = set([node]) 
        next_node = nodes.pop 
        while nodes: 
            node = next_node() 
            vis(node) 
            nodes |= neigh[node] - visited 
            yield node 
    for node in neigh: 
        if node not in visited: 
            yield sorted(comp(node))

示例：

merge_common(l)
# [[1, 2, 3, 4], [5, 6, 7, 8, 9]]

python3 加入列表列表中具有相同值的列表

python3 join lists that have same value in list of lists

python

merge

list

网络x

python