または配列をシャッフル

ある範囲(たとえば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]
		1	2	3	4	5	6	7
i	j
6	1	1	7	3	4	5	6	2
		未						済
5	4	1	7	3	4	6	5	2
		未					済
4	0	6	7	3	4	1	5	2
		未				済
3	3	6	7	3	4	1	5	2
		未			済
2	1	6	3	7	4	1	5	2
		未		済
1	0	3	6	7	4	1	5	2
		済

上記では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

こう変えて、結果

123	1665884
132	1667793
213	1665931
231	1666056
312	1667340
321	1666996

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

実装上の誤り

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

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

を

j = Int(i * Rnd)

の結果

123	3334715
132	0
213	0
231	3331656
312	3333629
321	0

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

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

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

を

j = Int(3 * Rnd)

の結果

123	1667208
132	1668235
213	1665363
231	1667749
312	1666487
321	1664958

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

余談

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

参考

https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%83%E3%82%B7%E3%83%A3%E3%83%BC%E2%80%93%E3%82%A4%E3%82%A7%E3%83%BC%E3%83%84%E3%81%AE%E3%82%B7%E3%83%A3%E3%83%83%E3%83%95%E3%83%AB

https://teratail.com/questions/28507

https://programming-place.net/ppp/contents/algorithm/other/002.html