algorithm - 将值拆分为分布相似、大小均匀的组

Question

给定一个标量值列表，我们如何将列表分成 K 个大小均匀的组，以使这些组具有相似的分布？请注意，简单性比效率更受欢迎。

我目前正在做:

sort values
create K empty groups: group_1, ... group_k
while values is not empty:
    for group in groups:
        group.add(values.pop())
        if values is empty:
            break

Answer 1

这是 @m.raynal 提出的变体，即使 n 只是 k 的相当小的倍数，它也能很好地工作。

1. 将元素从小到大排序。
2. 创建 k 个空组。
3. 将它们放入 Priority Queue从最少元素到最多元素排序，然后从最大总和到最小元素排序。 (因此下一个元素始终是所有元素最少的元素中总和最大的那个。)
4. 对于每个元素，从优先级队列中取出一组，添加该元素，将该组放回优先级队列中。

在实践中，这意味着前 k 元素随机分组，接下来的 k 元素以相反的顺序排列。然后它在保持事物平衡方面变得聪明。

根据您的应用程序，底部两个值按预期间隔很远的事实可能是个问题。如果是这种情况，那么您可以通过“中间出”来使事情复杂化。但该方案要复杂得多。