)
１．はじめに
Ｘ（旧Twitter）でシャッフル処理の話題があり、高速にシャッフルする方法について考察した結果をメモしておきたいと思います。今回は（も）ネットでググったり、ＡＩに聞いたりせずに自力で検討を進めました。
自力で検討した場合、「車輪の再発明」になってしまうかもしれませんが、思考過程を楽しみたいこと及び、ググった場合はその手法に捕らわれて思考の広がりが制限されてしまうことを避けたいためです。
２．物理的なシャッフル操作
もともとのお題としてはトランプのシャッフル動作をプログラム化することが話の発端です。具体的には一山のトランプからランダムに一枚を選び、そのカードをトランプの山から取り除き、一列に並べていくという動作を繰り返すことでシャッフルされたカードの列を作り出すというものです。
３．トランプ操作とは異なるシャッフル方法
前項で書いたトランプの操作は直感的にも偏りなくランダムに並べ替えられることが直ぐに判りますが、下記の「シャッフル処理１」でシャッフルしても、確率計算してみると均等にシャッフルできることに気が付きました。尚、下記の処理では0から9までの10個の配列要素をシャッフルしています（以降の処理も同様）。
| ||
| ※RND(1)*N は自動的に整数変換された結果 0..N-1 の範囲の整数になる、SWAPは変数の値を交換する処理 |
更に下記の「シャッフル処理２」の結果も確率計算してみると偏りなくランダムに並べ替えられるので、配列要素に連番を設定するループとシャッフルするためのループを同一にできました。
| ||
４．シャフル処理の改善
上記の「シャッフル処理２」ではループ処理の最初の I=0 の時に A(0) と A(0) を入れ替えているので無駄な乱数発生を行っていることになります。このことからＮ個の要素をシャッフルするには（Ｎ－１）回の乱数発生を行えばいいことが判ります（上記２項の「物理的なシャッフル操作」の場合も同数の乱数発生が必要ですね）。変数の初期値が零であることを利用して乱数発生回数を最小限になるように「シャッフル処理２」を改善した処理が下記になります（Iの初期値を1に変更）。
| ||
しかし、上記の処理は A(0) が零であることを前提にしているので、そのままでは再度シャッフルできないという欠点があります。
そこでシャッフル処理だけに特化した下図の処理を考えました。これならば何度でもシャッフルすることが可能で、当然ですがシャッフル対象も連番である必要がないので汎用的なシャッフル処理として利用できます。
| ||
| ※Ｎはシャッフル対象要素の個数 |
５．フィッシャー・イェーツのシャッフル
Ｘのコメントで教えて頂いたのですが「フィッシャー・イェーツのシャッフル」というシャッフル処理があります。ネットで「高速なシャッフル処理」を検索すると最初に出てきました。処理内容は上記２項に書いた「物理的なシャッフル操作」を効率よく行う処理になっています。計算量は上記の「汎用化したシャッフル処理」と同等で O(N) オーダーであり、高速です。
| ||
| ※ウィキペディアより引用 |
６．あとがき
ひょんなことからシャッフル処理の検討が始まり、現在最速と思われるフィッシャー・イェーツのシャッフルと同程度の速度で処理内容の異なるシャッフル処理まで辿り着きました。今回のような検討のトリガが得られるのもＸの醍醐味ではないかと思います。また、安易にネット検索やＡＩに聞かないことで思考の過程を楽しむことができました。
尚、今回辿り着いたシャッフル処理を skyriverのシャッフル と命名しますｗ
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}