从成对组合中识别集合

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