1

という制約でランダム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

良いアルゴリズムはありますか？

4

4 に答える 4

3

ボールを分配するには、単純に行をたどり、乱数 [0, 1) を要求します。それが 1/(残りのバケツの合計) より小さい場合は、ビンにボールを置き、次のビンに進みます。この終了時にまだボールが残っている場合は、ビン間の差を評価します。ビンが可能な限り離れている場合は、このパスで最大のビンを無視します。これを行うには、最小値を見つけ、それ以上のボールを無視しminimum+difference-1ます。すべてのボールを分配するまで、このプロセスを繰り返します。

このアルゴリズムの複雑さは、ボールの数 (n) とバケットの数 (m) に依存します。の複雑さがありO(mn)ます。

各バケットには特定の最小数のボールが含まれている必要があることを認識することで、これを大幅にスピードアップできます。したがって、主要なアルゴリズムを実行する前に、ボールを各バケットに「事前に配置」することで、実行時間を半分に節約できます。

事前に配置可能なボールの数を計算するには、ボールの数をバケツの数で割り、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したがって、ボールを事前に配置できます。

于 2012-10-18T14:31:05.667 に答える
1

最も単純なアプローチは、生成とテストのループです。

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

はるかに効率的な方法は他にもあると思いますが、これが最も簡単にコーディングできます。

于 2012-10-18T14:37:40.013 に答える
0

を使用したO(n)アルゴリズムは次のdiff <= 1とおりです。

は、 のdiff場合は 0、それ以外の場合n mod m == 0は 1 になります。

于 2012-10-18T15:08:22.110 に答える
0 
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 は、必要に応じて調整できるパラメーターです。値が大きいほどランダム性が高くなり、値が小さいほどパフォーマンスが向上します。多くのテスト ケースを試して、最適な値を見つけることができます。

于 2012-10-18T15:16:05.330 に答える