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

  • 0
    いいね
  • 0
    コメント

    Fisher-Yates Shuffle

    ロナルド・フィッシャーさんおよびフランク・イェーツさんが考案したシャフルのアルゴリズムです。

    アルゴリズムのイメージ

    くじ引きの箱の中から1つずつくじを引いて並べてシャッフルするイメージです。

    「取り出す範囲(くじ箱の中)」と「結果の範囲(くじ箱の外)」の2つに分けて考えます。

    手順

    • 取り出す範囲(箱の中)から取り出す値をランダムに1つ決定する。
    • 末尾の値と交換する。末尾を結果の範囲(くじ箱の外)とする。
    • くじ箱の外が新しくできたので、取り出す範囲(くじ箱の中)を1つ前に狭める。
    • 上記3つの処理を先頭の値がくじ箱の外になるまで繰り返す。
    • 値が不規則に並んでかえってくる

    おわり

    //ソートされた配列
    a = [1,2,3,4,5,6,7,8,9];
    
    //取り出す範囲(箱の中)を末尾から狭める繰り返し
    for(i = a.length -1;i>0;i--){
        //乱数生成を使ってランダムに取り出す値を決める
        r = Math.floor(Math.random()*(i+1));
        //取り出した値と箱の外の先頭の値を交換する
        tmp = a[i];
        a[i] = a[r];
        a[r] = tmp;
    }
    //結果を表示
    console.log(a);