かんたんなアルゴリズムのミス？？ランダムな数を重ならないように配列に入れる

Question

変数pNum[]にランダムな数を重ならないように入れたいのですが、なぜかうまくいきません。
多分この部分だと思うのですが、チェックしてもらえませんか？

	Q_MAX = ans.length;
	i = 0;
	a = 0;
	while(i < Q_MAX){
		qNum[i] = Math.floor(Math.random() * Q_MAX);
		while(a < qNum.length - 1 && i > 0){
			if(qNum[i] == qNum[a]){
				i--;
				a = 0;
				break;
			}
			a++;
		}
		i++;
	}

Answer 1

コードから類推するに 要素数 Q_MAX の配列に、0 ～ Q_MAX-1 までの数を重複しないように入れる、
ということですよね。

ならば、0 ～ Q_MAX-1 までの整数をランダムに並べ替える（シャッフルする）というロジックの方がいいと思います。
現状のロジックだと後に行くほど重複する確率が高くなり、再試行が多発します。

シャッフルのjQueryプラグインが下記にありますので、それを利用すると簡単です。

jQuery: Shuffle Plugin – Yelotofu

上記のプラグインをコピーしておいて、

Q_MAX = ans.length;
i = 0;
for (i = 0; i < Q_MAX; i++) {
    qNum[i] = i;
}

qNum = $.shuffle(qNum);

追記：jQueryタグがついてなかったので、jQueryなしで。

//シャッフルメソッドを定義
Array.prototype.shuffle = function() {
  var i = this.length;
  while (i) {
    var j = Math.floor(Math.random()*i);
    var t = this[--i];
    this[i] = this[j];
    this[j] = t;
  }
}

var qNum = [];
Q_MAX = 10;
//0 ～ 9 までの連番の配列を生成
for (i = 0; i < Q_MAX; i++) {
    qNum[i] = i;
}
//配列をシャッフル
qNum.shuffle();

上記のシャッフルメソッドはFisher–Yates shuffleという割と有名なアルゴリズムで偏りなく高速にシャッフルできます。

ちなみに、質問のコードの間違いは、aの初期化の位置ですね。重複チェックのループの前で初期化しないと。

    while(i < Q_MAX){
        qNum[i] = Math.floor(Math.random() * Q_MAX);
        a = 0; //ここで初期化
        while(a < qNum.length - 1 && i > 0){
            if(qNum[i] === qNum[a]){
                i--;
                break;
            }
            a++;
        }
        i++;
    }

Answer 2

質問文のコードをベースにしたものを示します。

var qNum = [];
Q_MAX = 10; // qNum.length;

var idx = 0;
while (idx < Q_MAX) {
  // 追加する数の候補
  n = Math.floor(Math.random() * Q_MAX);

  // 重複をチェックする。
  var exists = false;
  for (var a = 0; a < idx; a++) {
    if (n == qNum[a]) {
      exists = true;
      break;
    }
  }

  if (exists) {
    // 値が重複していたので、値を選び直す。
    continue;
  }

  // 値を登録する。
  qNum[idx] = n;
  idx++;
}

console.log(qNum);

実行例 (node.js で実行)

$ node 111.js
[ 8, 3, 7, 0, 5, 1, 9, 4, 2, 6 ]

$ node 111.js
[ 6, 1, 7, 8, 3, 9, 5, 4, 2, 0 ]

Answer 3

質問を取り違えた様子ですので、削除

Answer 4

場当たりで書くんではなくて、こんな感じで、処理単位ごとに。

function makeUniqArr(count)
{
	var arr = [];

	//重複を判定する
	//重複があれば true を返す
	var check_duplicate = function(arr, num) {
		//処理
		return false;
	};

	// ランダムな数値を生成する
	var mkRand = function() {
		//処理
		return int;
	};

	//指定回数分ループ
	for (var i = 0; i < count; i++) {
		var num = mkRand();
		if (check_duplicate(arr, num)) {
			i--;
		} else {
			arr[i] = num;
		}
	}

	return arr;
}

Comments

[otftrough]

見やすくなって、書きやすさも上がりました。ありがとうございます。