Fisher–Yates（Knuth）シャッフル：最短で正しい基本形

function shuffleInPlace(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]]; // swap
  }
  return arr;
}

// 使用例
const xs = [1,2,3,4,5,6];
shuffleInPlace(xs); // xs がシャッフルされる

非破壊版：元の配列を変えずにシャッフル

function shuffle(xs) {
  const arr = xs.slice(); // or [...xs]
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

不変データ前提の設計（React/Reduxなど）では非破壊版が安全です。

暗号学的に安全なシャッフル（Web Crypto）

セキュリティやフェアネスが重要（抽選・ガチャ履歴の監査など）な場合はcrypto.getRandomValuesを使います。

function cryptoShuffle(xs) {
  const arr = xs.slice();
  for (let i = arr.length - 1; i > 0; i--) {
    // 0..i を均等に得る（バイアス回避のためリジェクションサンプリング）
    let j;
    const range = i + 1;
    const max = Math.floor(256 / range) * range; // 0..255 のうち等分できる最大
    const buf = new Uint8Array(1);
    do {
      crypto.getRandomValues(buf);
    } while (buf[0] >= max);
    j = buf[0] % range;
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

シード再現（同じ並びを再現できるシャッフル）

ABテスト・リプレイ可能なテスト・デモ動画作成に便利です。

// シンプルで速い 32bit PRNG
function mulberry32(seed) {
  let t = seed >>> 0;
  return function() {
    t += 0x6D2B79F5;
    let x = Math.imul(t ^ (t >>> 15), 1 | t);
    x ^= x + Math.imul(x ^ (x >>> 7), 61 | x);
    return ((x ^ (x >>> 14)) >>> 0) / 4294967296;
  };
}

function seededShuffle(xs, seed = 12345) {
  const rnd = mulberry32(seed);
  const arr = xs.slice();
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(rnd() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

部分シャッフル（上位Kだけランダムに取り出す）

「10,000件からランダムに100件だけ抽出」などに。全体をシャッフルする必要はありません。

function shuffleTopK(xs, k) {
  const arr = xs.slice();
  const n = arr.length;
  k = Math.min(k, n);
  for (let i = 0; i < k; i++) {
    const j = i + Math.floor(Math.random() * (n - i));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr.slice(0, k);
}

これは部分Fisher–Yatesで、先頭kだけが無作為抽出になります（順序もランダム）。

重み付きシャッフル（人気度やスコアを反映）

重み w[i] に比例した確率で並びを作る簡易手法です（完全な「並び全体の分布」を重み付きにするのは複雑なので、ここでは1つずつ重み付きで取り出す方式を示します）。

function weightedShuffle(items, weights) {
  const result = [];
  const xs = items.slice();
  const ws = weights.slice();
  while (xs.length) {
    const sum = ws.reduce((a, b) => a + b, 0);
    let r = Math.random() * sum;
    let idx = 0;
    while (idx < ws.length && (r -= ws[idx]) > 0) idx++;
    result.push(xs.splice(idx,1)[0]);
    ws.splice(idx,1);
  }
  return result;
}

規模が大きい場合はEfraimidis–Spirakis法（優先度キーkey = U^(1/w)で並べ替え）なども検討してください。

理論とバイアスの理解（なぜFisher–Yatesは正しいのか）

Fisher–Yatesは各ステップで未確定領域の中から一様に1つ選び入れ替える操作を行います。帰納法により、各要素が各位置に来る確率が常に等しいことが示せます。対してsort(Math.random()-0.5)は比較関数の推移律を満たさず、ソート実装の枝刈りや安定性に起因する系統的な偏りが発生します。

• 各ステップでの選択確率は1/(i+1)（iは未確定末尾のインデックス）。
• 全順列数n!に対して、アルゴリズムが生成しうる順列もn!通りで等確率。
• 逆走査（降順）であることが重要：重複選択や未確定領域外の参照を防ぎます。

また、Math.random()はCSPRNGではありません。ゲームの抽選や公平性が問われる領域ではcrypto.getRandomValuesのCSPRNGを用いるべきです。

パフォーマンスとメモリ（スケール時の実務ポイント）

• 時間計算量：Fisher–YatesはO(n)。sort利用はO(n log n)で不利。
• メモリ：破壊版はO(1)、非破壊版は入力のコピー分O(n)。
• ストリーミング：全件読み込みが難しい場合はReservoir Sampling（k件抽出）や部分Fisher–Yatesを使用。
• 並列処理：単一配列を正しく並列シャッフルするのは難しいため、分割シャッフル→再結合の際は偏りに注意。

ユースケース別おすすめ

• UIのランダム並び替え：非破壊版shuffle()を推奨（状態の予期せぬ変異を防止）。
• ガチャ・抽選：cryptoShuffle()。監査ログにはシード・ハッシュ等の追加設計を。
• 検索結果の多様化：shuffleTopK(xs, k)で上位のみ無作為化しつつ高速化。
• 人気度反映：weightedShuffleまたはEfraimidis–Spirakis法。
• 再現実験・デバッグ：seededShuffleで固定シード。

分布の健全性を簡易チェックする（実務チェックリスト）

• ランダム化の目的を定義（均等化？希釈？重み付き？）
• 規模見積り：nとメモリ制約・応答時間SLO
• テスト：位置頻度・ペア頻度の集計、AB差検定（カイ二乗）
• 再現性要件：シード方式・ロギング・監査証跡
• フェアネス：CSPRNGの必要性、国/年齢等属性への過度な偏りの排除

分布の健全性を簡易チェックする

本番投入前に「偏りがないか」を軽く検査しておくと安心です。以下は位置の出現頻度を見る簡易テストです。

// n要素をT回シャッフルし、要素iが位置jに来た回数を集計
function testUniform(n=8, T=20000) {
  const cnt = Array.from({length:n}, () => Array(n).fill(0));
  const arr = Array.from({length:n}, (_,i) => i);
  for (let t=0; t<T; t++) {
    const a = arr.slice();
    for (let i=n-1; i>0; i--) {
      const j = Math.floor(Math.random() * (i + 1));
      [a[i], a[j]] = [a[j], a[i]];
    }
    for (let j=0; j<n; j++) cnt[a[j]][j]++;
  }
  return cnt; // すべて ~T/n 付近になれば良い
}

より厳密にはカイ二乗検定やコルモゴロフ–スミルノフ検定等で統計的に評価します（ここでは割愛）。

FAQ

Q. sort(Math.random)は小規模なら許容？

いいえ。常に非推奨。データ規模・ブラウザ実装に依存する偏りは、将来の不具合温床になります。

Q. 連想配列（オブジェクト）のシャッフルは？

Object.entries(obj)で配列化してシャッフルし、必要ならObject.fromEntriesで戻します。

Q. 重複を保ったままシャッフルできる？

もちろん可。Fisher–Yatesは要素の同一性を気にしません（比較やハッシュ不要）。

Q. TypeScript での型付けは？

export function shuffleInPlace<T>(arr: T[]): T[] {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

Appendix: 実装コレクション（コピペ用）

• 基本：shuffleInPlace / shuffle
• 暗号学的：cryptoShuffle
• シード再現：seededShuffle
• 部分シャッフル：shuffleTopK
• 重み付き：weightedShuffle
• ヒートマップ検査：testUniform

用途や要件（速度・公平性・再現性）に応じて選択してください。