合并共享公共元素的列表 [英] Merge lists that share common elements
问题描述
我的输入是一个列表列表.其中一些共享相同的元素,例如.
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']]
推荐答案
您可以将列表视为图形的符号,即 ['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.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.
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.
这篇关于合并共享公共元素的列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!