5

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

[ (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)，它们被放在同一个组中。

更复杂的是，我应该提一下，我并没有真正拥有这些整洁的集合，而是一个包含数百万行的 DB 表，如下所示：

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

等等。所以我很想用 SQL 来做这件事，但我会对解决方案的总体方向感到满意。

编辑：将表列名称更改为 (element, set_id) 而不是 (key, group_id)，以使术语更加一致。请注意，Kev 的答案使用旧的列名。

4

4 回答 4

6

问题正是超图连通分量的计算：整数是顶点，集合是超边。计算连接组件的一种常用方法是一个接一个地泛洪它们：

  • 对于所有 i = 1 到 N，请执行以下操作：
  • 如果 i 已被某个 j < i 标记，则继续（我的意思是跳到下一个 i）
  • 否则 flood_from(i,i)

其中 flood_from(i,j) 将被定义为

  • 对于每个包含 i 的集合 S，如果它还没有被 j 标记，那么：
  • 用 j 标记 S 并且对于 S 的每个元素 k，如果 k 还没有被 j 标记，则用 j 标记它，并调用 flood_from(k,j)

然后，集合的标签会为您提供您正在寻找的连接组件。

就数据库而言，该算法可以表示为：在数据库中添加一个 TAG 列，然后通过以下方式计算集合 i 的连通分量

  • S = 选择 set_id == i 的所有行
  • 对于 S 中的行，将 TAG 设置为 i
  • S' = 选择未设置 TAG 且元素在元素 (S) 中的所有行
  • 当 S' 不为空时，执行
  • ---- 为 S' 中的行设置 TAG 为 i
  • ---- S'' = 选择未设置 TAG 且元素在元素中的所有行（S'）
  • ---- S = S 联合 S'
  • ---- S' = S''
  • 返回 set_id(S)

呈现此算法的另一种（理论）方式是说您正在寻找映射的不动点：

  • 如果 A = {A 1 , ..., A n } 是一组集合，定义 union(A) = A 1 union ... union A n
  • 如果 K = {k 1 , ..., k p } 是一个整数集合，定义发病率(K) = 与 K 相交的集合

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

  1. K = S
  2. K' = 发生率（联合（K））。
  3. 如果 K == K'，则返回 K，否则 K = K' 并转到 2。
于 2008-10-07T21:46:23.557 回答
1

您可以将其视为一个图问题，其中集合 (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]]
于 2008-10-07T15:12:03.303 回答
0

这可能效率很低，但至少应该可以：从一个键开始，选择包含该键的所有组，选择这些组的所有键，选择包含这些键的所有组等，并且只要一个步骤不会添加新的键或组，您有一个子图的所有组的列表。排除这些并从头开始重复，直到没有数据为止。

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

于 2008-10-07T15:16:14.967 回答
0

在考虑了更多之后，我想出了这个：

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

最后我应该有一个groups包含所有集合的表。

这不是纯 SQL，但看起来像 O(nlogn)，所以我想我可以忍受。

马特的回答似乎更正确，但我不确定如何在我的情况下实现它。

于 2008-10-07T15:59:22.133 回答