LoginSignup
16

More than 5 years have passed since last update.

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

Last updated at Posted at 2017-02-12

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);

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
16