「取り出し」アルゴリズムのフィッシャー–イェーツシャッフル

「取り出し」アルゴリズム

「j と i が等しくない場合」の処理は、初期化されていない配列の要素に対するアクセスが許容されているプログラミング言語であれば省略することができ、比較してよりコストのかからないアルゴリズムを実行できる。
フィッシャー–イェーツのシャッフル - Wikipedia

「おお、これ、JavaScriptのことじゃん」と思って書いてみました。

const shuffle = (src) =>
  src.reduce((a, x, i) => {
    const j = Math.floor(Math.random() * (i + 1));
    [a[i], a[j]] = [a[j], x];
    return a;
  }, [])

一応確認。

const matrix = Array.from(Array(10), () => Array(10).fill(0))
for (let i = 0; i < 1000000; i++)
    shuffle([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]).forEach((x, i) => matrix[x][i]++);
// [[99562,100257,99884,100396,99908,100376,99586,99682,100205,100144],[99610,100240,99775,99913,99432,100482,100190,99801,100584,99973],[100107,100071,100084,99905,99911,99882,99926,100067,99604,100443],[100167,99691,100548,99453,99885,99892,100281,100024,99986,100073],[100223,100000,99731,99779,100406,99809,100129,100343,99464,100116],[99581,100106,99855,100381,100445,100304,100190,99662,99682,99794],[100042,99876,99803,99887,99862,99885,100185,100470,99714,100276],[100084,99288,100128,100382,100383,99995,99665,99742,100602,99731],[100020,100308,100263,100076,99644,99693,99683,100310,100366,99637],[100604,100163,99929,99828,100124,99682,100165,99899,99793,99813]]

大丈夫そう。

---

イテレータからのシャッフル

「取り出し」版のもう一つの利点は、元配列のデータから完全に独立したランダムな要素が取得できるのであれば、元配列の総要素数 n が未知の場合でも使用できる点である。
フィッシャー–イェーツのシャッフル - Wikipedia

なるほど。

const g = function* () {
    let i = 0;
    while (Math.random() < 0.9) yield i++;
}

const shuffle = (src) => {
    let a = [];
    for (let x of src) {
        const i = a.length;
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], x];
    }
    return a;
}

shuffle(g())；

Iterator.prototype.reduce() があれば Array と同じコードで動くんですが……
Iterator.prototype.reduce() - JavaScript | MDN