python中的高效连接分组算法或实现

Question

我正在寻找一种有效的连接分组（我不确定这是正确的名称..）算法或 python 的实现。

例如，我有这个嵌套列表：

connection_data = [
   ...:     ["A", "B", "C"],
   ...:     ["B", "D"],
   ...:     ["A", "C"],
   ...:     ["E", "F"],
   ...:     ["C", "D"],
   ...:     ]

此数据表示嵌套列表中的每个列表都显示连接。例如，第一个连接 ["A", "B", "C"] 表示 A 并且 B 和 C 相互连接。嵌套列表有多个连接信息。

我想根据嵌套列表计算连接分组。比如我有上connection_data，我想得到

grouped_connection = [
   ...:     ["A", "B", "C", "D"],
   ...:     ["E", "F"],
   ...:     ]

因为，A、B、C、D在connection_data的这些连接数据中有连接：["A", "B", "C"], ["B", "D"], ["A", "C"], ["C", "D"]， E 和 F 通过 ["E", "F"] 建立联系。

总结一下我的问题：

这类问题一般叫什么？
我想我可以实现很多基于 for-loop 的求解器。但是 python 中是否有针对此类问题的有效算法或实现？

Answer 1

注意：这个答案实际上比union-find算法慢由 hilberts_drinking_problem 给出。如果所有输入连接都是成对的（即大小为 2），则两种算法的运行时间基本相同。但是，OP 的问题是 而不是 的情况。详情见评论。

您可以构造一个图，其中节点的字母为 A、B、C ...，并在两个节点之间放置一条无向、未加权的边，如果初始分组指示他们应该在同一组中。然后，最后的组是构造图的connected components。（这是最接近您的问题的一般称呼。）

这可以使用图形遍历算法（例如 BFS 或 DFS）来完成，但如果您不想手动编写代码，networkx 可以在您完成后处理所有事情图。您需要对分组进行一些预处理，因为其中一些分组的大小大于 2，但除此之外 networkx 是 well-suited 对于这个问题：

from itertools import combinations
import networkx as nx

groups = [
    ["A", "B", "C"],
    ["B", "D"],
    ["A", "C"],
    ["E", "F"],
    ["C", "D"],
]

G = nx.Graph()

# Handle initial groupings of size greater than two by iterating over
# each possible pair of letters in the group.
for group in groups:
    G.add_edges_from(combinations(sorted(group), 2))

# Result should look something like [['B', 'C', 'A', 'D'], ['F', 'E']],
# but the ordering may be nondeterministic.
print(list(list(group) for group in nx.connected_components(G)))

Answer 2

Networkx 提供了一个联合查找数据结构的实现[1] [2]，它有效地解决了这个问题：

from networkx.utils.union_find import UnionFind

groups = [
    ["A", "B", "C"],
    ["B", "D"],
    ["A", "C"],
    ["E", "F"],
    ["C", "D"],
]

ds = UnionFind()
for gp in groups:
  ds.union(*gp)
for s in ds.to_sets():
  print(s)

# {'B', 'C', 'D', 'A'}
# {'E', 'F'}

python中的高效连接分组算法或实现

Efficient connection grouping algorithm or implementation in python

python

algorithm

grouping