シャッフルを紙とペンでやってみる

前回の、「フィッシャ–イェーツのシャッフルを視覚化してみる」の続きです。

フィッシャー-イェーツのシャッフル

紙とペンで、実際やってみるとよくわかります。一番簡単な、３つの数字、１２３の並びをシャッフルしてみます。このやり方に従ってすべての場合を出したときに、６通りが均等になっていれば、確率的に正しいことがわかります。

簡単なのですぐできます。

ダステンフェルトの手法（正しいやり方）

これをプログラミング的に書いたダステンフェルトのやり方もやってみましょう。

　　　　　　　　　　　　(↑この部分、3つとも j=2 ではなくて、j=1 の間違いです。書き間違えてる!!)

ダステンフェルトの手法（間違ったやり方）

前の記事フィッシャ–イェーツのシャッフルを視覚化してみるの中の、赤いやり方の処理と青いやり方の処理をごちゃまぜにした間違ったやり方です。当初、ウィキペディアの説明が間違っているのではないかと思ってやってみたのですが、それは私の勘違いで、そちらの説明は合っていました。前の記事も訂正しておきました。でもこれはこれで間違いの例なので載せておきます。数字でやるなら数字で、順番でやるなら順番で、統一しないといけないということです。

結果、４通りとなってしまいました。

これは、１順目で、２以外の数字が二番目にくる結果が１通りあるので、それに対して２順目で２通りあり、合計１×２通りが狂うからです。

ということで、やはり間違いであることがわかりました。

ところで、このダステンフェルトの手法

要素数が n の配列 a をシャッフルする(添字は0からn-1):
  i を n - 1 から 1 まで減少させながら、以下を実行する
       j に 0 以上 i 以下のランダムな整数を代入する
       a[j] と a[i]を交換する

は、フィッシャー−イェーツをコンピュータ向けに改良したものとあって、内容がプログラミングの書き方（forループ）そのものです。

だからもし、プログラミングを習っていなかったら、これが何を言おうとしているのか、多分わからなかったと思います。そんなところからも、またすごく面白みを感じたのでした。

【追記】

あれから大学時代の古い記憶がかすかに蘇ってきて、何の科目か何の勉強かも思い出せないのですが、レポートをやるために本を調べていたときに、iとｊの出てくる、こんなような説明の意味がさっぱりわからなくて半日以上考えたり調べたりしたけれどわからなくて諦めたことがあって（当時はまだパソコンもなかったし）、もしかするとこれだったのかな・・とふと思いました。上の「ダステンフェルドの手法」の文には、日本語的に致命的な欠陥があると思います。（笑

〜減少させながら、以下を「繰り返し」実行する

と書くのが正確なのではなかろうか٩(๑`^´๑)۶。繰り返し処理というのは普通の数学教育では一般的ではないので、プログラミングをやっている人にはパッと見ですぐわかることでも、やったことのない人には「減少させながら以下を実行する」とだけ書かれても意味不明だと思います。