python - 将列表与常用元素组合

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

在许多情况下，将问题建模为图形可以使相当复杂的任务变得更加容易。在这种情况下，我们从图论的角度寻找的是 connected components。的图形。

一个简单的方法就是用 NetworkX 生成一个图表，并使用 add_edges_from 添加您的列表作为图形边缘.然后使用 connected_components ，这将精确地为您提供图中连通分量集的列表:

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'}]

---

包含多个(>2)项的子列表呢？

如果子列表包含超过 2 个元素，您可以将它们添加为路径，而不是使用 nx.add_path 的节点，因为它们可以连接多个节点:

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

G=nx.Graph()
for l in L:
    nx.add_path(G, l)
list(nx.connected_components(G))

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

我们还可以使用 nx.draw 可视化这些连接的组件:

pos = nx.spring_layout(G, scale=20, k=2/np.sqrt(G.order()))
nx.draw(G, pos, node_color='lightgreen', node_size=1000, with_labels=True)

---

关于连通分量(图论)

关于 connected components 的更详细解释:

In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph

从本质上讲，这段代码创建了一个图，其中包含列表中的边，其中每条边由两个值 u,v 组成，其中 u 和 v 将是通过这条边连接的节点。

因此，子列表与至少一个具有公共(public)元素的子列表的联合可以转化为一个图论问题，因为所有节点都可以通过现有路径在彼此之间到达。