JavaScriptで配列をシャッフルする方法

当ページのリンクには広告が含まれています。
JavaScriptで配列シャッフル






JavaScriptで配列をシャッフルする方法 — 完全ガイド


JavaScriptで配列をシャッフルする方法

sort(() => Math.random() - 0.5)」は本当に安全?——結論はいいえ。この記事では、Fisher–Yates(Knuth)シャッフルを中心に、暗号学的乱数、シード再現、部分シャッフル、重み付き、テスト手法、パフォーマンスまで、配列シャッフルのすべてを一気に学べます。

元配列 0 1 2 3 4 5 i を末尾から下げながら、 j ∈ [0, i] を一様に選んで swap 0 1=j 2 3 4 5=i

よくある誤り:sort(() => Math.random() - 0.5)

非推奨:比較関数は「順序の決定」に使われます。Math.random()を返すと、反射律/推移律の前提が崩れ、ソートアルゴリズムの内部実装に依存した偏りが入ります。配列の長さが大きいほどバイアスが顕著になります。
誤り:sort(() => Math.random() – 0.5) 内部実装依存 比較の推移律が崩れる → 一部の順列に偏り 正解:Fisher–Yates シャッフル 各ステップで未確定領域から一様に選択 全順列 n! を等確率に生成

図:ランダム比較での偏りと、Fisher–Yatesでの一様化の対比。

結論:使わない。代わりに次節のFisher–Yatesを使いましょう。

Fisher–Yates(Knuth)シャッフル:最短で正しい基本形

In-place / O(n) / 一様分布
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 がシャッフルされる
ポイント

  • i = n - 1から降順に走査し、j ∈ [0, i]を一様に選ぶ。
  • 各要素は等確率 1/nで全位置を取りうる。
  • 時間計算量 O(n)、追加メモリ O(1)

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

copy & shuffle
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を使います。

CSPRNG
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テスト・リプレイ可能なテスト・デモ動画作成に便利です。

Mulberry32 PRNG
// シンプルで速い 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件だけ抽出」などに。全体をシャッフルする必要はありません

O(n) / 最初のKをランダム化
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つずつ重み付きで取り出す方式を示します)。

重み付きサンプリング without replacement
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 での型付けは?

TS版
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: 実装コレクション(コピペ用)

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