python:如何将列表合并到集群中？

Question

我有一个元组列表:

[(3,4), (18,27), (4,14)]

并且需要合并具有重复数字的元组的代码,制作另一个列表,其中所有列表元素将仅包含唯一数字.列表应按元组的长度排序,即:

>>> MergeThat([(3,4), (18,27), (4,14)])
[(3,4,14), (18,27)]

>>> MergeThat([(1,3), (15,21), (1,10), (57,66), (76,85), (66,76)])
[(57,66,76,85), (1,3,10), (15,21)]

我理解它类似于层次聚类算法,我已经读过了,但无法解决它们.

是否有一个相对简单的MergeThat()函数代码？

Answer 1

我努力想到这一点,但只有在我尝试了Ian的答案之后(谢谢!)建议我意识到理论问题是什么:输入是边缘列表并定义图形.我们正在寻找此图的强连接组件.这很简单.

虽然你可以有效地做到这一点,但实际上没有理由自己实现它!只需导入一个好的图库:

import networkx as nx

# one of your examples
g1 = nx.Graph([(1,3), (15,21), (1,10), (57,66), (76,85), (66,76)])
print nx.connected_components(g1) # [[57, 66, 76, 85], [1, 10, 3], [21, 15]]

# my own test case
g2 =  nx.Graph([(1,2),(2,10), (20,3), (3,4), (4,10)])
print nx.connected_components(g2) # [[1, 2, 3, 4, 10, 20]]