将一组集合按共同元素分成多个部分

Question

以下是问题的要点：给定一个集合列表，例如：

[ (1,2,3), (5,2,6), (7,8,9), (6,12,13), (21,8,34), (19,20) ]

返回一个集合组的列表，使具有共享元素的集合在同一组中。

[ [ (1,2,3), (5,2,6), (6,12,13) ], [ (7,8,9), (21,8,34) ], [ (19,20) ] ]

请注意“粘性”-集合（6,12,13）与（1,2,3）没有共同元素，但由于（5,2,6），它们被放在同一组中。

更加复杂的是，我应该提到我实际上没有这些整洁的集合，而是一个包含数百万行的数据库表，看起来像：

element | set_id
----------------
1       | 1
2       | 1
3       | 1
5       | 2
2       | 2
6       | 2

等等。因此，我希望有一种在SQL中完成它的方法，但是如果能给出解决方案的一般方向，我也会很高兴。

编辑：将表格列名更改为（元素，集合ID）而不是（键，组ID），以使术语更加一致。请注意Kev的答案使用了旧的列名。

- itsadok

Answer 1

问题在于计算超图的连通分量：整数是顶点，集合是超边。计算连通分量的一种常见方法是逐个进行泛洪：

- 对于所有 i = 1 到 N，执行以下操作： - 如果 i 已被某个 j < i 标记，则继续（跳转到下一个 i） - 否则从 i 开始进行泛洪 flood_from(i,i)

其中 flood_from(i,j) 的定义为：

- 对于包含 i 的每个集合 S，如果它尚未被标记为 j，则： - 将 S 标记为 j，并对 S 中的每个元素 k 进行如下操作：如果 k 尚未被标记为 j，则将其标记为 j，并调用 flood_from(k,j)

然后集合的标记就给出了您要查找的连通分量。

---

从数据库的角度来看，算法可以表示为：向数据库添加一个 TAG 列，并通过以下方式计算集合 i 的连通分量：

- S = 选择所有 set_id == i 的行 - 为 S 中的行设置 TAG 为 i - S' = 选择所有 TAG 未设置且元素属于 element(S) 的行 - 当 S' 不为空时，执行以下操作： - ---- 为 S' 中的行设置 TAG 为 i - ---- S'' = 选择所有 TAG 未设置且元素属于 element(S') 的行 - ---- S = S 并集 S' - ---- S' = S'' - 返回 set_id(S)

---

另一种（理论上的）表述这个算法的方式是说，您正在寻找映射的不动点：

- 如果 A = {A₁, ..., A_n} 是一组集合，则定义 union(A) = A₁ 并集 ... 并集 A_n - 如果 K = {k₁, ..., k_p} 是一组整数，则定义 incidences(K) = 与 K 相交的集合的集合

然后，如果 S 是一个集合，则通过在 S 上迭代 (incidences)o(union) 直到达到不动点来获得 S 的连通分量：

- K = S - K' = incidences(union(K)) - 如果 K == K'，则返回 K；否则，K = K' 并转到步骤 2.

- Camille

---

辛苦了！你能看一下我的答案并告诉我它是否有错，基本上与你的解决方案相同还是只是不同的解决方案？ - itsadok

在我看来，你需要一些合并步骤才能使你的解决方案完整：你可能会为应该在同一组中的集合启动不同的goup_ids，因为你还没有发现它们。如果你有一个重复项，并且两个集合在不同的组中，那么就合并这两个组。 - Camille

Answer 2

你可以将其视为一个图问题，其中集合（1,2,3）通过2与集合（5,2,6）相连。然后使用标准算法来查找连接的子图。

以下是一个快速的Python实现：

nodes = [ [1,2,3], [2,4,5], [6,7,8], [10,11,12], [7,10,13], [12], [] ]
links = [ set() for x in nodes ]

#first find the links
for n in range(len(nodes)):
    for item in nodes[n]:
        for m in range(n+1, len(nodes)):
            if (item in nodes[m]):
                links[n].add(m)
                links[m].add(n)

sets = []
nodes_not_in_a_set = range(len(nodes))

while len(nodes_not_in_a_set) > 0:
    nodes_to_explore = [nodes_not_in_a_set.pop()]
    current_set = set()
    while len(nodes_to_explore) > 0:
        current_node = nodes_to_explore.pop()
        current_set.add(current_node)
        if current_node in nodes_not_in_a_set:
            nodes_not_in_a_set.remove(current_node)
        for l in links[current_node]:
            if l not in current_set and l not in nodes_to_explore:
                nodes_to_explore.append(l)
    if len(current_set) > 0:
        sets.append(current_set)

for s in sets:
    print [nodes[n] for n in s]

输出：

[[]]
[[6, 7, 8], [10, 11, 12], [7, 10, 13], [12]]
[[1, 2, 3], [2, 4, 5]]

- Matt Price

---

你能详细说明一下吗？ - itsadok

这很难在没有lft，rgt策略的情况下完成（除非您想要大量循环进行树遍历）。 - Pittsburgh DBA

Answer 3

这可能相当低效，但至少应该可以工作：从一个键开始，选择包含该键的所有组，选择这些组的所有键，选择包含这些键的所有组等等，直到一步不再添加新的键或组为止，你就有了一个子图中所有组的列表。排除这些并从头开始重复，直到没有数据剩余。

在 SQL 方面，我认为这需要一个存储过程。 WITH RECURSIVE 可能会在某种程度上帮助你，但我还没有任何经验，并且我不确定它是否可用于你的数据库后端。

- Kev

Answer 4

经过进一步思考，我想到了以下方法：

1. 创建一个名为groups的表，其列为(group_id, set_id)
2. 按element对sets表进行排序。现在应该很容易找到重复元素。
3. 遍历sets表，当你找到重复元素时执行以下操作：
   1. 如果set_id字段之一存在于groups表中，则将具有相同group_id的另一个添加到其中。
   2. 如果set_id都不存在于groups表中，则生成一个新的组ID，并将两个set_id都添加到groups表中。

最终我应该会得到一个包含所有集合的groups表。

这不是纯粹的SQL语言，但似乎是O（nlogn），所以我想我可以接受它。

Matt的回答看起来更正确，但我不确定如何在我的情况下实现它。

- itsadok