logo标签列表

合并具有共同元素的列表

pythonlistnetworkx
14

假设我有一个嵌套列表，如下所示：

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

如何将这些子列表分组，通过获取至少与同一组中的另一个子列表具有共同元素的子列表的并集？因此，对于前面的示例，结果应为：

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

因此，由于它们共享'John'，第一和第二个子列表被合并。

有人可以分享他们宝贵的想法吗？
6个回答
24
在许多情况下，将问题建模为图可以使相当复杂的任务变得更加容易。从图论的角度来看，我们要找到的是图的连通组件。
因此，一种简单的方法是使用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个元素的子列表，可以使用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)

enter image description here

关于连通分量（图论）

更详细的连通分量解释：

在图论中，无向图的连通分量是一个子图，在该子图中，任意两个顶点都通过路径相互连接，并且不与超级图中的其他顶点相连。

因此，这段代码创建了一个图形，其中包含列表中的边，每个边由两个值u,v组成，其中u和v将是由此边连接的节点。

因此，至少有一个子列表具有共同元素的子列表的并集可以转化为图论问题，即所有通过现有路径相互到达的节点。

1
有趣的方法，请解释一下这是做什么的。 - Jab
1
如果子列表有超过两个元素会发生什么？ - Dani Mesejo
1
@Aiyaz 更新了一个更通用的情况，即具有超过2个元素的子列表。 - yatu
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)

请看

列表推导式

append与extend的区别

1
您可以使用 networkx 中的 connected_components 函数：
import networkx as nx 
​
L = [['John','Sayyed'], ['John' , 'Simon'] ,['bush','trump'],
     ['Sam','Suri','NewYork'],['Suri','Orlando','Canada']]
​
G = nx.Graph()
​
for i in L:
    G.add_path(i)
​
lst = list(nx.connected_components(G))
print(lst)

输出：

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

考虑到嵌套列表长这样

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

以下是我分享的两个潜在选项来解决 OP 的问题。

选项1

使用（注释使其自我解释）：

L = [set(l) for l in L] # Convert the list of lists to a list of sets
for i in range(len(L)): # For each set
    for j in range(i+1,len(L)): # For each set after the current set
        if len(L[i].intersection(L[j])) > 0: # If the two sets have a common element
            L[i] = L[i].union(L[j]) # Union the two sets
            L[j] = set() # Empty the second set
L = [list(l) for l in L if len(l) > 0] # Remove empty sets and convert the list of sets to a list of lists

这将给我们

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

为方便起见，你可能想要进行重构。
def union(L):
    L = [set(l) for l in L] # Convert the list of lists to a list of sets
    for i in range(len(L)): # For each set
        for j in range(i+1,len(L)): # For each set after the current set
            if len(L[i].intersection(L[j])) > 0: # If the two sets have a common element
                L[i] = L[i].union(L[j]) # Union the two sets
                L[j] = set() # Empty the second set
    L = [list(l) for l in L if len(l) > 0] # Remove empty sets and convert the list of sets to a list of lists
    return L

然后简单地

L_new = union(L)

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

选项 2

使用 NetworkX。

首先创建一个没有节点和边的空图。

G = nx.Graph()

然后，为了添加节点，有各种选项，比如使用{{link1：Graph.add_nodes_from}}和{{link2：Graph.add_edge}}。

for l in L: # For each sublist
    G.add_nodes_from(l) # Add all the elements of the sublist as nodes
    for i in range(len(l)): # For each element in the sublist
        for j in range(i+1,len(l)): # For each element after the current element
            G.add_edge(l[i],l[j]) # Add an edge between the two elements

# or

for l in L: # For each sublist
    G.add_nodes_from(l) # Add all nodes in the sublist to the graph
    for i in range(len(l)-1): # For each node in the sublist
        G.add_edge(l[i],l[i+1]) # Add an edge between the current node and the next node in the sublist

最后，我们可以使用 connected_components 获取连接组件的列表。

L = list(nx.connected_components(G))

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

作为额外的步骤，您可能想要绘制图形。为此，NetworkX 提供了可视化图形的基本功能。在这里查看有关使用 NetworkX 绘制图形的更多信息。
一种方法是使用 matplotlib。
有各种布局可供使用，例如：

  • spring_layout

    import matplotlib.pyplot as plt

# 创建图形的布局
pos = nx.spring_layout(G, k=0.5, iterations=20, scale=10)

# 使用布局绘制图形
nx.draw(G, pos, with_labels=True, font_weight='bold', font_color='white', node_size=2500, node_color='blue')

# 显示图形
plt.show()

    enter image description here

  • spiral_layout

    import matplotlib.pyplot as plt

# 创建图形的布局
pos = nx.spiral_layout(G, scale=5)

# 使用布局绘制图形
nx.draw(G, pos, with_labels=True, font_weight='bold', font_color='white', node_size=2500, node_color='blue')

# 显示图形
plt.show()

    enter image description here

  • shell_layout

    import matplotlib.pyplot as plt

# 创建图形的布局
pos = nx.shell_layout(G, scale=10)

# 使用布局绘制图形
nx.draw(G, pos, with_labels=True, font_weight='bold', font_color='white', node_size=2500, node_color='blue')

# 显示图形
plt.show()

    enter image description here

  • 还有更多，取决于使用情况和目标。在此处查看所有可用的布局。

0

如果顺序很重要且列表很大，您可以使用这种双管齐下的方法：

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

合并两个列表：

merge = lambda l1, l2: l1 + [ x for x in l2 if x not in l1 ]

为了更高效，可以在 l1 上创建一个 set；
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接