重複のない乱数発生のアルゴリズムを考えてみた
重複のない乱数を作る
重複のない乱数を発生させるアルゴリズムを考えてみた。まあ、ちょこっとggったらスマートなやつが見つかるとは思ったけど、自分で考えるというのが大事だと思ったのですよ。
素人丸出しのやり方なので、笑ってくれたらいいと思います。
考え方
ちょこっと作戦を考えてみた。
たとえば、1~10までの乱数を作るだけなら、Rnd関数を用いて、
Int(Rnd * 10) + 1
とでもすればよかろう。
問題は、これだけだと同じ数が出てきてしまうことだ。
順番をランダムに変えたいようなとき、これでは困る。
そこで、次のような手順を考えた。
- 10個の値を格納することができる配列を準備する
- 乱数を発生させる
- (2回目以降)発生させた値を、それまでに格納した全ての値と比べる
- 同じ値にぶつかったら、乱数発生をやり直して3.に戻る
- 一度も同じ値にぶつからずに3.を終えると、新たに配列に追加する
- 2.に戻る
このやり方でできると思った。
実装
リスト1
Dim qNumbers() As Integer '……(1)' ReDim qNumbers(1 To cnt) Dim i As Integer Dim n As Integer Dim hasDone As Boolean Randomize For i = 1 To cnt Do qNumbers(i) = Int(Rnd * cnt) + 1 '……(2)' hasDone = True '……(3)' If i > 1 Then '……(4)' For n = 1 To i - 1 '……(5)' If qNumbers(i) = qNumbers(n) Then hasDone = False Exit For End If Next End If Loop While hasDone = False '……(6)' Next
まず、(1)からの2行、
Dim qNumbers() As Integer ReDim qNumbers(1 To cnt)
では、作成した乱数を格納する配列を用意し、要素数でReDimしている。cntというのは、要素数が入っている変数だと思ってください。
(2)の
qNumbers(i) = Int(Rnd * cnt) + 1
で、1~10までの数を1つ作り、ひとまず配列qNumbersに格納。
一旦(3)で
hasDone = True
としてフラグ用の変数をTrueにしておく。
すでに取得済みの数と比較する必要があるのは、ループの2回目以降なので、(4)の
If i > 1 Then
で、ループの1回目のみ(5)以下のForループを飛ばすようにした。
(5)以下の6行、
For n = 1 To i - 1 '……(5)' If qNumbers(i) = qNumbers(n) Then hasDone = False Exit For End If Next
が重複を防ぐためのロジック。
Forループの最終値を「i - 1」にしておかないと無限ループになるので注意w(←経験者)
1つ手前までのqNumbersの全ての要素と比較し、同じ値があったら即hasDoneをFalseにしてループを抜けるようにした。
従って、このループを無事抜けるということは、重複のない値がセットされていて、hasDoneがTrueになっているということ。
(6)では、Doループの繰り返し条件としてhasDone = Falseを指定しているので、重複のない値が取得できていないときはDoループの先頭に戻って値を取得しなおすことになる。
実行結果
cntを10にして、リスト1に
For i = 1 To cnt debug.Print qNumbers(i) Next
を付け加えて実行してみると、
無事に重複なく1~10の数字が格納されていることが分かる。
おわりに
重複のない乱数の取得なんていうのは、さんざん考え尽くされた類のものだと思うので、もっとエレガントかつスマートなやり方があると思う。
もう少し仕事に余裕があったら、本格的にアルゴリズムの勉強をするんだけどなあ。