1

の順列を生成したいのですが、などarray aの効用関数を使用したくありませんjava.util.Collections()。
順列はランダム化する必要があり、すべての順列が発生する可能性がありますが、均等に分散された確率は必要ありません。

次のコードはこれを実現しますが、パフォーマンスは低下します。

// array holding 1,...,n
// initialized somewhere else
int[] a = new int[N];

for (int i = 0; i < a.length ; i++) {
     int r = (int) (Math.random() * (i+1));     
     swap(r,i,a);
  }

private static void swap(int j, int k, int[] array){
      int temp = array[k];
      array[k] = array[j];
      array[j] = temp;
}

質問：
順列の生成に使用される乱数の総数を減らす可能性はありますか？

4

3 に答える 3

4

誰かがクヌースシャッフルを改善したら、私は驚かれることでしょう。O（n）です。

O（n）の乱数が必要ですが、これでは不十分です。

この引用は、O（n log n）アルゴリズムを主張しています。

O（log n）またはO（1）を見てみたいです。

O（log n）アルゴリズムは通常、「分割統治」二分法に依存します。これにより、デッキを切り取り、各半分を分割することが思い浮かびます。

しかし、もっと速いアルゴリズムにアクセスできれば、クヌースはそれを見つけたはずだと思わずにはいられません。

于 2009-11-14T15:47:24.973 に答える
2

長さnのシーケンスにはnがあります！順列。それぞれの灌流が可能である必要がある場合、それぞれに可能な乱数のシーケンスがなければなりません。

したがって、長さnの配列をランダムに並べ替えるには、1..nの範囲から単一の乱数を生成できます。ランダムに均一に。これにより、単一の順列が識別され、それを適用できます。

質問を改善して、必要なランダムビットの数を尋ねることができます。同じ引数で、それはlog（n！）になります。その関数の漸近的振る舞いについてのアイデアを与えるために、以下を考慮してください：

n> 3とします：

n = log（2 ^ n）<log（n！）<log（n ^ n）= n * log（n）

したがって、n個のランダムビットでは不十分です（n> 3の場合）。実際、log（n！）がO（n）にないことを証明できます。

于 2009-11-14T16:44:39.993 に答える
1

私が考えることができる唯一の可能な最適化は、乱数ジェネレーターを高速化することです。簡単な解決策は、最初にランダムなintを生成することです。

import java.util.Random;
Random rand = new Random();

for (int i = 0; i < a.length ; i++) {
    swap(rand.nextInt(i+1), i, a);
}

...

あるいは、多かれ少なかれ乱数を生成するためのより高速な方法を発明することができます（均一に分散されているかどうか、ニーズに適しています）。ただし、O（n）の制限を克服する方法はありません。

于 2009-11-14T16:13:10.710 に答える