分區通過共享元素

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似乎更正確，但我不知道如何實施它在我的情況。