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