按共享元素对集合列表进行分区

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

注意stickeyness - 集合(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的答案使用旧的列名称.

Answer 1

问题恰恰是超图的连通分量的计算:整数是顶点,而集合是超边界.计算连接组件的常用方法是一个接一个地泛滥它们:

• 对于所有i = 1到N,执行:
• 如果我被一些j <i标记,那么继续(我的意思是跳到下一个i)
• 否则flood_from(i,i)

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

• 对于包含i的每个集合S,如果它还没有被j标记,那么:
• 标记S by j和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 union S'
• ---- S'= S''
• return set_id(S)

呈现此算法的另一种(理论)方式是说您正在寻找映射的固定点:

• 如果A = {A ₁,...,A _n }是一组集合,则定义union(A)= A ₁ union ... union A _n
• 如果K = {k ₁,...,k _p }是一组整数,则定义入射(K)=与K相交的集合集

然后,如果S是一个集合,则通过在S上迭代(入射)o(并集)直到达到一个固定点来获得S的连通分量:

1. K = S.
2. K'=发生率(联合(K)).
3. 如果K == K',则返回K,否则K = K'并转到2.