python– 将任意数据数组分组为N个bin

概述我想将任意大小的随机值数组分组为n个组,这样任何一个组/ bin中的值之和尽可能相等.因此,对于值[1,2,4,5]和n = 2,输出桶应为[sum(5 1),sum(4 2)].我遇到的一些可能性：>完全详尽的广泛搜索>具有硬编码的停止条件的随机过程>从排序数组的一端开始,分组直到总和等于全局平均值,然后移动到下一个组,直到达到n似乎最优

我想将任意大小的随机值数组分组为n个组,这样任何一个组/ bin中的值之和尽可能相等.

因此,对于值[1,2,4,5]和n = 2,输出桶应为[sum(5 1),sum(4 2)].

我遇到的一些可能性：

>完全详尽的广泛搜索
>具有硬编码的停止条件的随机过程
>从排序数组的一端开始,分组直到总和等于全局平均值,然后移动到下一个组,直到达到n

似乎最优解(在给定输入数组的情况下,二进制位的内容之和尽可能相等)可能是非平凡的;所以目前我倾向于最后一个选项,但感觉我可能错过了更优雅的解决方案？最佳答案这是NP难问题.换句话说,在不探索所有组合的情况下找不到最佳解决方案是不可能的,组合的数量是n ^ M(其中M是数组的大小,n是bean的数量).这是一个非常类似于clustering的问题,它也是NP难的.

如果您的数据集足够小,可以使用强力算法(探索所有组合).

但是,如果您的数据集很大,那么您需要一个多项式时间算法,它不能为您提供最佳解决方案,但需要很好的近似.在这种情况下,我建议你使用类似于K-Means的东西……

步骤1.计算每个箱的预期总和.设A是你的数组,然后每个bin的预期总和是SumBin = SUM(A)/ n(数组中所有元素与二进制数之和的总和).

第2步.将数组的所有元素放在一些我们称之为The Bag的集合(例如另一个数组)中(这只是一个概念,所以你理解了下一步).

步骤3.将Bag分成n组(最好是随机的,这样每个元素最终以某个bin i结束,概率为1 / n).此时,你的垃圾桶里有所有的元素,而且这个垃圾袋是空的.

步骤4.计算每个bin的总和.如果结果与上次迭代相同,则退出. (这是K-Means的预期步骤)

步骤5.对于每个bin i,如果其总和大于SumBin,则选择大于SumBin的第一个元素并将其放回The Bag中;如果它的总和小于SumBin,选择少于SumBin的第一个元素并放回The Bag中.这是K-Means的梯度下降步骤(又称最大化步骤).

步骤6.转到步骤3.

这个算法只是一个近似值,但它很快并且保证收敛.

如果你对如上所述的随机算法持怀疑态度,在第一次迭代后回到第3步,而不是随机分配元素,你可以通过运行Hungarian algorithm来做到最佳,但我不确定这会更好地保证 – 所有结果. 总结

以上是内存溢出为你收集整理的python – 将任意数据数组分组为N个bin全部内容，希望文章能够帮你解决python – 将任意数据数组分组为N个bin所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。