カテゴリーはJavaScriptでコードもJavaScriptですが、どちらかというとアルゴリズム寄りの話です。たいがいのプログラミング言語では同様の方法で実装できる方法だと思います。
配列からランダムに複数の値を得たいということがあると思うのですが、普通にランダム関数でランダムの値を取得して、その配列のインデックスの値を取得しても重複してしまいます。
例えば下記のようなソースコード。
var arr = [1,2,3,4,5,6,7,8,9,10];
var randArr = [];
var rand;
for(var i=0,len=arr.length;i<5;i++){
rand = Math.floor( Math.random() * len); // 0～len-1の範囲の整数からランダムに値を取得
randArr.push(arr[rand]); // 配列のランダム値に対応するインデックスを得る
console.log("arr:" + arr);
console.log("randArr:" + randArr);
}
上記のコードは、arrという名前の配列からランダムに値を5つ取得してrandArrという配列に格納していくというプログラムですが、コンソールの結果は下記のようになりました。
arr:1,2,3,4,5,6,7,8,9,10 randArr:6 arr:1,2,3,4,5,6,7,8,9,10 randArr:6,6 arr:1,2,3,4,5,6,7,8,9,10 randArr:6,6,4 arr:1,2,3,4,5,6,7,8,9,10 randArr:6,6,4,10 arr:1,2,3,4,5,6,7,8,9,10 randArr:6,6,4,10,7
randArrの中の値は重複せずに入っていることもありますが、かなりの確率で重複してしまいます。
じゃあ、重複せずにランダムで複数の値を取得するにはどうすればいいか考えてみると、最初に配列をシャッフルしてシャッフルした後の最初の5つを取得すれば重複せずに取得できます。ただ、全体をシャッフルしなきゃいけないので無駄が多そうです。なお、余談ですが、ランダムシャッフルはFisher-Yates法がよさそうです(参考：svartalfheim.jp - 配列を少ない仕事量でシャッフルするFisher-Yates法)。
ところで、よくよく考えたら複数の値を取得する配列が変更可能であれば、ランダムに取得した値はなくして大丈夫なわけです。ということは、ランダムで得た値の箇所をランダム値の上限のインデックス(1回目は配列の最後の要素)で置き換え、次に取得するランダム値の範囲を1減らせばランダムで取得する範囲はすでに取得した値以外になるわけです。
例えば、下記のようなサンプルコード。
var arr = [1,2,3,4,5,6,7,8,9,10];
var randArr = [];
var rand;
for(var i=0,len=arr.length;i<5;i++,len--){
rand = Math.floor( Math.random() * len); // 0～len-1の範囲の整数からランダムに値を取得
randArr.push(arr[rand]); // 配列のランダム値に対応するインデックスを得る
arr[rand] = arr[len-1]; // ランダムに得た値の箇所を、インデックスがlen-1(ランダム値がとりうる最大の値)の要素に置き換える
console.log("arr:" + arr);
console.log("randArr:" + randArr);
}
コンソールには下記のように表示されました。
arr:1,2,3,4,5,6,10,8,9,10 randArr:7 arr:1,9,3,4,5,6,10,8,9,10 randArr:7,2 arr:1,9,3,4,5,8,10,8,9,10 randArr:7,2,6 arr:1,9,3,4,5,8,10,8,9,10 randArr:7,2,6,10 arr:1,9,3,4,8,8,10,8,9,10 randArr:7,2,6,10,5
元々の配列がかなり変更することになりますが、重複なく値を取得できています。ループ回数も取得したい値の数(上記の例では5)だけですみました。
上記はJavaScript以外のプログラミング言語のことも考えて実装したアルゴリズムです。実は、JavaScriptだと配列の指定の箇所を取り除くspliceというメソッドがあるので、それを使うと上記のプログラムは下記のように実装できます(参考：Array.splice - JavaScript | MDN)。
var arr = [1,2,3,4,5,6,7,8,9,10];
var randArr = [];
var rand;
for(var i=0,len=arr.length;i<5;i++,len--){
rand = Math.floor( Math.random() * len); // 0～len-1の範囲の整数からランダムに値を取得
randArr.push(arr.splice(rand,1)[0]); // 配列のランダム値に対応するインデックスを得たうえで元々の配列から取り除く
console.log("arr:" + arr);
console.log("randArr:" + randArr);
}
コンソールの結果は下記のようになりました。
arr:1,2,3,4,5,6,7,8,10 randArr:9 arr:1,2,3,4,6,7,8,10 randArr:9,5 arr:2,3,4,6,7,8,10 randArr:9,5,1 arr:2,3,4,7,8,10 randArr:9,5,1,6 arr:2,4,7,8,10 randArr:9,5,1,6,3
こちらだと元々の値を取得する配列は要素が減るだけなので、スッキリしています。もし、ランダム値を取得する順番をとわないのであれば、ランダムに値を減らした元々の配列に入っている値をランダムに取得した値と考えることもできそうです(例えば、100個の値が入っている配列からランダムに90個取得する場合、ループは90回でなく10回でいい)。
2014/05/13 23:39追記：spliceメソッドの戻り値は配列なので、0番目の値を入れるように指定しました。
コメント