将列表与公共元素组合

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

简单的方法

L = [['John','Sayyed'], [ 'John' , 'Simon'] ,['bush','trump']]
L[0].extend([x for x in L[1] if x not in L[0]])
L.pop(1)
print(L) 

看

List Comprehensions

Append vs Extend

Answer 2

如果订单很重要且列表很大，则可以使用以下双管齐下的方法：

 l = [['john', 'sayyid'], ['john', 'simon'], ['b', 't']]

 def join(l1, l2):
     mset = set(l1)
     result = l1[:] # deep copy
     for each in l2:
         if each in mset:
             continue
         else:
             result.append(each)
     return result

要在主列表中合并，只需按其排名调用列表并弹出原始列表：

l1 = l.pop(0)
l2 = l.pop(0)
l.insert(0, join(l1, l2))
>>> l:
[['john', 'sayyid', 'simon'], ['b', 't']]

Answer 3

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

一个简单的方法是用NetworkX生成一个图，然后用^{}将列表添加为图边。然后使用^{}，它将精确地为您提供图形中连接组件集的列表：

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

我们还可以使用^{}将这些连接的组件形象化：

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将是该边连接的节点

因此，子列表与至少一个子列表和一个公共元素的并集可以转化为图论问题，因为所有节点都可以通过现有路径相互访问