寻找簇间距离最小的两个簇

Question

我有一个解决方案集群的列表，格式如下：

输入：

test = []

# solutions, centroid
test.append([[3,5],4])
test.append([[2,8],5])
test.append([[1,3],2])
test.append([[5,9],7])

Out：[[[3, 5], 4], [[2, 8], 5], [[1, 3], 2], [[5, 9], 7]]

我将如何返回所有星系团中质心距离最小的两个星系团的联合？

目标产出：[[2,8,3,5],4.5]

联合组中解决方案的顺序与此无关。

我花了相当长的时间试图想出一个有多个循环的解决方案，但没有结果。

Answer 1

你可以用两个for-loop

res = []
for t1 in test:
    for t2 in test:
        if t1 != t2:
            res.append([t1[0]+t2[0], (t1[1]+t2[1])/2])
  
# Or as one-line          
res = [[(t1[0]+ t2[0]), (t1[1]+t2[1])/2] for t1 in test for t2 in test if t1 != t2]

输出：

>>> sorted(res, key=lambda x: x[1])[0]
[[3, 5, 1, 3], 3.0]

>>> sorted(res, key=lambda x: x[1])
[[[3, 5, 1, 3], 3.0],
 [[1, 3, 3, 5], 3.0],
 [[2, 8, 1, 3], 3.5],
 [[1, 3, 2, 8], 3.5],
 [[3, 5, 2, 8], 4.5],
 [[2, 8, 3, 5], 4.5],
 [[1, 3, 5, 9], 4.5],
 [[5, 9, 1, 3], 4.5],
 [[3, 5, 5, 9], 5.5],
 [[5, 9, 3, 5], 5.5],
 [[2, 8, 5, 9], 6.0],
 [[5, 9, 2, 8], 6.0]]

Answer 2

您可以计算所有距离(基本上所有组合为2乘2)，并根据最小的距离对它们进行排序，它们加入列表(下面的代码假设为您在问题中定义的test )：

from itertools import combinations

best_pair = sorted([(abs(el1[1] - el2[1]), el1, el2) for el1, el2 in combinations(test, 2)])[0]
result = [best_pair[1][0] + best_pair[2][0], abs(best_pair[1][1] + best_pair[2][1])/2]

如果有太多的集群，可以进行优化，因为上面的算法在时间和内存上都是二次的。