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 的回答(谢谢!)的方法后，我才意识到理论问题是什么:输入是一个边列表并定义一个图。我们正在寻找该图的强连通分量。就这么简单。

虽然你可以 do this efficiently ，实际上没有理由自己实现!只需导入 good graph library :

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]]