将值分成分布相似且大小均匀的组

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

- tmakino

---

你能具体说明一下分组的大小应该如何均匀，以及它们的分布应该有多相似吗？ - m.raynal

每个组应该有 floor(num_values / K) 个元素，除了一个包含余数的组。分布应尽可能相似。 - tmakino

顺便提一下，由于你使用类似Python的伪代码，你的伪代码的Python等价代码是[sorted(values)[i::k] for i in range(k)]。 - jferard

Answer 1

这里有一种（某种程度上）均匀分布值的方法。 假设您的标量数组 A 的大小为 n，其中 n 是 k 的倍数，以使其更简单。 一种方法可能是：

sort(A)
d = n/k
g = 0
for i from 0 to d-1 do {
  for j from 0 to k-1 do {
    group[(j+g) % k].add(A[k*i + j])
  }
  g ++
}

你需要将前k个元素添加到组1，...，k中，接下来的k个元素添加到组2，...，k，1中，然后是3，...k，1，2等。如果k² > n，则它不会很好地工作，在这种情况下，您不应该将g增加1，而应该增加一个接近k/d的较大值。如果k几乎等于n，那么此算法变得无用。

如果A中存在一些极端值，则此方法绝对不能保证标量均匀分布。但是，如果A本身在某种程度上分布良好，并且n > k²，则它会在k个组之间分配值。

一旦排序了A，它至少具有以O(n)运行的优点。

- m.raynal

---

谢谢你的好主意。我注意到如果A = [1, 2, 3, ..., n]，那么你的方法具有这样的属性：在每次将k个元素添加到k个列表中的迭代结束时，这些列表的总和相等。这是你的意图吗？ - tmakino

这不是我的本意，我在写伪代码时意识到了这一点。由于子集和问题是 NP 完全的，我只是采用了朴素和直接的方法来解决问题，以得到一个高效的方法。 - m.raynal

Answer 2

这是对@m.raynal的改进，即使n只是k的相当小的倍数，也能很好地工作。

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

实际上，这意味着前k个元素随机分配到组中，接下来的k个元素按相反顺序排列。然后它聪明地保持平衡。

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

- btilly

---

我会称其为一种改进而不是变化，这实际上比我提出的要聪明得多。它将更好地分配物品，成本为 O(n.log n)，这个成本已经在排序时支付了。 - m.raynal

谢谢您提供这个有效的方法。然而，我不理解您所说的“中间向外”的评论。如果指定数据分布，这种方法是否可以改进？我的数据是双峰的，大致在0到1之间，其中大部分（约80％）的数据要么接近于0，要么接近于1，其余部分均匀分布在两者之间。 - tmakino

@tmakino 想象一下，如果您的数据是正态分布的，那么每个人左侧尾部的最后2个值的分布会明显奇怪。在中间向外的方法中，您会从中间分配值，然后来回反弹，为每个人添加一个高于中间值的值，一个低于中间值的值。然而，对于像您描述的双峰分布，这种方法没有任何意义。 - btilly