月別: 2018年6月

プログラミングはすごく数学に似ています。似ている、というのは、考え方はもちろんのこと、理解の仕方や積み重ねで勉強していくところとか、勉強の仕方も似ている・・というより、私はもろ数学だと思いました。

「学校（小学校から高校）で習う数学は、本当の数学ではない」と私の中学時代の数学の先生は言いました。「大学に行ったらさっぱりチンプンカンプンで、それでも数学という学問の、大海原の一滴を見たに過ぎなかった」と言われましたが、私もそのとおりだと思います。

確かに、高校までの、問題から答えを導き出すような数学は、数学を使ったパズルゲームのようなもので、基礎的な数の扱いに過ぎません。積み木遊びのような。それでも、積み木遊びが幼児にとってはとても大切な良い遊びであるように、数の扱い方や計算、順序だてた物事の考え方など、身について役に立つことはたくさんあります。

プログラミングも目的に向かって一つの解答を導くものです。こういう風に動かすにはどうしたらいいか、という問題があるとしたら、公式をつかって組み立てていきます。組み立てていくときには、順番（論理）というものがすごく重要で、いろんなパーツを順序良く当てはめて解いていくパズルと似ています。そして、一つの解（プログラム）が導かれますが、それは一つではなくて、色々な解き方があるというところも同じです。

いろんな公式が増えていって、それを組み合わせ、前に使ったものを土台にしてどんどんピラミッドのように積み重ねられて複雑な大きな問題も解けるようになる、というところも同じです。

公式を知っただけでは問題は解けなくて、いろんなパターンの問題を実際に解いてみて、使い方もいろんなパターンで身につけて初めて解けるようになるというところも同じです。メソッドを教えてもらってプログラミングしてみても、最初は大抵うまくいかないことがほとんどです。トライ（トライアル）・アンド・エラーの繰り返しです。そして、公式も最初に覚えなくても使ううちに自然に覚えていくように、コードも打ち込んでいくうちに覚えていきます。

その過程には「そういうことだったのか！」という発見もたくさんあって、そして解けたときの喜びは、問題が難しければ難しいほど、大きいものです。

・・というわけで、数学は、プログラミングの為にあるのはもちろんのこと（笑）、詰まる所、数学も、プログラミングも、ゲームだ （から面白い）ということがわかりました😆　

・swap視覚化

・80本の棒のシャッフル

１．フィッシャ–イェーツのシャッフルとは

先日の授業では、シャッフルを教えてもらいました。

その中で、「フィッシャ–イェーツのシャッフル」を簡単にしたものを扱いました。そこで、フィッシャ–イェーツのシャッフルとは実際どういう動きでシャッフルしているのか知りたくて、視覚化した物を作ってみようと思って、その為に調べてみました。

ウィキペディアのフィッシャ–イェーツのシャッフルによると、

1. 1 から N までの数字を書く。
2. まだ消されてない数字の数を数え、1 からその数以下までのランダムな数字 k を選ぶ。
3. 残っている数字から k 番目の数字を消し、別の場所にその数字を書き出す。
4. すべての数字が消されるまで手順 2, 3 を繰り返す。
5. 手順3で書かれた数列が元の数値からのランダム順列となるとなる

というものです。

何かを訳したものだと思いますが「消されていない」「消されるまで」となっていてわかりにくいですが、これは「選ばれていない」「選ばれる」と読み換えるとわかりやすいと思います。

例えば1〜5までの数字、12345をシャッフルする場合、

これがこのシャッフルの仕方です。

２．ダステンフェルドの手法

さらに、現代ではこれをコンピュータでの使用を想定して改良した、ダステンフェルドの手法が採用されているとのことです。これは

要素数が 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でやってみると・・

となります。

なぜ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本の棒のシャッフル