公平なランダム

質問

重複のないｎ個の配列を作成する、効率がよくて高速なランダム発生プログラムを探しています。
　現在は下記のようなロジックを組んでいます。

　　１．ｎ個の配列を用意（ｎはパラメータで与えられる）
　　２．配列に１からｎまでの数値を昇順に格納
　　３．ランダムな値ｘを生成し、配列の１番目とｘ番目を交換
　　４．ランダムな値ｘを生成し、配列の２番目とｘ番目を交換
　　　　　　：
　　　　　　：
　　５．ランダムな値ｘを生成し、配列のｎ番目とｘ番目を交換

　この方法を越えるものはないでしょうか。
　条件は、効率（公平性）がこれよりも高くて、速度が O(2n) を超えないことです。
　最終的に配列の先頭２０個程度の効率が高くなっていればよく、それ以降は多少偏りがあっても構いません。

　ちなみに現在は、単純に x = rand(n); という方法で生成しており、初期化関数は使っていません。

　よろしくお願いします。

回答No.2

neKo_deux · ベストアンサー

良くあるのは、

１．ｎ個の配列を用意（ｎはパラメータで与えられる）
２．配列に１からｎまでの数値を昇順に格納
３．配列にランダムな値ｘを格納
４．配列をｘでソート
５．並べ替えられた１からｎの数字を取り出し

ですね。
高速なソートを行えば、早いハズ。

> 速度が O(2n) を超えないことです。

何のオーダーなのかわかりません。
交換の処理回数が２ｎ、ランダムな値の生成回数が２ｎ、評価の回数が２ｎ、ボトルネックになるのをどの処理と定義するかによります。

--
> 最終的に配列の先頭２０個程度の効率が高くなっていればよく、

20個以上は必要ないという事でしたら、棄却法のような方法が良いかも。

１.ランダムに１からｎの範囲の数を生成。
２.既に格納されている値なら１へ。
３.格納数が20になるまで繰り返し。

ｎが十分大きければ、ほぼ20回で処理が終了するハズ。
逆に、ｎが21とかですと、なかなか決まりません。

補足

ありがとうございます。

　ランダムな数値をさらにソートするというのは面白い方法ですね。たしかに効率はよくなりそうですね。
　ちなみにオーダーは、配列を１からｎまで一通りの「生成、評価、交換」を行ったところで O(n) であるというつもりでした。

　ちなみに棄却法は試したんですが、２０番目以降のデータも「いちおーそれっぽく」入れ替わっている必要がある関係で、実行したらあっさりハングアップしました(笑)（いつかは返ってくるんでしょうけど(^_^;）

回答No.4

UKY

乱数が一様に分布し、乱数発生に掛かるコストは一定という仮定の元で、

1. 配列の要素を1～nでそれぞれ初期化する。
2. 1～nの乱数Rを取り出し、R番目とn番目の要素を入れ替える。
3. 1～n-1の乱数Rを取り出し、R番目とn-1番目の要素を入れ替える。
4. 1～n-2の乱数Rを取り出し、R番目とn-2番目の要素を入れ替える。
(中略)
n. 1～2の乱数Rを取り出し、R番目と2番目の要素を入れ替える。

完全に公平で、オーダーは O(n) になります。
また、nの値がある程度大きければ、全ての要素を入れ替えずに6～7割入れ替えた時点で終わりにしてしまってもそれなりにランダムになっていると思います。
なお、上のアルゴリズムでは配列の後ろの方から値を入れ替えるようになっているので、必要に応じて適宜修正してください。

お礼

ありがとうございます。

　俺の作ったロジックはある程度公平だったんですね。
　よかったよかった。

回答No.3

ymmasayan

ｎ個の間、データをダブらせないためには次のようにします。
１．１～ｎの乱数（ｘ）を作り、ｘとｎを交換します。
２・１～ｎ－１の乱数（ｘ）を作り、ｘとｎ－１を交換します。
これを繰り返していきます。
ｘが出力系列です。

お礼

ありがとうございます。

　なんか難しくなってきましたね(^_^;
　これも試してみますね。

回答No.1

ymmasayan

大体いいと思いますが、同じデータが出てくるのは構わないのでしょうか。
これを防ぐ方法もありますが必要あれば言ってください。

お礼

ありがとうございます。

　重複があったらダメです。
　システムの都合上、データが壊れるんです(^_^;
　よろしくお願いします。