從成對明智組合中識別集合

Question

我有一個元組列表，用於識別項目之間的成對關係。

[(1,2), (2,3), (3,1), (4,5), (5,4), (6,7)] 

我想要在整個元組的外觀和它們摺疊成獨特的收藏如下（也許作爲一個哈希地圖 - 任何其他有效的數據結構）：

{a: (1,2,3), b: (4,5), c(6,7)} 

是否有確實的算法這是有效的 - 我現在只能想到一種暴力方法。

尋求在Python或R中實現這個。我原來的例子有大約2800萬個元組。

Answer 1

你基本上想找到連接的組件。爲此，scipy中有一個功能connected_components。你只需要重新詮釋你的數據位：

l = [(1,2), (2,3), (3,1), (4,5), (5,4), (6,7)] 

from scipy.sparse.csgraph import connected_components 
from scipy.sparse import csr_matrix 

# make list of unique elements 
uniques = list(set(list(map(lambda a: a[0], l)) + list(map(lambda a: a[1], l)))) 
# reverse index to lookup elements index 
unique2index = dict([(el, i) for (i, el) in enumerate(uniques)]) 

# prepare data for csr_matrix construction 
data = [1 for x in l] # value 1 -- means edge 
data_i = [unique2index.get(x[0]) for x in l] # source node 
data_j = [unique2index.get(x[1]) for x in l] # target node 

graphMatrix = csr_matrix((data, (data_i, data_j)),shape=(len(uniques), len(uniques))) 
(numComponents, labels) = connected_components(graphMatrix) # here is the work done 
# interpret labels back to original elements 
components = [[uniques[j] for (j,x) in enumerate(labels) if x==i] for i in range(0, numComponents)] 

print(components) # [[1, 2, 3], [4, 5], [6, 7]] is printed