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有联系：["A", "B", "C"], ["B", "D"], ["A", "C"], ["C", "D"]，E和F通过["E", "F"]相互连接。

总结我的问题：

1. 这种类型的问题通常叫什么名字？
2. 我认为我可以实现基于多重循环的求解器。但是，有没有针对这种问题的有效算法或Python实现？

- Atsushi Sakai

---

我认为这个链接很相关：https://dev59.com/ImIj5IYBdhLWcg3wilkI - Shlomo Gottlieb

Answer 1

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

- hilberts_drinking_problem

Answer 2

注意：这个答案实际上比hilberts_drinking_problem给出的并查集算法要慢。如果所有输入连接都是成对的（即大小为2），那么两种算法的运行时间本质上是相同的。然而，这不是OP问题的情况。有关详细信息，请参见评论。

---

您可以构建一个图，其中节点以字母A、B、C等命名，并在两个节点之间放置一个无向、未加权的边，如果初始分组规定它们应该在同一组中。然后，最终的组是所构造图的连通分量。（这是您的问题通常被称为的最接近的事物）

这可以使用图遍历算法（如BFS或DFS）完成，但如果您不想手动编写代码，networkx可以在您制作图形后处理所有内容。您需要对分组进行一些预处理，因为其中一些分组的大小大于2，但除此之外，networkx非常适合解决此问题：

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)))

- BrokenBenchmark

---

另外，就我个人而言，在StackOverflow上阅读答案时，我非常喜欢能够看到输出结果。因此，在这种情况下，我建议在最终的“print”语句下方添加结果# [['E'，'F']，['B'，'A'，'C'，'D']]。 - Stef

我认为并查集是解决这个问题的最佳方法，尽管这个参考链接提供了一些相关讨论。 - hilberts_drinking_problem

@Stef 修订后的答案。 - BrokenBenchmark

在我看来，用图形化的方式解释这个问题更容易，因为你可以很容易地将其分解成节点、边和标准图算法。但我认为使用并查集也没有任何问题。（你链接的讨论中，有人指出“union（）”不是“O（1）”操作，但反阿克曼函数在实践中受到了小常数的限制。） - BrokenBenchmark

@Stef 啊，说得好。通常问题的表述方式是所有组的大小都为2，所以这个问题通常不会出现。 - BrokenBenchmark