番目の数字を消し、別の場所にその数字を書き出す。手順3で書かれた数列が元の数値からのランダム順列となるとなるというものです。何かを訳したものだと思いますが「消されていない」「消されるまで」となっていてわかりにくいですが、これは「選ばれていない」「選ばれる」と読み換えるとわかりやすいと思います。(2)(3)を繰り返す。次は二巡目なので、まだ選択されていないのは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となる、これがこのシャッフルの仕方です。2.ダステンフェルドの手法さらに、現代ではこれをコンピュータでの使用を想定して改良した、ダステンフェルドの手法が採用されているとのことです。a[i]を交換するというもので、先のフィッシャ–イェーツとの違いは・・これもnを5としてやってみたらわかるでしょう。a[0]~a[4]までの5つの配列がある。a[0]a[1]a[2]a[3]a[4]iを4から1まで減少させながら(つまりは4回。・・先のフィッシャ–イェーツはランダムに選んでそれを結果として最後に加えていく方法でしたが、交換という方法を使うことによって後ろから付け加えていくという形で無駄を省いてやっているようなイメージですね。ダステンフェルドの手法で同じように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。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のどれか」を交換するあるいは、以下の処理でも同じです。やっていることはこれだけです。青い方のやり方と赤い方のやりかたの違いがわかるでしょうか?例えば青い方の4は、数字の4のことですが(配列のどこにあっても)、赤い方は「そのとき4番目にある数字」であって、数字の4とは限りません。青い方なら青い方でやって、赤い方のやり方と混ぜてはいけません。(ごっちゃにした間違いの例)ダステンフェルドの手法のプログラミングでは、赤い方の処理をやっています。してかというと、forループの繰り返し処理の中でその都度配列の並びが上書きされるからです。紙とペンでやってすべての場合がでるかどうか確かめてみました(メモ)が面白いことにどちらもすべての場合が出ます。ダステン先生はすごいですね。授業で書いたものは、簡単にしたものということで、正確なものとは異なっているようです。ランダムで添字を作るの部分は、配列の全部、(上のコードの場合(0、last))から取り出すと、厳密にいうとシャッフルの精度が下がる(確率が均等でなくなる)のだそうです。ランダムの範囲は、ずっと配列のどこでも好きなところからとるのではなく、まだ取り変えていない範囲(0、i)に減らしていくというのが、正しいやり方だそうです。サイトにも間違えて書かれてあるところが多いそうです。こちらのサイトが参考になりました。配列シャッフルFisher-Yatesを覚え間違えていた件これはこれで、一つの間違いがわかりました。これとはまた別の疑問がでてきてしまいました。a[i]を交換するのやり方に従ったものです。Wikipediaには続きがあって、「紙とペンを使用した場合」として実際にやってみる説明が書かれているのですが、これとは違う(間違ってる?)ということに気づいてしまいました。Wikipediaですから、間違いがあるのはあることなのかも知れませんね、どちらが正しいのだろう・・多分、下の「紙とペンを使用した場合」の説明のほうが間違っていると私は思います。どこが違うかというと、下の説明の部分で、赤字にした部分です。これが、下のやり方では8番目の数字、7番目の数字、6番目の数字・・2番目の数字となっているのですが、先の説明のやり方に従うなら、「8番目の数字」ではなくて、「数字の8」(どこの順番にあろうが)、「7番目の数字」ではなくて、「数字の7」と交換しなければならないはずです。そのほうが正しいです。(わかる方いたら教えていただきたいです)正しくないです、下のWikipediaの説明で合ってました。紙とペンを使用した場合ここでは同じ例をダステンフェルドの手法で行う。上記の例では数字の消去と書き出しを行ったが、今回は選ばれていない数字の中で最後の数字との入れ替えを行う。前と同様に1から8までの数字をメモしておく。81から8までの数字の中でランダムな数字を取得する。今回は6だったとする。この場合、6番目と8番目の数字を交換する。6次は1から7までの数字の中でランダムな数字を取得する。2だった場合、2番目と7番目の数字を交換する。6続けて1から6までの数字の中でランダムな数字を取得する。ここで取得した数字が6だった場合、6番目の数字をそのまま結果とする。今回の例で言えば8を結果とする。結果の数列が完成するまで、ここまでの処理を繰り返す。6」という順列が得られる。調べてみてわかったら書きます。(→紙とペンでやってみて確かめてみました。すみません〜💦この前の授業(9/8)の後、プログラミングでは上記の赤い方の処理でやっているのだということに気づきました。この説明を、私は青い方のやり方が書いてあると思って間違いと思ってしまったのですが、赤い方のやり方で書いてあったということがわかりました。すごい勉強になりました。結果、ダステンフェルドの手法を視覚化してつくって以下のようにつくってみました。・12345のシャッフルもっとたくさんで見てみたくて、80本のバーでも作ってみました。上の段も下の段も同じシャッフルをしています。上は色が混ざっていくことでシャッフルされている様子がわかります。下の段は、移動済みのものが青から赤に色が変わっていきます。22:16私も絶対の自信はありませんが、wikipediaの赤字の部分は、間違いだと思います。「8番目の数字」ではなくて、「数字の8」で正しいと思います。添え字の数字と、並び順を分けて考える必要はない気がします。あるはずで、フィッシャーイエーツの考え方そのものです。ダステンフェルドの手法も結局、5!してるので確率は均等で、配列の要素数分5回入れ替えをしてしまうと5の5乗になって不均一になるのだと思います。さいごの紙とぺんでの場合は、結局のところフィッシャーイエーツとほぼ同じことをやっているような...。入れ替えること自体が、無駄な感じがしますね。すごく勉強になりました。00:34>さいごの紙とぺんでの場合は、結局のところフィッシャーイエーツとほぼ同じことをやっているような...。同じことを、紙とペンでやるとどうやるかという説明が付け加えられていて、これはこれでとてもわかり易いと思うのです。ダステンフェルドの手法も同じもので、プログラミングでやろうとすると行き着く完成形の書き方(無駄のないやり方)だと思います。実際授業で書いたのはこちらでした。これはフィッシャーのやり方で「後ろに順番に結果を書き加えていく」ので、これを「今並んでいる数字の後ろから”位置”を順番に交換していく」と間違えてしまったのでしょう。要は、このforの繰り返し処理って同じことをやっているようで、実際はその都度並び順が変わっている中で処理をしているんですね。ランダムの選択の範囲も変わっていく。最初に割り振られた添え字は変わらない。これを添え字までその都度更新されるかのように間違えてしまっています。コメントをキャンセルメールアドレスが公開されることはありません。