ダステンフェルドのシャッフルについてのメモ

ダステンフェルドの手法

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

例)数字の「1,2,3,4,5」をシャッフルする場合の手順

1.数字を基準とするやり方。どこにあるか位置は関係なし。

(1)「数字の5」と「数字の1~5のどれか」を交換する

(2)「4」と「1~4のどれか」を交換する

(3)「3」と「1~3のどれか」を交換する

(4)「2」と「1~2のどれか」を交換する

あるいは、以下の処理でも同じ。

2.位置を基準とするやり方。数字は何であるか関係なし。

(1)「5番目にある数」と「1~5番目にある数」のどれかを交換する

(2)「4番目」と「1~4番目」のどれかを交換する

(3)「3番目」と「1~3番目」のどれかを交換する

(4)「2番目」と「1~2番目」のどれかを交換する 

プログラミングでの処理は↑こちら。

紙でやってみる。順序は違うが結果は同じになる。

二重のfor文を使ってビンゴカードを作る

今回の授業は、for文を使って、ビンゴカードを自動作成しようというものでした。

二重のfor文

ポイントは、二重のfor文です。「5回の繰り返し」を5回繰り返すことで、5×5の25個の数字を並べます。

// 二重のfor文(c0,c1,c2,c3,c4を5回繰り返す)
for(var r=0; r<5; r++){
    console.log("r" + r);//r0~r4
    for(var c=0; c<5; c++){
        console.log(" c" + c);
        // 座標に応用
        var x = 32 * r;// 授業とはrとcが逆(列と行を逆にしたいから)
        var y = 32 * c;
        console.log(x + ", " + y);
        // ラベル
        var label = new Label();
        label.x = x;
        label.y = y;
        label.text = "[" + r +","+ c +"]";// こちらも逆にする(これで[列、行]の並びになる)
        scene.addChild(label);
         label.text = getRandom(1, 75);
    }
}

c0からc4をr0からr4まで5回繰り返すということです。(授業でやったものとはrとcを逆にしました。列でまとめたかったからです)

c0~c4が5列に並ぶという形になります。

ラベルのところでテキストを「“[” + r +”,”+ c +”]”」とすることで、

[00][10][20][30][40]

[01][11][21][31][41]

[02][12][22][32][42]

[03][13][23][33][43]

[04][14][24][34][44]

となりました。(rが列、cが行となっています)

あとは label.text = getRandom(1, 75); で、それぞれの表示を1〜75の数字をランダムに出るようにすれば、ビンゴカードの出来上がりです。

・・しかし、これだとそれぞれの数のランダムなので、数が重複する場合があります。(それはそれで二つ空けられるラッキーナンバーということにすればいいのかもしれませんが、一般的なビンゴゲームにも一応ルールがあって、その中には数は重複しないというのがあります)

数が重複しないようにシャッフルを使う

そこで、数が重複しないように作るにはどうしたらいいかということで、その方法も教えてくださいました。

ここでダステンフェルドのシャッフルを使います。

// 配列を使ってダブらないビンゴカードにする
// 配列を作る
var nums = [];
for (var i=0; i<25; i++){
    nums.push(i);//numsの中にiがプッシュされていく。今iは0~24の25個の数字
}
console.log(nums);
// ダステンフェルドの手法でシャッフルする
for(var i=nums.length-1; 0<i; i--){// iが24から1まで24回繰り返す
    var rdm = getRandom(0, i);// rdm:自分の数以下からランダムに選んだ数字一つ
    var tmp = nums[i];// 新しくtmpを用意してnum[i]を入れておく
    nums[i] = nums[rdm];// nums[i]に選ばれたランダムな数を入れる
    nums[rdm] = tmp;// nums[rdm]にtmp(muns[i])を入れる。これで交換完了
}
console.log("nums", nums);

0から24までの数をシャッフルしています。

どうなっているのかわかりにくいのでそれぞれconsole.logで見てみました。

// ダステンフェルドの手法でシャッフルする
for(var i=nums.length-1; 0<i; i--){// iが24から1まで24回繰り返す
    console.log("i:", i, "," , "muns[i]:", nums[i]);
    var rdm = getRandom(0, i);// rdm:自分の数以下からランダムに選んだ数字一つ
    console.log("rdm:" , rdm , "," , "nums[rdm]:" , nums[rdm]);
    var tmp = nums[i];// 新しくtmpを用意してnum[i]を入れておく
    console.log("tmp(=nums[i]):" , tmp);
    nums[i] = nums[rdm];// nums[i]に選ばれたランダムな数を入れる
    console.log("muns[i](=nums[rdm]):" , nums[i]);
    nums[rdm] = tmp;// nums[rdm]にtmp(muns[i])を入れる。これで交換完了
    console.log("nums[rdm](=tmp):" , nums[rdm]);
    console.log(nums);
    //全部consoleで見てみる
}
console.log("nums", nums);

すると、このような動きになっていました。

for文の繰り返しの中でその都度配列の順番が変わって上書きされるので、最初はnums[22]は22だったのが、入れ替わったことで途中でnums[22]は24に変わっています。

一度交換の相手になったランダムで選ばれた「数字」は、後ろから順番に入っていって固定され(iは減少していくから)二度と交換されることはありません。そうでないと精度的に正しいシャッフルとなりません。

ラベルで表示する

あとは、ランダムに並べ替えられた数字にindexを用意して、num[0]~num[24]までがラベルのテキストに入るように書き換えて、ランダムに並んだ数字を表示できました。

// インデックス
var index = 0;
//label.text = "[" + r +","+ c +"]";// こちらも逆にする(これで[列、行]の並びになる)
label.text = nums[index];// 初期値は0
index++;// ラベルのテキストがnums[0]からnums[24]になる

一般的なルールのビンゴカードを作る

つぎに、これを応用して、日本でのビンゴの一般的なルールにしたがったものを作ってみたいと思ってやってみました。

wikipediaのビンゴより

ルールには無数にバリエーションがあるが、ここでは日本で一般的に行われている代表的なものを示す。一般的にビンゴカードはタテ・ヨコ5マスずつ、計25個のマス目が書かれている。その内、中央を除く24マスには1から75までの番号のうち24個の番号が書かれており、中央はフリースポットとして最初から有効な番号として扱われる。1枚のカードの中で同じ番号が重複することはない。

カードに書かれる番号は、通常はまったくのランダムで配置されているわけではなく、一番左の列は1-15の中から5個選ばれている。同様に、左から2列目は16-30、中央列は31-45、右から2列目は46-60、一番右の列は61-75から5個ずつ(中央列のみフリースポットがあるので4個)選ばれている

全くのランダムではなく、15づつの数の固まりから5個ずつ選ぶようになっているようですね。

ちょっとややこしそうですが、for文をたくさん使ってやってみました。

1〜15まで、16から30まで、31から45まで、46から60まで、61から75までの数からそれぞれ5つずつランダムに選ぶ必要があるので、それぞれシャッフルした15個の中から5つを選んでそれを左の列から並べるというやり方で作りました。

まず、nを始めの数とする変数として15個の数のシャッフルを作る関数 Nums15(n) を作ります。ここでやっていることは、要素15個の配列をシャッフルして、その最初から5つの目までの数を取り出してnumsselという配列に入れていくという処理です。既にシャッフルされた数なので、そこから5つの数を取り出せば、ランダムで重複しない数となります。

    // 目的の配列を用意
    var numssel = [];

    //nをはじめの数とする15個の数字のシャッフルを作る関数
    function Nums15(n){
        var nums15 = [];// 15個の配列の入れ物を用意
        for (var i=n; i<n+15; i++){
            nums15.push(i);// n~n+15までの数を[]に入れる
        }
        // シャッフル
        for (var i=nums15.length-1; 0<i; i--){
            var rdm = getRandom(0, i);
            var tmp = nums15[i];
            nums15[i] = nums15[rdm];
            nums15[rdm] = tmp;
        }
        // 出来たランダムな配列nums15から5つの数字を取り出してnumsselという配列に入れていく。
        for(var i=0; i<5; i++){
            numssel.push(nums15[i]);// 最初から5つをnumsselに入れていく
        }
    }

あとは、そのかたまりの始めの数は1,16,31,46,61なので、その関数をつぎのようなfor文で実行します。

// 実行する。ここでnumsselが最終的に5*5で25個となる
for(var i=1; i<76; i+=15){ 
    Nums15(i);
}

すると、ランダムに選ばれた5つの数を5回入れていくので、numsselには、1~15から5つ、16~30から5つ、31~45から5つ、46~60から5つ、61~75から5つ、合計25個の数が選ばれて入ります。

ただし、真ん中はFreeにしたいので、真ん中はmussel[12]なので

numssel[12] = "free";

とします。

あとは、授業でやったときとおなじように、この配列musselにindexを使ってラベルに対応させて表示させれば、左の列からルールのようにならんだビンゴカードができました。

forをたくさん使ったので、すごくforの練習になりました。functionも使ったので、途中、頭がこんがらがって死にそうになりました。関数は作ってもその実行は別の場所でやる感じなので、コードでは後ろに書いてあっても処理としては戻るような感じになって、あっちこっちで訳がわからなくなりそうでしたが、これも慣れなのでしょうか・・頭の中でforループの処理を同時にシミュレーションできないと書けないと思うので、これがサラッとできちゃうプログラマさんてすごいね。でもfunctionmとforを使うと本当に短く書くことが出来て、達成感がありました。あと今見て思ったんですが「配列の配列」ってあるんかな、当然あるでしょうね。(私は汚いコードでも動けばいいという^^;だめよねそれじゃ)

文字の基準が中心で揃っていなっていないのが気になります・・そのうちこれを使って、何かゲームが作れたら作ってみたいと思います・・(授業で話しが出た独りビンゴなんかいいと思うけどなー)

完成したもの

時計を作ってみよう(javaScript)

1.時計の表示

今回の授業は、デジタル時計を作るというものでした。

「一秒ごとに何かが起きるというjavascriptの機能を使う」と先生は説明されました。(子供向けにこのような説明の仕方をされるところが面白いですね)

まず、一定時間ごとに処理をするというsetIntervalを使った関数を作ります。

// 1秒毎に処理をする
setInterval(function(){
    console.log("Hello!!");
},1000);

時間はミリ秒で指定します。ここでは1秒ごとに処理をしたいので、1秒=1000ミリ秒で指定します。

console.logで確かめると、一秒ごとにHello,Hello,と表示されるので、処理されていることが確かめられました。

時計の処理の関数を作って、この中に入れます。(console.logをshowClock();に書き換える)

function showClock(){
    console.log("時計の処理!!")
    // 日付オブジェクト
    var dObj = new Date();
    // 時間を取得する
    var hours = dObj.getHours();//日付から時間をgetする
    console.log(hours);
    var minutes = dObj.getMinutes();//日付から分をgetする
    console.log(minutes);
    var seconds = dObj.getSeconds();//日付から秒をgetする
    console.log(seconds);
}

new Date();で、今現在の日付のデータを取得し、その中に含まれている時間、分、秒を取り出しています。それぞれconsole.logで

10
11
05

のように表示されます。これではわかりにくいので、横並びに表示されるようにします。

    // デジタル時計
    var str = hours + minutes + seconds;//数値として加算されてしまうので間違い
    console.log(str);
    var str = hours + ":" + minutes + ":" + seconds;
    console.log(str);
    var str = hours + "時" + minutes + "分" + seconds + "秒";
    console.log(str);

単に+でつなぐと、数値として扱われるために、加算されて一つの数値となってしまいます。

そこで、間に文字列を挟むことで、

10:11:05

あるいは

10時11分05秒

と表示させることができました。

2.日付の表示

次は日付です。

    // 年月日を取得する
    var year = dObj.getYear() + 1900;
    console.log(year);
    var month = dObj.getMonth() + 1;
    console.log(month);
    var date = dObj.getDate();
    console.log(date);

これもさっきと同じように、dObjから年、月、日のデータをそれぞれ取り出します。

ここで注意が必要なのは、getYearでは1900マイナスの年が取り出されるので(1900年台に始まったコンピュータの世界で、下2桁で処理をしていた為と考えられるそうです)、1900をプラスしたのが現在の年になること(代わりにgetFullYearとすると2018で出すことができるようになっている)、月は1月から配列として扱うのが都合がよいので(月は国によって呼び方が異なるから。日本では1月、2月だが、January、 February・・だったり)、1月は0というデータとして与えられるから1を加えること、日付はそのまま(多分これはどこの国でも1日、2日だから)となることです。

これを横並びで表示させるには、時計のときと同じように

    // デジタル日付
    var str2 = year + "年" + month + "月" + date + "日";
    console.log(str2)

となります。

2018年8月25日

と表示されました。

3.曜日の表示

最後に曜日です。

    // 曜日
    var arr = ["日", "月", "火", "水", "木", "金", "土"];
    var day = dObj.getDay();//日付から曜日をゲットする
    console.log(day);
    console.log(arr[day] + "曜日")

まず、曜日の配列を作ります。次に日付のデータから曜日をゲットします。曜日は、日曜日を0として土曜日まで、0,1,2,3,4,5,6という数字で与えられます。今日は土曜日なので6と出ました。

そこで、曜日の配列から、その数値を添字としたものを取り出せば、

土曜日

と今日の曜日が表示させることができました。

4.【感想】

この日の授業は盛りだくさんの、ぼーっとしている暇のないとても濃い授業でした。どうして年は1900を引かれた値になっているのだろうかとか、コンピュータの起源と歴史にまつわる話が出てきたり、なぜ月のデータは0から始まっているのか、考えてみたら日本では1月2月・・だけど英語圏や他の国では違うよね、日本でも睦月、如月・・と呼んでいたとか、いろいろ興味深い話題もいろいろ出てきました。

それにしても、この日の授業はゲームのように画像が動いたりするのでもなく、ただコンソール画面に表示される数字や文字を見ながら、「おぉー!」とか「わー!」とか盛り上がっているという、なんとまあプログラマーさん(の卵たち)でしょうかと思いました。(知らない人が見たら一体何が面白いの何を喜んでいるのという感じでしょう。)みんな打ち込むのもすごく速くなっているし。

先生方、よくここまで子どもたちを育てられましたね・・と少し感動を覚えた私でした。