巡回乱数 †
巡回乱数の生成方法を考え方（アルゴリズム）を交えて説明しますが乱数発生自体はシステムが提供しているものを使います。(HSPではrndに相当。)
「巡回乱数」という言葉は聞き慣れないかも知れませんが、それもそのはずkz3が先ほど勝手に命名しました。
俗にいう「重複のない乱数」です。
rndで得られる乱数値は「一様乱数」と呼ばれる乱数ですが直前に得られた乱数値が続けて得られることもあります。
巡回乱数の"巡回"とは、rndで得られるある範囲内の一様乱数を（順不同で）巡回して得るということから来ています。
- 例
rndで得られる一様乱数が0〜9の時、1回目に0を得ると次回からは1〜9が得られます。
2回目で9を得ると次回からは1〜8が得られます。
そうやって全ての一様乱数を得る（巡回する）と次回は再び0〜9が得られます。
まず簡単な方法としては、得た乱数を記録しておき乱数を得るたびに過去にその乱数を得たかどうかを調べる方法が挙げられます。
|
A l g o r i t h m : はじめに・・・
|
この場合何度も既出の値を選んでしまい、特に最後の巡回乱数を得る時などは頻繁にやり直しが発生します。
- 力ずく法の実装例を見る！
はい、これがkz3が自力で閃いたアルゴリズムですが、実際には多くの方が同じような方法を思いついてるみたいです。
でも自分で閃いたので胸張って書きます。p(ﾟーﾟq
|
A l g o r i t h m : はじめに・・・
|
要素を交換するとき、乱数で得た要素とランダムポイントの要素と重なる場合がありますがアルゴリズムを単純にするために処理を省いています。 このアルゴリズムの巡回乱数を得る時間計算量はO(1)ですが、具体的にはシステム定義の乱数発生機の計算量に依存するということです。
- 追い出し法の実装例を見る！
発生させる全ての乱数値を配列の要素に設定し、配列要素をシャッフルさせ、順番に配列の要素を取り出す方法。
力ずく法・追い出し法が乱数発生時に発生させるべき数値を決めているのに対し、この方法はシャッフルした時点で将来発生させる数値が決まっています。
この方法をここでは便宜的にシャッフル法と呼ぶことにします。
|
A l g o r i t h m : はじめに・・・
|
著者(eller)が独自に考えたアルゴリズムですが、簡単なため他の方のアイデアと重複しているかも知れません。
- シャッフル法の実装例を見る！
- シャッフルについてはModule/配列要素のシャッフルおよびアルゴリズム/トランプを参照。
- 乱数の性能は検定してみないとわからないと思いますが、、検定はしないの？
- 旧「配列要素のシャッフル」を文書化中です。 -- kz3 2005-11-10 (木) 13:25:00
- 追い出し法を考えていたときの様子は脱力さんが覚えているかもです。 -- kz3 2005-11-10 (木) 15:27:14
- HSPの書籍に載ってる「スワップ法」はシャッフルであって巡回乱数とは関係ありませんでした。 -- kz3 2005-11-10 (木) 15:32:00
- 文章のおかしいところがないかチェック。 -- kz3 2005-11-10 (木) 17:44:05
- やっぱり実装例もないとアカンですよね？´ﾛ` -- kz3 2005-11-10 (木) 17:47:18
- まぁ上の箇条書きをソースにするだけなんですが･･･ -- kz3 2005-11-10 (木) 17:50:31
- ソースは小ワザとかModuleとかに書けばいいのでは？？ -- Charlotte 2005-11-10 (木) 17:56:25
- なるほど、小ワザでソース、アルゴリズムの解説はこっちでっと・・・。 -- kz3 2005-11-10 (木) 18:07:29
- 実に1年以上ぶりの更新。実装例は後日追記いたします。 -- eller 2007-05-29 (火) 22:10:00