使用 python 将列表/数组拆分为平衡的子列表，其中子列表中的每一对都具有最小指定差异

Question

我正在尝试在 python 中获取一个浮点数列表或数组，并将它们分成最小（ish）数量的块，以便每个块中每个元素之间的最小成对间距高于某个阈值。

我看到过类似的问题here，但我觉得这个问题有细微的不同，我想在过程结束时平衡每个块的大小，并且每个元素的距离需要成对比较到所有其他元素而不仅仅是相邻的元素。

这是我尝试过（并陷入困境）的示例工作流程：

import numpy as np
import matplotlib.pyplot as plt

# An example list of floats
lst = [1,2,3,3.3,3.5,3.9,4,5,6,8,10,12,13,15,18]
lst.sort()
lst=np.array(lst)

接下来我会抓取所有元素，这些元素与所有其他元素的成对距离是可以接受的，基于一些距离

threshold

。为此，我将生成一个差异矩阵，并选择成对距离之和不是

nan

.

的行（或列）

threshold = 1
diff = np.subtract.outer(lst, lst)
matrix = np.abs(diff)
#We don't care about the diagonal so set to any value that's not nan
matrix[matrix==0] = threshold 
#Highlight the pairs with distances below the threshold
matrix[matrix<threshold] = np.nan 

这是我在这里使用的距离矩阵：

plt.figure()
plt.imshow(matrix)

在这一点上，我有一个理想化的块和一组剩菜。

ideal_indices = matrix.sum(axis=1)>0
ideal_chunk = lst[ideal_indices]
remainders = lst[~ideal_indices]

print('Idealised chunk: ', ideal_chunk)
print('Remainders ', remainders)

出局：

Idealised chunk:  [ 1.  2.  5.  6.  8. 10. 12. 13. 15. 18.]
Remainders  [3.  3.3 3.5 3.9 4. ]

然后我会考虑找到一种方法将每个余数与理想化块进行比较，并进一步拆分理想化块以合并（但保持分离）余数。

是否有更有效的方法来完成整个过程，因为感觉我可能已经过分追求一级简单方法，请记住，这几乎肯定是一个 NP-hard 问题。

任何指针或链接将不胜感激！