JavaScriptの配列をランダムに並べ替える

はじめに

前回の記事で配列をランダムに並べ替えるコードを紹介しましたが、そのやり方では大きな偏りが発生することをコメントで教えていただきました。

その際に、偏りの検証や発生原因・対策について書かれた以下の記事を紹介いただいたので、自分でも試してみた結果について記事に残します。

以下のコードは文脈に合わせたり自分仕様にカスタマイズしているため、
元記事のものとは若干異なる点があることをご了承ください。

今回使用するメソッドや構文

Object.entries(obj) 静的メソッド
オブジェクトを[キー, 値]形式の2次元配列に変換した結果を返します。
今回は、オブジェクトをその値に応じて並べ替えるために使用しました。

Object.fromEntries(list) 静的メソッド
[キー, 値]形式の2次元配列をオブジェクトに変換した結果を返します。

分割代入を用いた変数の入れ替え
[x, y] = [y, x] のようにすることで変数の値を入れ替えることができます。

もともとのコード (偏りが大きい)

console.log(array.sort(() => Math.random() - 0.5));

前回の記事で紹介したコードです。

偏りの検証

// 配列をランダムに並べ替える関数
const shuffleArray = (array) => {
    return array.sort(() => Math.random() - 0.5);
};

// 配列を100万回並べ替え, 結果を集計する
const results = {};
for (let i = 0; i < 1000000; i++) {
    const array = ['1', '2', '3', '4', '5'];
    const shuffledArray = shuffleArray(array);
    const key = shuffledArray.join(',');

    // ソート結果のカウントを増加
    if (results[key]) {
        results[key]++;
    } else {
        results[key] = 1;
    }
}

// 結果を降順に並べ替えて表示
const sortedResults = Object.entries(results).sort((a, b) => b[1] - a[1]);
console.log(Object.fromEntries(sortedResults));

結果

{
    '1,2,3,4,5': 94057,
    '5,4,3,2,1': 75538,
    '1,2,5,3,4': 31325,
    ...
    '3,5,1,2,4': 1890,
    '5,2,4,3,1': 1882
}

やはり非常に大きな偏りがありますね。

偏りの原因

ほとんど元記事の内容そのままですが、sortメソッドでは以下の要領で処理を行っているようです。
簡略化のため、処理対象の配列を[a, b, c]とします。

1. aとbを比較する
2. bとcを比較する
3. (a < b && b < c) || (a > b && b > c) の場合は推移律が成立するとして処理を終了し、それ以外の場合はaとcを比較する

よって、冒頭のコードは全ての組み合わせを比較することを前提にしていましたが、sortメソッドでは毎回全ての組み合わせについて比較するわけではないため、偏りが出たようです。
この問題を解決するためには、以下のフィッシャー–イェーツのシャッフルのように、全ての組み合わせについて比較する方法が適しています。

フィッシャー–イェーツのシャッフル

フィッシャー–イェーツのシャッフル (英: Fisher–Yates shuffle) は、有限集合からランダムな順列を生成するアルゴリズムである。
このアルゴリズムのオリジナルの手法は、1938年、フィッシャーとイェーツによって Statistical tables for biological, agricultural and medical research に記述された。
フィッシャー–イェーツのシャッフルは、全ての順列の組み合わせが等しく存在しうるため、偏りがない。

プログラミングで利用する場合、以下の改良されたバージョンが適しているようです。

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

(引用元) フィッシャー–イェーツのシャッフル - Wikipedia

このアルゴリズムを使って冒頭のコードを書き直してみます。

配列をランダムに並べ替えるコード (偏り解消版)

const shuffleArray = (array) => {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
    return array;
};
console.log(shuffleArray(arr));

フィッシャー–イェーツのシャッフルアルゴリズム (改良版) をそのまま実装したものです。

偏りの検証

// 配列をランダムに並べ替える関数
const shuffleArray = (array) => {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
    return array;
};

// 配列を100万回並べ替え, 結果を集計する
const results = {};
for (let i = 0; i < 1000000; i++) {
    const array = ['1', '2', '3', '4', '5'];
    const shuffledArray = shuffleArray(array);
    const key = shuffledArray.join(',');

    // ソート結果のカウントを増加
    if (results[key]) {
        results[key]++;
    } else {
        results[key] = 1;
    }
}

// 結果を降順に並べ替えて表示
const sortedResults = Object.entries(results).sort((a, b) => b[1] - a[1]);
console.log(Object.fromEntries(sortedResults));

結果

{
  '4,2,5,3,1': 8568,
  '1,3,5,2,4': 8533,
  '4,1,2,3,5': 8509,
  ...
  '5,4,3,2,1': 8099,
  '3,4,2,5,1': 8085
}

偏りがなくなりました！

おわりに

前回コメントをいただいたことで、新たな学びや発見をたくさん得ることができました。
これまで自分で記事を書くことばかりがアウトプットだと思っていましたが、これからは他の人の記事にも積極的にコメントしていきたいと思います。
もちろん今後も私の記事にもお気軽にコメントいただけると嬉しいです！