・swap視覚化
・80本の棒のシャッフル
１．フィッシャ–イェーツのシャッフルとは
先日の授業では、シャッフルを教えてもらいました。
その中で、「フィッシャ–イェーツのシャッフル」を簡単にしたものを扱いました。そこで、フィッシャ–イェーツのシャッフルとは実際どういう動きでシャッフルしているのか知りたくて、視覚化した物を作ってみようと思って、その為に調べてみました。
- 1 から N までの数字を書く。
- まだ消されてない数字の数を数え、1 からその数以下までのランダムな数字 k を選ぶ。
- 残っている数字から k 番目の数字を消し、別の場所にその数字を書き出す。
- すべての数字が消されるまで手順 2, 3 を繰り返す。
- 手順3で書かれた数列が元の数値からのランダム順列となるとなる
というものです。
何かを訳したものだと思いますが「消されていない」「消されるまで」となっていてわかりにくいですが、これは「選ばれていない」「選ばれる」と読み換えるとわかりやすいと思います。
例えば1〜5までの数字、12345をシャッフルする場合、
⑴ 1から5までの数字を書く→12345
⑵ まだ選択されていない数字の数を数え→ここではまだ一つも選択されていないので5つ
1からその数以下までのランダムな数字kを選ぶ→1から5までのランダムな数字例えば3を選んだとする
⑶ 残っている数字（ここでは12345）から3番目の数字を選び（ここでは3）、それを結果として書き出す（シャッフルの結果の5桁の最初の数字が3となる）残った数は1245となる
⑷ ⑵⑶を繰り返す。次は二巡目なので、まだ選択されていないのは4つ、1から4までのランダムな数、また3を選んだとする
残っている数（1245）の3番目の数字（4）を選び、結果に加える。（先の3と合わせて、34となる。残った数は125となる）
これをなくなるまで繰り返す。（3巡目）3個数字が残っているので、1〜3までのランダムな数字、1が選ばれたとして125の1番目の数字、1を結果として加えて、341となり、残ったのは25。
（4巡目）2個数字が残っているので、1〜2までのランダムな数字、2が選ばれたとして、25の2番目の数字、5が選択されて、結果として加えられて3415、残った数字は2の一つ。
（5巡目）最後2という数字がが1個残っていて、ランダムな数字といっても1しかないので、1番目の数2が選択されて、結果に加えられて、最終結果は34152となる、
これがこのシャッフルの仕方です。
２．ダステンフェルドの手法
さらに、現代ではこれをコンピュータでの使用を想定して改良した、ダステンフェルドの手法が採用されているとのことです。これは
要素数が n の配列 a をシャッフルする(添字は0からn-1):
i を n - 1 から 1 まで減少させながら、以下を実行する
j に 0 以上 i 以下のランダムな整数を代入する
a[j] と a[i]を交換する
というもので、先のフィッシャ–イェーツとの違いは・・これもnを5としてやってみたらわかるでしょう。
a[0]~a[4]までの5つの配列がある。a[0]a[1]a[2]a[3]a[4]
iを4から1まで減少させながら（つまりは4回。5回ではない）、jに0以上i以下（こちらは一巡目は0から5までの5つの数字となる）のランダムな数字を入れて、a[ j ]とa[ i ]を交換する。
・・先のフィッシャ–イェーツはランダムに選んでそれを結果として最後に加えていく方法でしたが、交換という方法を使うことによって後ろから付け加えていくという形で無駄を省いてやっているようなイメージですね。
ダステンフェルドの手法で同じように12345でやってみると・・
（1巡目）i=4、jを0から4までのランダムな数字、例えば3とすれば、a[3]とa[4]を交換して、(4と5）
12354。
（2巡目）i=3、jは0から3までのランダムな数字、例えば1とすれば、a[1]とa[3]を交換して、(2と4）
14352。
（3巡目）i=2、jは0から2までのランダムな数字、例えば0とすれば、a[0]とa[2]を交換して、（1と3）
34152。
（4巡目）i=1、jは0から1までのランダムな数字、例えば1とすれば、a[1]とa[1]を交換して、（2と2）
34152
となります。
なぜ5つの数字に対して5巡ではなくて4巡なのかというと、仮に5巡目をやったとしても、a[0]とa[0]の交換になると決まっているので、やる意味がないからです。
これを別の言い方で説明すると、
1巡目・・5つの全部の数字のうちどれかをランダムに選んで5と交換する。
（「5」と「1~5のどれか」を交換する）
2巡目・・1巡目で交換した5以外の4つの数字からランダムに一つ選んでそれと4を交換する。
（「4」と「1~4のどれか」を交換する）
3巡目・・1、2巡目で交換した5、4以外の3つ数字からランダムに一つ選んでそれと3を交換する。
（「3」と「1~3のどれか」を交換する）
4巡目・・1、2、3巡目で交換した5、4、3以外の数字2つのうちランダムに一つ選んでそれと2を交換する。（「2」と「1~2のどれか」を交換する）
つまりもっと簡単に書くと、
(1)「5」と「1~5のどれか」を交換する
(2)「4」と「1~4のどれか」を交換する
(3)「3」と「1~3のどれか」を交換する
(4)「2」と「1~2のどれか」を交換する
あるいは、以下の処理でも同じです。
(1)「5番目」と「1~5番目」のどれかを交換する
(2)「4番目」と「1~4番目」のどれかを交換する
(3)「3番目」と「1~3番目」のどれかを交換する
(4)「2番目」と「1~2番目」のどれかを交換する
やっていることはこれだけです。
青い方のやり方と赤い方のやりかたの違いがわかるでしょうか？例えば青い方の４は、数字の４のことですが（配列のどこにあっても）、赤い方は「そのとき４番目にある数字」であって、数字の４とは限りません。青い方なら青い方でやって、赤い方のやり方と混ぜてはいけません。（ごっちゃにした間違いの例）
ダステンフェルドの手法のプログラミングでは、赤い方の処理をやっています。どうしてかというと、forループの繰り返し処理の中でその都度配列の並びが上書きされるからです。紙とペンでやってすべての場合がでるかどうか確かめてみました（メモ）が面白いことにどちらもすべての場合が出ます。ダステン先生はすごいですね。
これをコードで書くと授業でやったものを使って、
//シャッフル
function shuffle() {
// カードグループの一番最後の添え字
var last = cardGroup.childNodes.length - 1;
// 繰り返し処理
// for(初期化; 繰り返し条件; 後処理){処理}
for(var i=last; i>0; i--){
// for(var i=0; i<=last; i++){ 授業ではこのように書きました
console.log(i);
// 添え字を使ってカードを呼び出す
var card1 = cardGroup.childNodes[i];
// ランダムで添え字を作る
var r = getRandom(0, i); // ここをlastではなく、iにするのが精度的には正しいそうです
//var r = getRandom(0, last); 授業ではこのように書きました
// 添え字を使ってカードを呼び出す
var card2 = cardGroup.childNodes[r];
// 交換処理
swap(card1, card2);
}
}
となります。
授業で書いたものは、簡単にしたものということで、正確なものとは異なっているようです。
ランダムで添字を作るの部分は、配列の全部、（上のコードの場合（0、last)）から取り出すと、厳密にいうとシャッフルの精度が下がる（確率が均等でなくなる）のだそうです。ランダムの範囲は、ずっと配列のどこでも好きなところからとるのではなく、まだ取り変えていない範囲（0、i）に減らしていくというのが、正しいやり方だそうです。うーん難しい。サイトにも間違えて書かれてあるところが多いそうです。
こちらのサイトが参考になりました。
クジラ机ブログ / 配列シャッフルFisher-Yatesを覚え間違えていた件
これはこれで、一つの間違いがわかりました。
これとはまた別の疑問がでてきてしまいました。上のソースコードの書き方はWikipediaの説明部分の
改良されたアルゴリズム(ダステンフェルドの手法）
要素数が n の配列 a をシャッフルする(添字は0からn-1):
i を n - 1 から 1 まで減少させながら、以下を実行する
j に 0 以上 i 以下のランダムな整数を代入する
a[j] と a[i]を交換する
のやり方に従ったものです。
でも、Wikipediaには続きがあって、「紙とペンを使用した場合」として実際にやってみる説明が書かれているのですが、これとは違う（間違ってる？）ということに気づいてしまいました。Wikipediaですから、間違いがあるのはあることなのかも知れませんね、どちらが正しいのだろう・・多分、下の「紙とペンを使用した場合」の説明のほうが間違っていると私は思います。どこが違うかというと、下の説明の部分で、赤字にした部分です。これが、下のやり方では8番目の数字、7番目の数字、6番目の数字・・2番目の数字となっているのですが、先の説明のやり方に従うなら、「8番目の数字」ではなくて、「数字の8」（どこの順番にあろうが）、「7番目の数字」ではなくて、「数字の7」と交換しなければならないはずです。
たぶん、そのほうが正しいです。（わかる方いたら教えていただきたいです）正しくないです、下のWikipediaの説明で合ってました。（後述）
間違っている気がするWikipediaの説明部分↓
紙とペンを使用した場合
ここでは同じ例をダステンフェルドの手法で行う。上記の例では数字の消去と書き出しを行ったが、今回は選ばれていない数字の中で最後の数字との入れ替えを行う。前と同様に1から8までの数字をメモしておく。
範囲 乱数 メモ 結果 1 2 3 4 5 6 7 8 1から8までの数字の中でランダムな数字を取得する。今回は6だったとする。この場合、6番目と8番目の数字を交換する。
範囲 乱数 メモ 結果 1–8 6 1 2 3 4 5 8 7 6 次は1から7までの数字の中でランダムな数字を取得する。2だった場合、2番目と7番目の数字を交換する。
範囲 乱数 メモ 結果 1–7 2 1 7 3 4 5 8 2 6 続けて1から6までの数字の中でランダムな数字を取得する。ここで取得した数字が6だった場合、6番目の数字をそのまま結果とする。今回の例で言えば8を結果とする。結果の数列が完成するまで、ここまでの処理を繰り返す。
範囲 乱数 メモ 結果 1–6 6 1 7 3 4 5 8 2 6 1–5 1 5 7 3 4 1 8 2 6 1–4 3 5 7 4 3 1 8 2 6 1–3 3 5 7 4 3 1 8 2 6 1–2 1 7 5 4 3 1 8 2 6 この時点で処理が終了し、「7 5 4 3 1 8 2 6」という順列が得られる。
また調べてみてわかったら書きます。👩🏻💻 （→紙とペンでやってみて確かめてみました。やはり間違ってました）やっぱり合ってました^^; すみません〜💦この前の授業（9/8)の後、プログラミングでは上記の赤い方の処理でやっているのだということに気づきました。この説明を、私は青い方のやり方が書いてあると思って間違いと思ってしまったのですが、赤い方のやり方で書いてあったということがわかりました。すごい勉強になりました。
結果、ダステンフェルドの手法を視覚化してつくって以下のようにつくってみました。
３．完成作品
・12345のシャッフル
もっとたくさんで見てみたくて、80本のバーでも作ってみました。
上の段も下の段も同じシャッフルをしています。上は色が混ざっていくことでシャッフルされている様子がわかります。下の段は、移動済みのものが青から赤に色が変わっていきます。
・80本の棒のシャッフル
私も絶対の自信はありませんが、wikipediaの赤字の部分は、間違いだと思います。
「8番目の数字」ではなくて、「数字の8」で正しいと思います。
添え字の数字と、並び順を分けて考える必要はない気がします。（よりプログラムが複雑になるだけ）
配列12345のシャッフルした結果は、 5！＝5×4×3×2×1＝120通り あるはずで、
フィッシャーイエーツの考え方そのものです。
ダステンフェルドの手法も結局、5！してるので確率は均等で、配列の要素数分5回入れ替えをしてしまうと
5の5乗になって不均一になるのだと思います。
さいごの紙とぺんでの場合は、結局のところフィッシャーイエーツとほぼ同じことをやっているような…。
残された数字が1 2 3 4 5 7 8でも1 2 3 4 5 8 7でもランダムに数字を取得するなら確率はかわらないので、
入れ替えること自体が、無駄な感じがしますね。
すごく勉強になりました。ついついネットに書いてあることを信じてしまうので、
一度立ち止まってじっくり考えるよい機会になりました！！
＞さいごの紙とぺんでの場合は、結局のところフィッシャーイエーツとほぼ同じことをやっているような…。
そうです〜、同じことを、紙とペンでやるとどうやるかという説明が付け加えられていて、これはこれでとてもわかり易いと思うのです。
ダステンフェルドの手法も同じもので、プログラミングでやろうとすると行き着く完成形の書き方（無駄のないやり方）だと思います。実際授業で書いたのはこちらでした。
このダステンフェルドの手法について、紙とペンでのやり方も同じことが書いてないといけないのに（フィッシャーのほうの紙とペンのやり方の説明のほうは間違ってない）、違うことが書いてあるっぽくておかしいんじゃない？！と言う話でした^^;
私の書き方も悪かったのですが、「８番目の数字という間違い」は、「ランダムに取り出す範囲の間違い」とはまた別の話で、ランダムに取り出したものを何と交換するかという話で、確かに、最初は８番目の数字のところに８があって、最初に７が選択されていなければその次も７番目の数字のところに７があるのでいいんですが、８分の１の確率で７でなくなる（７と８で交換するから）ので狂いますからやっぱりこれは間違いですね・・
多分これはフィッシャーのやり方で「後ろに順番に結果を書き加えていく」ので、これを「今並んでいる数字の後ろから”位置”を順番に交換していく」と間違えてしまったのでしょう。
要は、このforの繰り返し処理って同じことをやっているようで、実際はその都度並び順が変わっている中で処理をしているんですね。ランダムの選択の範囲も変わっていく。だけど、最初に割り振られた添え字は変わらない。これを添え字までその都度更新されるかのように間違えてしまっています。
わー、文章で説明するのって難しいー数学って文章力が必要ですね（他の教科もですが）
実際手作業で確かめてみたので、よかったらまた見てみてください！