算法：有约束的最大最小随机分布<= 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分发ň球m个区段

的diff将为0，如果是n mod m == 0，则为1，否则为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是一个您可以随意调整的参数。更高的值确保更多的随机性，更少的值确保更好的性能。您可以尝试很多测试用例，并以适合您的最佳值出来。