algorithm - 将数组划分为具有最小总方差的子集的算法

Question

我有一个浮点数数组，我想将该数组分成两个子集，以使它们的总方差最小化。

总方差定义如下：

var = (var_1 * n_1 + var_2 * n_2)/(n_1 + n_2)

其中n_1和n_2分别是左/右元素的数量， 和 分别var_1是var_2左/右方差。

我的问题是：是否有任何有效的算法来找到总方差的全局最小值？该算法应该输出两个子集，每个子​​集都包含相应组的元素。

此外，假设每个元素都是一个 tuple (x,y)，而不是方差，我想找到左右的全局协方差，以与上面类似的方式定义。是否有一些通用算法来处理此类分区问题？我想这应该更难，因为我能想到的所有算法都需要对数组进行排序，但是这里没有明显的比较器来对元组进行排序。

标签： algorithmpartition