python - 合并共享共同元素的列表

Question

我的输入是一个列表列表。其中一些具有共同的元素，例如。

L = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]

我需要合并所有共享一个公共(public)元素的列表，并重复此过程，只要没有更多具有相同项目的列表。我考虑过使用 bool 运算和while循环，但没有想出一个好的解决方案。

最终结果应该是:

L = [['a','b','c','d','e','f','g','o','p'],['k']] 

Answer 1

您可以将您的列表视为图表的符号，即 ['a','b','c'] 是具有 3 个相互连接的节点的图表。您要解决的问题是查找 connected components in this graph .

您可以使用 NetworkX为此，它的优点是几乎可以保证是正确的:

l = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]

import networkx 
from networkx.algorithms.components.connected import connected_components


def to_graph(l):
    G = networkx.Graph()
    for part in l:
        # each sublist is a bunch of nodes
        G.add_nodes_from(part)
        # it also imlies a number of edges:
        G.add_edges_from(to_edges(part))
    return G

def to_edges(l):
    """ 
        treat `l` as a Graph and returns it's edges 
        to_edges(['a','b','c','d']) -> [(a,b), (b,c),(c,d)]
    """
    it = iter(l)
    last = next(it)

    for current in it:
        yield last, current
        last = current    

G = to_graph(l)
print connected_components(G)
# prints [['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p'], ['k']]

为了自己有效地解决这个问题，无论如何你都必须将列表转换为图形化的东西，所以你不妨从一开始就使用 networkX。