読者です 読者をやめる 読者になる 読者になる

重複のない乱数発生のアルゴリズムを考えてみた

重複のない乱数を作る

重複のない乱数を発生させるアルゴリズムを考えてみた。まあ、ちょこっとggったらスマートなやつが見つかるとは思ったけど、自分で考えるというのが大事だと思ったのですよ。

素人丸出しのやり方なので、笑ってくれたらいいと思います。

考え方

ちょこっと作戦を考えてみた。

たとえば、1~10までの乱数を作るだけなら、Rnd関数を用いて、

Int(Rnd * 10) + 1

とでもすればよかろう。

問題は、これだけだと同じ数が出てきてしまうことだ。

順番をランダムに変えたいようなとき、これでは困る。

そこで、次のような手順を考えた。

  1. 10個の値を格納することができる配列を準備する
  2. 乱数を発生させる
  3. (2回目以降)発生させた値を、それまでに格納した全ての値と比べる
  4. 同じ値にぶつかったら、乱数発生をやり直して3.に戻る
  5. 一度も同じ値にぶつからずに3.を終えると、新たに配列に追加する
  6. 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

を付け加えて実行してみると、

f:id:akashi_keirin:20170514134531j:plain

無事に重複なく1~10の数字が格納されていることが分かる。

おわりに

重複のない乱数の取得なんていうのは、さんざん考え尽くされた類のものだと思うので、もっとエレガントかつスマートなやり方があると思う。

もう少し仕事に余裕があったら、本格的にアルゴリズムの勉強をするんだけどなあ。

@akashi_keirin on Twitter