JSの重複なしランダム

メタデータ

公開日：2018/11/05
更新日：2021/07/10
カテゴリ：コード
タグ：JavaScript

リアクション

シェア寄付

【こちらは前サイトからの移植記事になります。】

概要

重複なしのランダムな値をとるjsについて、アルゴリズムを理解しつつ書きたい。

そしたら、今までなんとなく書いてたところもなんとなくわかった。

ちなみに、朝に余裕ができたので、この記事から朝書いて公開することにしました。

いっぱいあるけど

ググれば重複しないランダムな値をとるjsは出てくるのですが、なんでそうなるのか理解しないといつまでたってもコピペで対応しちゃう。ので、アルゴリズムの方を参考にして、書けばいいと思った。

フィッシャー–イェーツのシャッフル

wikipediaによると、アルゴリズム(改良版)は下記の通り。

要素数が n の配列 a をシャッフルする(添字は0からn-1):

i を n – 1 から 1 まで減少させながら、以下を実行する

j に 0 以上 i 以下のランダムな整数を代入する

a[j] と a[i]を交換する

コード

それじゃ、上記を文章通りコードにしてみます！！

//配列a
let a = ['あ','い','う','え','お','か','き','く','け','こ'];
let n = a.length;

//whileでの書き方
let i = n - 1;
while(i) {
	let j = Math.floor( Math.random() * i );
	let k = a[i];
	a[i] = a[j];
	a[j] = k;
  i = i - 1;
}

//forでの書き方
for(let i = n - 1; i > 0; i = i - 1){
	let j = Math.floor( Math.random() * i);
	let k = a[i];
	a[i] = a[j];
	a[j] = k;
}

console.log(a);

//配列a

let a = ['あ','い','う','え','お','か','き','く','け','こ'];

let n = a.length;

//whileでの書き方

let i = n - 1;

while(i) {

let j = Math.floor( Math.random() * i );

let k = a[i];

a[i] = a[j];

a[j] = k;

i = i - 1;

}

//forでの書き方

for(let i = n - 1; i > 0; i = i - 1){

let j = Math.floor( Math.random() * i);

let k = a[i];

a[i] = a[j];

a[j] = k;

}

console.log(a);

これで、aの配列内の順番が並び変わっているかと思います。

で、これをスリムにします。

//配列a
let a = ['あ','い','う','え','お','か','き','く','け','こ'];
let n = a.length;

//whileでの書き方
while(n--) {
	let j = Math.floor( Math.random() * n );
	let k = a[n];
	a[n] = a[j];
	a[j] = k;
}

//forでの書き方
for(n > 0; n--;){
	let j = Math.floor( Math.random() * n);
	let k = a[n];
	a[n] = a[j];
	a[j] = k;
}

console.log(a);

//配列a

let a = ['あ','い','う','え','お','か','き','く','け','こ'];

let n = a.length;

//whileでの書き方

while(n--) {

let j = Math.floor( Math.random() * n );

let k = a[n];

a[n] = a[j];

a[j] = k;

}

//forでの書き方

for(n > 0; n--;){

let j = Math.floor( Math.random() * n);

let k = a[n];

a[n] = a[j];

a[j] = k;

}

console.log(a);

変数iを省略できるので、１行減りました。

ループはforかwhileか

少数の配列ではforが、配列の中身が50こを超えたくらいからはwhileの方が早かったです。配列の要素がもっと長ければ、もっと早い段階で違いがでたのかな？

計測方法は、関数の前後の時間を測って差分を計算するものです。簡単だから、あんまり正確じゃないかも。

デクリメント

インクリメント/デクリメントについて、前でも後ろでも挙動同じかと思ってました。っていうか、普段forでしか++使わずに他は+1使ってたから気づいてなかった。←この理由は自分でもよくわからん。なんとなく。

whileの書き方は、他にも同じくらいスリム化した書き方があって、その時に気づいた。

//n--でも--nでもいい
while(n--) {
	let j = Math.floor( Math.random() * n );
	let k = a[n];
	a[n] = a[j];
	a[j] = k;
}

//--nじゃないとだめ
while(n) {
	let k = a[--n];
	let j = Math.floor( Math.random() * n );
	a[n] = a[j];
	a[j] = k;
}

//n--でも--nでもいい

while(n--) {

let j = Math.floor( Math.random() * n );

let k = a[n];

a[n] = a[j];

a[j] = k;

}

//--nじゃないとだめ

while(n) {

let k = a[--n];

let j = Math.floor( Math.random() * n );

a[n] = a[j];

a[j] = k;

}

–nだと他のnにも影響するのね。今度からインクリメント/デクリメントも使ってみようかな。