分区通过共享元素

Question

的集列表这里的问题JIST：鉴于套，如列表：

[ (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）。

更复杂的是，我要指出，我真的没有这些整齐套，而是一个数据库表与几百万行，看起来像：

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，如下：
• 如果我已被标记由一些Ĵ< I，然后继续（我的意思是跳到下一I）
• 其他flood_from（I，I）

其中flood_from（I，J）将用于被定义为

• 每个集合S包含i，如果它尚未被j标记，则：
• 标签S由j和S的每个元素k，如果k尚未被j标记，则标记为j，并调用flood_from（ k，j）

这些集合的标签会为您提供您正在寻找的连接组件。

---

在数据库方面，该算法可表示如下：添加一个TAG列到你的数据库，你做

• S =选择所有计算集我的连接组件行，其中SET_ID ==我
• 组TAG至i中代表S
行
• S“=选择所有的行，其中TAG未设置，并且其中元件是在元件（S）
• 而S”不​​为空，做
• ----在S '
• ---- S '设置TAG为i为行'=选择其中TAG没有设置所有的行，并且其中元件是在元件（S'）
• - --- S =小号工会S '
• ---- S'= S ''
• 返回SET_ID（S）

---

呈递本算法将是另一种（理论值）的方式说你正在寻找映射的固定点：

• 如果A = {A 1 ，...，A _Ñ}是一组套，限定接头（A）= A 1 _工会 ...工会甲_Ñ
• 如果K = [KP ，...，K _p}是一个整数集，定义发生率（K）=该组的组相交ķ

然后，如果S是一组中，通过在S迭代（发生率）O（联合），直到达到固定的点获得S的连接成分：

1. ķ= S
2. K” =发生率（工会（K））。
3. 如果K == K'，则返回K，否则K = K'并且转到2.

Answer 2

你可以把它看作一个图集问题，集合（1,2,3）通过2连接到集合（5,2,6）。然后使用标准算法对连接的子集-graphs。

这里有一个快速的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]] 

Answer 3

这可能是非常低效的，但它应该工作，至少包括：启动与一键，选择所有含组该键，选择这些组的所有键，选择包含这些键的所有组等等，并且只要一个步骤不添加新的键或组，就可以得到一个子图的所有组的列表。排除这些并从头开始重复，直到没有数据。

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

Answer 4

思考这个多一些，我想出了这个：

1. 创建的表中调用groups的列(group_id, set_id)
2. 排序sets表由element。现在应该很容易找到重复的元素。
3. 迭代通过套表，当你发现重复的元素做：
   1. 如果set_id领域之一的groups表存在，添加具有相同group_id另一个。
   2. 如果groups表中不存在set_id，则生成一个新的组ID，并将set_ids添加到groups表中。

到底我应该有一个包含所有集的groups表。

这不是纯粹的SQL，但看起来像O（nlogn），所以我想我可以忍受这一点。

Matt's answer似乎更正确，但我不知道如何实施它在我的情况。