具有共同元素的子列表联盟

Question

假设我有以下嵌套列表:

L = [['John','Sayyed'], ['John' , 'Simon'] ,['bush','trump'],
     ['Sam','Suri','NewYork'],['Suri','Orlando','Canada']]

如何通过将具有共同元素的子列表与该组中的至少另一个子列表结合起来,对这些子列表进行分组？所以对于前面的例子,结果应该是:

[['John','Sayyed','Simon'] ,['bush','trump'],
 ['Sam','Suri','NewYork','Orlando','Canada']]

因此,前两个子列表在他们共享时加入'John'.有人可以分享他们宝贵的想法吗？

Answer 1

你可以用nx.connected_components它.生成图形,并使用列表作为图形边缘添加networkx.然后使用add_edges_from,它将精确地为您提供图表中连接组件集的列表:

import networkx as nx 

L = [['John','Sayyed'], ['John' , 'Simon'] ,['bush','trump']

G=nx.Graph()
G.add_edges_from(L)
list(nx.connected_components(G))

[{'John', 'Sayyed', 'Simon'}, {'bush', 'trump'}]

更新

在具有多个connected_components元素的子列表的情况下,您可以2 2从每个子列表中获取所有长度并将其用作网络边缘:

from itertools import combinations, chain

L = [['John','Sayyed'], [ 'John' , 'Simon'] ,['bush','trump'],
     ['Sam','Suri','NewYork'],['Suri','Orlando','Canada']]

L2_nested = [list(combinations(l,2)) for l in L]
L2 = list(chain.from_iterable(L2_nested))
#[('John', 'Sayyed'), ('John', 'Simon'), ('bush', 'trump'), ('Sam', 'Suri')...

G=nx.Graph()
G.add_edges_from(L2)
list(nx.connected_components(G))

[{'John', 'Sayyed', 'Simon'},
{'bush', 'trump'},
{'Canada', 'NewYork', 'Orlando', 'Sam', 'Suri'}]

细节

有关连接组件的更详细说明:

在图论中,无向图的连通分量(或只是分量)是一个子图,其中任意两个顶点通过路径相互连接,并且在超图中没有连接到其他顶点

基本上,这段代码创建了一个图表,其中包含列表中的边,其中每个边由两个值组成,combinations其中nx.draw和u,v将是由此边连接的节点.

因此,具有至少一个具有共同元素的子列表的子列表的并集可以被转换为图论理论问题,因为所有节点可以通过现有路径在彼此之间到达.下图可以看到一个例子,它有三个连接的组件: