JavaScript
 Computer >> コンピューター >  >> プログラミング >> JavaScript

【JavaScript】Fisher-Yates（フィッシャー–イェーツ）シャッフルとは？仕組みとサンプルコードを解説

Fisher-Yatesシャッフルアルゴリズムとは

フィッシャー–イェーツ（Fisher-Yates）シャッフルは、配列内の要素をランダムに並べ替えるための古典的なアルゴリズムです。独自のロジックを実装することも可能ですが、すべての並び順が等しい確率で現れる（偏りがない）ことから、多くの開発者がこの「モダン版」Fisher-Yatesアルゴリズムを配列シャッフルのベストな手法と考えています。

アルゴリズムの手順

ここでは、8個の要素（A〜H、インデックス0〜7）を持つ配列を例に、処理の流れを順番に見ていきましょう。

  • 後ろから前へループする：まず配列を末尾から先頭に向かって走査します。最初のパスでは、最後尾のインデックス7にある要素「H」が対象になります。
  • 乱数（ランダムインデックス）を生成する：対象のインデックス7と先頭のインデックス0の間で、ランダムな数値を生成します。ここでは仮に「3」としましょう。
  • 要素を入れ替える（スワップ）：選択したインデックス7の要素「H」と、ランダムインデックス3の要素「D」を交換します。これにより配列は A,B,C,H,E,F,G,D に変わります。
  • 2周目以降は末尾を除外：次のパスでは、すでに確定済みのインデックス7を無視し、インデックス0〜6の範囲で乱数を生成します。仮に生成されたのが「2」だった場合、インデックス6の要素「G」とインデックス2の要素「C」を交換し、配列は A,B,G,H,E,F,C,D となります。
  • インデックス1まで繰り返す：同じパターンで対象範囲を1つずつ狭めながら、乱数との交換を続けます。ループはインデックス1で終了します。インデックス0は、それより小さいインデックスが存在しないため、処理対象にはなりません。
  • 自分自身との交換もある：生成された乱数が現在のループインデックスと一致することもあります。たとえばインデックス4を処理中に乱数として4が出た場合、その要素は元の位置のまま変化しません。この仕組みによって、すべての順列が公平な確率で得られるのです。

以下は、モダン版Fisher-Yatesシャッフルを実装した具体的なコード例です。

サンプルコード

<html>
<body>
<script>
    var arr = ['A','B','C','D','E','F','G','H'];
    var i = arr.length, k, temp; // k：ランダムインデックス用／temp：値交換用
    while (--i > 0) {
        k = Math.floor(Math.random() * (i + 1));
        temp = arr[k];
        arr[k] = arr[i];
        arr[i] = temp;
    }
    document.write(arr);
</script>
</body>
</html>

出力結果

C,F,H,D,A,G,E, B  // 実行するたびに出力は変わります

このように、Fisher-Yatesシャッフルを使えば、わずか数行のコードで公平かつ効率的に配列をシャッフルできます。計算量はO(n)と非常に軽量で、カードゲームの山札を作る場合や抽選・ガチャ機能など、ランダム性が必要なさまざまな場面で活用されています。

  1. JavaScriptでランダムな数値を生成する方法｜Math.random()の使い方を解説

    JavaScriptのMath.random()関数は、0以上1未満の範囲でランダムな浮動小数点数を生成するために使用されます。戻り値は「0以上・1未満」であり、1自体は含まれない点に注意してください。この関数を活用すれば、サイコロのようなランダムな整数の生成や、くじ引き・シャッフル処理など、さまざまな場面で乱数を利用できます。Math.random()で1〜10のランダムな整数を生成する方法1から10までのランダムな整数を取得するには、Math.random()の結果に10を掛け、Math.floor()で小数点以下を切り捨てた後、1を加算します。数式で表すと以下のようになります。Math.

  2. JavaScriptで配列のランダムな要素を置き換える方法

    JavaScriptの配列内にあるランダムな要素を別の値に置き換えたい場合は、Math.random()とmap()メソッドを組み合わせて使うことで実現できます。まず、ランダムに選ばれたインデックスをSetオブジェクトに格納し、その後map()を使って該当する位置の値だけを新しい値に差し替えます。重複しない複数のランダム位置を選びたい場合にも、Setを利用することでスマートに処理できます。サンプルコード以下が実際のコードです。function substituteRandomValue(names, size) {    return function () {