重複なしの乱数発生について、本来ならば一度発生した乱数を配列に登録していき、すでに登録されている乱数が発生されればその乱数は破棄する等の手順をとりますが、そうすると、必要な乱数の数よりも多い計算回数を必要とします。
そこで、乱数発生の数を必要な数と同じにし、判定の手順も必要としないアルゴリズムを考えてみました。
下記の例題にて、
int round_tbl[RAND_N]; // 変換テーブル
は、発生した乱数を使われていない値に変換するためのテーブルであり、必要な乱数の数(RAND_N)を次第に減らしていくために利用しています。
全ての値が発生すれば、必要な乱数の数は 0 になります。
このアルゴリズムでは、変換テーブル用の配列の準備が必要となります（その分のメモリが必要）。
乱数を発生する数は、必要な乱数の数と同じであり、不必要な乱数を破棄することはありませんので、高速なアルゴリズムになります。
例題では、通常のアルゴリズムと比較した時間も表示しています。
10000 の数を発生する際には16倍程度高速になっています。 図解begin
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
｜０｜１｜２｜３｜・・｜ｎ−１｜ → n個の配列
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
最大 n の乱数を発生 val=2 → 配列から 2番目の値を抜き出し、抜けた分を詰める
＿＿＿＿＿＿＿＿＿＿＿＿＿＿
｜０｜１｜３｜４｜・｜ｎ−１｜ → n-1個の配列
￣￣￣￣￣￣￣￣￣￣￣￣￣￣
最大 n-1 の乱数を発生し、上記と同じように発した値の配列を抜き出し、抜けた分を詰める
以下、配列がなくなるまで繰り返す
図解end
クラス化し、必要な値だけ取り出すように変更した例は こちら
実行結果
投稿
line 66で、結果、val == rn-1 の場合、変換テーブルの更新は不要だと思いますが？？？
返信削除仰るとおり、
削除if ( val != rn-1 ) {
for ( i=val; i<rn; i++ ) round_tbl[i] = round_tbl[i+1];
}
で大丈夫ですね。また修正しておきます。
<2013年10月21日 17:25> の者です。
削除ほんとクールなコードですね。
こちらを見つけるまで、先頭からちくちく探索していました。
どうもありがとうございました。