JavaScriptで重複しない乱数を生成する - どうでもいいプログラム研究所

f:id:tdyu5021:20190504020858p:plain

プログラミングでよく必要になるのが、重複しないランダムな数の生成です。出典は忘れてしまったのですが、以前どこかのサイトで非常にスマートな記述方法が載っており感動したので、備忘録としてメモします。JavaScriptでの例です。

重複しない乱数生成のJavaScriptのコード

早速ですが、コードは以下です。下記の例では配列numArrに1から5までの数字をランダムに１つずつ格納するコードです。

function randomizing(){
   var arr = [];
   numArr = []; 
   for(var i=0; i < 5; i++){
      arr[i]=i+1;
   }

   for(var j = 0, var len = arr.length; j < 5; j++, len--) {
      rndNum = Math.floor(Math.random()*len);
      numArr.push(arr[rndNum]);
      arr[rndNum] = arr[len-1];
   }
}

重複しない乱数を生成するロジック

では、上記のコードでなぜ重複しない乱数ができるのかを見ていきましょう。

生成した乱数を格納するnumArrという配列をつくる
上記とは別に配列（arr）を作り、ランダムに生成したい値（今回は1,2,3,4,5）を順にいれておく
乱数を生成（Math.floor(Math.random()*len)）する・・・①とする
配列numArrの中に、配列arrの[①で生成した乱数]番目の数をpushで追加する
配列arrの中で、[①で生成した乱数]番目のところに、[arrの配列の要素数-1]番目の数字を埋めていく
乱数を生成したい数だけforループで繰り返す（上記の例では5回）。その際、arrの配列の要素数の数字を１つずつ減らしていく

最初見たときこのコードが理解できませんでした。なぜ上記のステップ5でarrの[乱数]番目のところに[arr配列の要素数]番目の数字をいれるのでしょうか。順番に見ていきます。

まず、１～６行目のコードが実行されると配列arrには以下の要素が入っていることになります。

arr[0] =1
arr[1] =2
arr[2]= 3
arr[3]= 4
arr[4] =5

まず乱数の生成で2の数字が出たとしましょう。arr[2]は3ですから、numArrに3の値をpushして次のようになります。

numArr[0] =3
numArr[1] = ""
numArr[2] = ""
numArr[3] = ""
numArr[4] = ""

先ほど言及した、”ステップ5でarrの[乱数]番目のところに[arrの配列の要素数-1]番目の数字を入れる（arr[rndNum] = arr[len-1]）を実行すると以下になります。

arr[0] =1
arr[1] =2
arr[2]= 5
arr[3]= 4
arr[4] =5

ここが最大のポイントです。この配列を見るとarr[2]も5だしarr[4]も5なので、一瞬それでいいの？と思ってしまいます。

しかし、この処理が終わった後forループがはじめに戻るわけですが、初期値が5の変数lenは1つ値が減るためMath.floor(Math.random()*len)で生成されるrndNumの値は0～3に限られます。

つまり次に配列arrから値を持ってくるときは、もう二度とarr[4]が選ばれることはないのです（arr[0]、arr[1]、arr[2]、arr[3]しか選ばれない）。

試しにこの状態でもう一度乱数を生成してみましょう。次の乱数に1が生成されたとしたら、arr[1]は2が格納されているので、numArrにプッシュすると以下のようになります。

numArr[0] =3
numArr[1] =2
numArr[2] =""
numArr[3] =""
numArr[4] =""

arr[1]にはarrの「arrの要素数-1」番目にあった”4”をいれるので以下のようになります。

arr[0] =1
arr[1] =4
arr[2]= 5
arr[3]= 4
arr[4] =5

しつこいですが、さらに繰り返してみましょう。forループで、乱数の2が出現したとすると以下のようになります。

numArr[0] =3
numArr[1] = 2
numArr[2] =5
numArr[3] = ""
numArr[4] = ""

arr[0]=1
arr[1]=4
arr[2]=3
arr[3]=4
arr[4]=5

繰り返しにはありますが、このプログラムでは乱数の生成で以下の青の数字が生成されると、そのループ時点での[arr配列arrの要素数-1]番目の値が右辺に代入されます。

arr[0]=XXX
arr[1]=XXX
arr[2]=XXX
arr[3]=XXX
arr[4]=XXX

Math.random()*lenのうち変数lenが１つずつどんどん減っていくため、発生する乱数の範囲が縮まり、得られる数字が限られてしまうのですが、その限られたarr[X]には、[すでに発生しない乱数]番のarrの値をいれておくことで、必要なものが得られるという仕組みなっているのです。

こうすることでたとえ乱数がどんな順番でどんな数がでてきても必ず重複しない乱数が無駄なループなしに得られるのです。試しに、乱数の０が５回連続で出たとしても、1～5までの数が得られます。

私が最初にこの仕組みを知ったときとても感動しました。一体どうやればこんなコードを思いつくのだろうか想像も付きませんが、真のプログラマーやアルゴリズムを考えられる方は本当に尊敬します。