按共享元素对列表进行分组

Question

假设我有以下子列表列表：

l = [['a', 'b'], 
 ['a', 'c'], 
 ['b', 'c'],
 ['c', 'd'],  
 ['e', 'f'], 
 ['f', 'g'], 
 ['x', 'y']]

我的目标是将该列表重新排列到“桶”中，使桶中的每个子列表与桶中的至少一个其他子列表共享一个元素，并且不与不同桶中的任何子列表共享任何元素。用文字理解有点困难，但在这种情况下，期望的结果将是：

result = [
    [
        ['a', 'b'],
        ['a', 'c'],
        ['b', 'c'],
        ['c', 'd']
    ],
    [
        ['e', 'f'],
        ['f', 'g']
    ],
    [
        ['x', 'y']   
    ],
]

这里的想法是 ['a','b'] 进入 Bucket 1。['a','b'] 与 ['a', 'c'] 和 ['b', 'c'] 共享元素，因此它们也进入 Bucket 1。现在 ['c', 'd'] 也与当前在 Bucket 1 中的元素共享一个元素 c，因此它也被添加到 Bucket 1 中。之后，没有更多的子列表与 Bucket 1 中的元素共享，因此我们打开一个新的 Bucket 2，从 ['e', 'f'] 开始。 ['e', 'f'] 与 ['f', 'g'] 共享一个元素，因此它也进入 Bucket 2。然后我们完成了 Bucket 2。['x', 'y'] 得到它自己的 Bucket 3。

我知道如何递归地完成所有这些，但是 l 非常大，我想知道是否有更快的方法将元素组合在一起！

Answer 1

此代码似乎有效：

l = [
 ['a', 'b'], 
 ['a', 'c'], 
 ['b', 'c'],
 ['c', 'd'],  
 ['e', 'f'], 
 ['f', 'g'], 
 ['x', 'y']]
 
l2 = []

# merge lists to sets
for x in l:
  for x2 in l2:
     if len(x2 & set(x)):
         x2 |= set(x)
         break
  else:
     l2.append(set(x))

# output lists
d = {i:[] for i in range(len(l2))}

# match each list to set
for x in l:
  for k in d:
    if len(set(x) & set(l2[k])):
       d[k].append(x) 

# merge dictionary values
fl = [v for v in d.values()]

print(fl)

输出

[[['a', 'b'], 
  ['a', 'c'], 
  ['b', 'c'], 
  ['c', 'd']], 
 [['e', 'f'], 
  ['f', 'g']], 
 [['x', 'y']]]

Answer 2

感谢大家的建议，我想我只是需要正确的词汇！由于在链接的答案下，有几个人要求提供代码来实现所有这些，我想我会 post 一个答案以供将来参考。显然，强连通分量的概念没有为non-directed图定义，所以解决方案是寻找连通分量。

为了我的回答，我调整了在这里找到的代码：https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/

它只需要重新制定 l 有整数，而不是字符串：

class Graph:
    # init function to declare class variables
    def __init__(self, V):
        self.V = V
        self.adj = [[] for i in range(V)]
 
    def DFSUtil(self, temp, v, visited):
 
        # Mark the current vertex as visited
        visited[v] = True
 
        # Store the vertex to list
        temp.append(v)
 
        # Repeat for all vertices adjacent
        # to this vertex v
        for i in self.adj[v]:
            if visited[i] == False:
 
                # Update the list
                temp = self.DFSUtil(temp, i, visited)
        return temp
 
    # method to add an undirected edge
    def addEdge(self, v, w):
        self.adj[v].append(w)
        self.adj[w].append(v)
 
    # Method to retrieve connected components
    # in an undirected graph
    def connectedComponents(self):
        visited = []
        cc = []
        for i in range(self.V):
            visited.append(False)
        for v in range(self.V):
            if visited[v] == False:
                temp = []
                cc.append(self.DFSUtil(temp, v, visited))
        return cc

现在我们可以运行

l = [[0, 1], 
 [0, 2], 
 [1, 2],
 [2, 3],  
 [4, 5], 
 [5, 6], 
 [7, 8]]


g = Graph(
    max([item for sublist in l for item in sublist])+1
)

for sl in l:
    g.addEdge(sl[0], sl[1])
cc = g.connectedComponents()
print("Following are connected components")
print(cc)

我们得到：

Following are connected components
[[0, 1, 2, 3], [4, 5, 6], [7, 8]]

然后我们可以返回并分组原始列表：

result = []
for sublist in cc:
    bucket = [x for x in l if any(y in x for y in sublist)]
    result.append(bucket)

输出：

[[[0, 1], [0, 2], [1, 2], [2, 3]], [[4, 5], [5, 6]], [[7, 8]]]

Answer 3

这是使用建议的图形问题简化方法的替代方法。希望代码足够清晰，我还是会补充一些说明的。

转换为邻接列表

只是因为它更容易使用：

from collections import defaultdict

edges = [
    ['a', 'b'], 
    ['a', 'c'], 
    ['b', 'c'],
    ['c', 'd'],  
    ['e', 'f'], 
    ['f', 'g'], 
    ['x', 'y'],
]

def graph_from_edges(edge):
    graph = defaultdict(set)
    for u, v in edges:
        graph[u].add(v)
        graph[v].add(u)
    return graph

graph = graph_from_edges(edges)

graph 现在包含：

{
    'a': {'c', 'b'}, 
    'b': {'c', 'a'}, 
    'c': {'d', 'b', 'a'}, 
    'd': {'c'}, 
    'e': {'f'}, 
    'f': {'e', 'g'}, 
    'g': {'f'}, 
    'x': {'y'}, 
    'y': {'x'}
}

找到给定节点的连通分量

这是一个更简单的 sub-problem 求解，我们给出一个节点并探索附近的图，直到我们只访问了可用的节点：

def connected_component_from(graph, starting_node):
    nodes = set(starting_node)
    visited = set()
    while nodes:
        node = nodes.pop()
        yield node
        visited.add(node)
        nodes |= graph[node] - visited

print(list(connected_component_from(graph, 'a')))

这会打印节点 'a':

的连通分量中的节点列表

['a', 'b', 'c', 'd']

寻找所有连通分量

现在我们只需要重复前面的操作，直到我们访问了图中的所有节点。要发现新的未探索组件，我们只需选择一个随机未访问的节点重新开始：

def connected_components(graph):
    all_nodes = set(graph.keys())
    visited = set() 
    while all_nodes - visited:
        starting_node = random_node(all_nodes - visited)
        connected_component = set(connected_component_from(graph, starting_node))
        yield connected_component
        visited |= connected_component

def random_node(nodes):
    return random.sample(nodes, 1)


graph_cc = list(connected_components(graph))
print(graph_cc)

打印：

[{'a', 'c', 'd', 'b'}, {'g', 'e', 'f'}, {'y', 'x'}]

快捷方式

您也可以使用现有库为您计算这些连通分量，例如 networkx:

import networkx as nx

G = nx.Graph()

G.add_edges_from(edges)
cc = list(nx.connected_components(G))
print(graph_cc)

它还打印：

[{'a', 'c', 'd', 'b'}, {'g', 'e', 'f'}, {'y', 'x'}]

在实践中，这将是最好的解决方案，但如果目标是学习新事物，那就没那么有趣了。注意可以查看networkx implementation of the function (which uses this BFS)

回到最初的问题

我们设法从同一个连接组件中找到节点，但这不是您想要的，因此我们需要取回原始列表。为了在大图上更快地做到这一点，一种可能是首先在上一个列表中有一个从节点名称到它们的连接组件索引的映射：

node_cc_index = {u: i for i, cc in enumerate(graph_cc) for u in cc}
print(node_cc_index)

给出：

{'g': 0, 'e': 0, 'f': 0, 'a': 1, 'c': 1, 'd': 1, 'b': 1, 'y': 2, 'x': 2}

我们可以使用它来填充您第一次请求的分割边列表：

edges_groups = [[] for _ in graph_cc]
for u, v in edges:
    edges_groups[node_cc_index[u]].append([u, v])

print(edges_groups)

最后给出：

[
    [['e', 'f'], ['f', 'g']], 
    [['a', 'b'], ['a', 'c'], ['b', 'c'], ['c', 'd']], 
    [['x', 'y']]
]

每个子列表保留原始顺序，但列表之间的顺序不以任何方式保留（这是我们随机选择的直接结果）。为了避免这种情况，如果这是一个问题，我们可以通过选择“第一个”未访问的节点来替换随机选择。

按共享元素对列表进行分组

Group list of lists by shared elements

python

sorting

grouping

list

转换为邻接列表

找到给定节点的连通分量

寻找所有连通分量

快捷方式

回到最初的问题