算法：约束最大值<最小值=差异的随机分布

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/（剩余总桶）将球放在垃圾箱中，然后继续进入下一个垃圾箱。如果在此结束时，您仍然剩下球，请评估垃圾箱之间的差异，如果垃圾箱与允许的bin相距遥远，而bin却忽略了该通行证的最大值。通过找到最低限度并忽略所有球，而不是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

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

• 用现代的费舍尔 - 耶茨随机洗牌
• 现在使用简单的部门哈希 h(k) = k mod m将n球分配到m桶

如果n mod m == 0，则diff为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
}

限制是您可以根据需要进行调整的参数。更大的值确保更多的随机性和更少的值确保更好的性能。您可以尝试许多测试用例，并以适合您的最佳价值出来。