algorithm - 算法：具有约束 max-min<=diff 的随机分布

Question

我想随机n balls放入，但有约束m buckets

ballCountMax-ballCountMin <= diff
ballCountMax-ballCountMin as random as possible

和

Input: 
  ballCount: n
  bucketCount: m 
  allowedDiff: diff

Output: 
  ballCount distribution for buckets

有没有好的算法？

Answer 1

要分配球，只需沿着这条线走，询问一个随机数 [0, 1) 如果它小于 1/（剩余的总桶数）将一个球放入垃圾箱并移动到下一个垃圾箱。如果在此结束时，您仍然有球剩余，请评估垃圾箱之间的差异，如果垃圾箱之间的距离与允许的距离一样远，则忽略本次通过的最大垃圾箱。通过找到最小值并忽略任何球来执行此操作，而不是minimum+difference-1重复此过程，直到您分发完所有球。

该算法的复杂性取决于球的数量 (n) 和桶的数量 (m)。它的复杂度为O(mn).

我们可以通过意识到每个桶必须包含一定的最小数量的球来显着加快这一速度，例如有 5 个桶和 10 个球，相差 2 每个桶必须至少有 1 个球。因此，在执行主算法之前，我们可以通过将球“预先放置”到每个桶中来节省一半的运行时间。

要计算可预先放置的球的数量，我们只需将球的数量除以桶的数量，n/m然后取它的地板和天花板，这样a = ceiling(n/m)和b = floor(n/m)

现在b应该是每个桶 iff 可能的最小球数a-b = diff。如果等式最初不是真的，有很多方法可以解决这个问题，例如

while(a-b<diff){
  ++a;
  --b;
}

请注意，在所有情况下，此方法都会返回不正确的结果，因此添加一个a-b = diff必要的检查。

因此，我们可以预先放置b球。

Answer 2

最简单的方法是生成和测试循环：

do {
    distribute_balls_at_random();
} while (constraint_not_satisfied())

可能还有其他更有效的方法，但这将是最容易编码的。

Answer 3

以下是O(n)算法diff <= 1：

• 使用Modern Fisher-Yates shuffle 洗球
• 现在使用简单的除法散列h(k) = k mod m将 n 个球分配到 m 个桶中

如果diff，则为 0，n mod m == 0否则为 1。

Answer 4

function do(int n, int m, int diff){
      buckets = array of size m with initial values = 0
      while(n-- > 0){
          int limit = 1000;
          while(limit > 0){
              int idx = random number from 0 to m
              buckets[idx]+=1
              int min = min_element(buckets)
              int max = max_element(buckets)
              if(buckets[max] - buckets[min] <= diff) break
              buckets[idx]-=1
              limit--
          }
          if(limit == 0){
              int min = min_element(buckets)
              buckets[min]++;
              int max = max_element(buckets)
              if(buckets[max] - buckets[min) > diff)
                  return false; //there is no valid distribution
          }

      }
      print buckets
      return true
}

limit 是您可以根据需要调整的参数。更大的值确保更多的随机性，更少的值确保更好的性能。您可以尝试许多测试用例并得出最适合您的值。