按共享元素分组列表

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

Answer 1

这里有一个替代方案，使用建议的约简到一个图问题。我希望代码足够清晰，我仍然会添加一些解释。

仅仅因为它更容易使用：

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)

图现在包含：

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

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

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

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

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