ある範囲から重複無しかつランダムに全部取り出す

スポンサーリンク
スポンサーリンク

または配列をシャッフル

ある範囲(たとえば1-7)を重複なし(1122334とかじゃない)かつランダム(4635271とか)に全部(1-7だったらその範囲を一個ずつ全部)取り出したい。くじ引きとかおみくじのサンプルプログラムはよく見るんだけど、どれか1個みたいな感じなのでちょと違う。探したらそればっかり出てきてめんどくさかった。なんやかんやあってフィッシャー–イェーツのシャッフルという方法を見つけた。テトリスのテトリミノが落ちる順番がそんな感じらしく、どういうプログラムなんだろーと興味が湧いたのがきっかけ。7-bagっていうんだって。

スポンサーリンク

フィッシャー–イェーツのシャッフル

詳しくはWikipediaとか。下は紙とペンの方法らしいけど、それはすっ飛ばしてダステンフェルド、クヌースの方法を試してみたい。

要素数が n の配列 a をシャッフルする(添字は0からn-1):
i を n – 1 から 1 まで減少させながら、以下を実行する
j に 0 以上 i 以下のランダムな整数を代入する
a[j] と a[i]を交換する

こんな。Wikipediaに書いてあることの繰り返しだけど1回自分でやってみないとよく分からんので表にしてみる。各iの終了時の配列の状態で、jは適当。

a
初期配列(n=7)[0][1][2][3][4][5][6]
1234567
ij
611734562
541734652
406734152
336734152
216374152
103674152

上記ではi = 3 = jなのでこの時は交換しない。というかa[i=3]とa[j=3]で交換してるといえばいいのかな?あとi = 1のときj = 0 or 1なのでここで終了になる。ふむふむ。

スポンサーリンク

ExcelVBAで書く

ちょこちょこっと書ける環境が現状VBAしか無いんだぜ。

Sub FYShuffle()

    Dim arr As Variant
    arr = Array(1, 2, 3)
    
    arr = shuffle(arr)
    Debug.Print arr(0) & arr(1) & arr(2)

End Sub
Function shuffle(a As Variant)

    Dim j As Integer
    Dim t As Integer

    For i = UBound(a) To 1 Step -1
        Randomize
        
        j = Int((i + 1) * Rnd)
        
        t = a(j)
        a(j) = a(i)
        a(i) = t
    Next i
    
    shuffle = a

End Function

1-7だと7!の組み合わせで5040通りとかなので1-3でやった。結果

231
231
213
312
321
321
231
321
231
231

大丈夫かな?検証してみる。

検証

    For i = 1 To 1000000
        For j = 1 To 10
            arr = shuffle(arr)
            Cells(i, j).Value = arr(0) & arr(1) & arr(2)
        Next j
    Next i

こう変えて、結果

1231665884
1321667793
2131665931
2311666056
3121667340
3211666996

うん、これで合ってるのかな?試しにWikipediaにあった、実装上の誤りの方を試してみる。

実装上の誤り

“取得する乱数の範囲を誤ってしまう”

j = Int((i + 1) * Rnd)

j = Int(i * Rnd)

の結果

1233334715
1320
2130
2313331656
3123333629
3210

おお、全然っすね。円順列!

“インデックス j を常に「配列のすべて」から取得する”

j = Int((i + 1) * Rnd)

j = Int(3 * Rnd)

の結果

1231667208
1321668235
2131665363
2311667749
3121666487
3211664958

あれ?なんかそうでもないような気がする。なんでだろ、まぁいいか。

スポンサーリンク

余談

作りたいものがうまく作れないので、ちょっと時間をおこうと思い他のものに手を出してはまた作れずっていうのが続いててなんかヤダ。今も行き詰まってる。何しよっかなー。

スポンサーリンク

参考

フィッシャー–イェーツのシャッフル - Wikipedia
C言語で重複しない乱数生成の仕方を教えてください!|teratail
C言語で乱数を生成するときに、例えば1~10の乱数を生成するとして、 includeincludeint main() {     int x;   &nb
ランダムシャッフル | Programming Place Plus アルゴリズムとデータ構造編【その他のアルゴリズム】 第2章
スポンサーリンク
のーと
スポンサーリンク
スポンサーリンク
スポンサーリンク
dalomo

コメント

タイトルとURLをコピーしました