合并具有共同元素的列表

本文介绍了合并具有共同元素的列表的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我的输入是一个列表列表.其中一些共享共同的元素，例如.

My input is a list of lists. Some of them share common elements, eg.

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

我需要合并所有共享一个公共元素的列表，并重复此过程，只要不再有包含相同项目的列表即可.我曾考虑过要使用布尔运算和while循环，但无法提出一个好的解决方案.

I need to merge all lists, that share a common element, and repeat this procedure as long as there are no more lists with the same item. I thought about using boolean operations and a while loop, but couldn't come up with a good solution.

最终结果应该是:

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

推荐答案

您可以将列表看作是Graph的一种表示法，即['a','b','c']是一个具有3个相互连接的节点的图.您要解决的问题是在此图中找到连接的组件.

You can see your list as a notation for a Graph, ie ['a','b','c'] is a graph with 3 nodes connected to each other. The problem you are trying to solve is finding connected components in this graph.

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

You can use NetworkX for this, which has the advantage that it's pretty much guaranteed to be correct:

l = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']] import networkx from networkx.algorithmsponents.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.

To solve this efficiently yourself you have to convert the list into something graph-ish anyways, so you might as well use networkX from the start.