我有一个元组列表，用于标识项目之间的成对关系。
[(1,2), (2,3), (3,1), (4,5), (5,4), (6,7)]
我想查看元组并将它们折叠成如下所示的唯一集合(可能作为 HashMap - 任何其他有效的数据结构？):
{a: (1,2,3), b: (4,5), c(6,7)}
是否有一种算法可以有效地做到这一点 - 我现在只能想到一种蛮力方法。
希望在 Python 或 R 中实现它。我的原始示例有大约 2800 万个元组。
最佳答案
你基本上想要找到连接的组件。为此，有一个函数 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
关于python - 从成对组合中识别集合，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39133511/