JavaScript 配列からランダムに複数の要素を取り出す

配列から重複なくランダムに要素を取り出す方法についてメモメモ…

配列からランダムに重複なくn個の要素を抽出する方法です。たとえばこういう配列の中から値を3つ取り出したい！という場合にどうすればいいか、ということですね。

// ここから重複なく3つ取り出したい
const array = ["中居", "木村", "稲垣", "草彅", "香取"];

ググってみると「一旦もとの配列をランダムに並べ替えて、そのあとで最初のn個を取り出す」という方法が紹介されていました。というわけで、すぐ思いつくのがこういう方法。

// 配列からランダム(?)に3つ取り出す
const selected = array.slice().sort(function(){ return Math.random() - 0.5; }).slice(0, 3);

まずsort()関数を使って並べ替えた後、slice()関数でarray[0]からarray[2]までの値だけを取り出すという処理をしています。1行でシンプルに記述出来て、一見すると便利そうなのですが…

ただ、この方法には大きな落とし穴があります。それは、めちゃくちゃ偏るということです。実際に何度か実行してみると、配列の最初の値が明らかに多く出現したり、最後の値が全然出なかったりします。というのも、この方法は比較関数を指定し「隣り合う値を入れ替えるかどうか」をランダムに決めているだけなので、配列の両端にある要素がほとんど比較されず動かないのです。sort()の実装方法にもよると思いますが、まず間違いなく偏ります。

問題はまだあります。この方法だと、要素を取り出す前にいちいち配列全体を並び替えなければいけないのです。上の例であれば要素は5個ですが、これが何千、何万となれば間違いなくパフォーマンスにも影響が出てきます。取り出したいのはたった3個なのに！

このあたりの問題点はWikipediaのフィッシャー–イェーツのシャッフルの項目でも言及されています。

シャッフルによる手法の派生として、プログラミング言語がサポートしている、ユーザ独自拡張の比較機能を使用して、比較時にランダムな値を返すようにしてシャッフルを行う方法がある。しかし、これは「きわめて悪い方法」であり、この方法は結果がまったく均等に分布せず、ソートのアルゴリズムもきわめて重い。

というわけで上記の問題点を解決したのが次のコードです。

const array = ["中居", "木村", "稲垣", "草彅", "香取"];
const selected = randomSelect(array.slice(), 3);
 
// 配列arrayからランダムにnum個の要素を取り出す
function randomSelect(array, num)
{
  let newArray = [];
  
  while(newArray.length < num && array.length > 0)
  {
    // 配列からランダムな要素を選ぶ
    const rand = Math.floor(Math.random() * array.length);
    // 選んだ要素を別の配列に登録する
    newArray.push(array[rand]);
    // もとの配列からは削除する
    array.splice(rand, 1);
  }
  
  return newArray;
}

考え方はFisher–Yates shuffleとまったく同じ。「残っている要素の中からランダムにひとつ選び出し、横によけていく」という処理を繰り返します。Fisher–Yates shuffleは配列のすべての要素を選び終える(配列全体を並べ替える)まで続きますが、今回は3個だけ選べばいいので、3個選んだ時点で終わりです。

ではとりあえず実際に試してみます。悪い方法(最初に紹介したsort()の比較関数を使う方法)と悪くない方法(並び替えはせずランダムな要素を順に取り出していく方法) を比べてみてください。環境にもよりますが「悪い方法」だと各要素の選ばれた回数に偏りが出るはずです。

悪い方法　　悪くない方法
　　

中居	木村	稲垣	草彅	香取
0	0	0	0	0

注意点は、randomSelect()関数にもとの配列をそのまま渡すと、関数内のsplice()によって選び出した分の要素が削除されてしまうことです。もとの配列に変更を加えられたくない！という場合は上の例の2行目のように一旦slice()でコピーを作成してから渡すようにするか、randomSelect()関数内でコピーを作るように書きかえてください。

上のコードだと長いので、ギュッとちぢめてこんなふうにも書けます。

const array = ["中居", "木村", "稲垣", "草彅", "香取"];
const copy = array.slice();
const selected = [...Array(3)].map(() => copy.splice(Math.floor(Math.random() * copy.length), 1)[0]);

map()を使って新しい配列の各要素にランダムに抽出した値を放り込んでいます。取り出したい要素の数がもとの配列の要素数を超えないように注意。

細かいことを考えなければ、とりあえずこれで目的は果たせます。もしかしたら「ループ内でlengthにアクセスするな！」とか「splice()は遅いから使うな！」という人もいるかもしれませんが、そういう人はあらかじめlengthを変数に代入しておくなり、要素を削除するかわりに配列の端によけておくなり適宜変更を加えてください。ま、あくまで参考程度ということで…。