Fisher–Yates shuffleとは、例えば順番に並んでいる配列(JavaScriot)

というようにランダムにバラバラの配置にしたい。という時に使うアルゴリズムです。

コンピュータの使用を想定しリチャード・ダステンフェルドの改良版が今よく見るFisher–Yates shuffleのようです。

実装は改良版で、

配列の最後から順番にランダムに数字をえらんでその数字と、ランダムな数字のインデックスの数字を入れ替えます。どんどん前の数字がfor文で選ばれていくのでランダムに選ぶ数字も限られていきます。配列の最後まで行くと終了です。

pythonで実装してみます。

import random

arr = [1,2,3,4,8,9]

for i in reversed(range(len(arr))):
    j = random.randint(0,i)
    [arr[i], arr[j]] = [arr[j], arr[i]]

print(arr)

 ランダム関数を使うためにインポートしておきます。

配列を変数に入れて準備完了。

for 文で繰り返し入れ替え作業を行います。

reversed()で逆方向にします。この場合は配列の後ろ"9"の方向から前に進めていきます。

range()で範囲を指定します。

len(arr)範囲は"arr"配列の長さを取得しています。

ランダムな数字を発生させます。これは0から"i"までの数字を使うように指定しています。こうすることで後ろから選べる数字が順番に短くなっていきます。

最初は 1,2,3,4,8,9  次は1,2,3,4,8　その次は1,2,3,4　という感じ。

ここからがシャッフルの仕組み、入れ替えを行うコード。

このランダムな数字"j"と最後の数字"i"と入れ替えることでシャッフルします。

これで完了。

参考

pyhonの関数を使うと簡単にシャッフルできます。

import random

arr2 = [1,2,3,4,8,9]

random.shuffle(arr2)

print(arr2)