I recently came across code that looked something like this (generates 4 random numbers in an array, this is not the actual code, I just wrote this up now, so it's untested):
var uniqueNumbers = new Array();
var count = 4;
var max = 10;
function main() {
for (var i = 0; i < count; i++) {
do {
var tempNum = Math.floor(Math.random() * max); //number 0-9
} while (arrayContains(uniqueNumbers, tempNum))
uniqueNumbers.push(tempNum);
}
}
function arrayContains(a, val) {
for (var i = 0; i < a.length; i++) {
if (a[i] == val) return true;
}
return false;
}
Is it possible that the while
loop could possibly be infinite (or at least take a lot of time)? In the way that it just so happens that we continuously randomly choose a number that happens to be in the array? I imagine the probability of this happening would go up as count
increases. It's kind of reminding me of bogosort.
I would think that this would be improved by selecting from a diminishing 'pool' of numbers, instead of selecting randomly, something like:
var uniqueNumbers = new Array();
var count = 4;
var max = 10;
var pool = new Array();
function main() {
createPool();
for (var i = 0; i < count; i++) {
if (var tempNum = selectFromPool()) {
uniqueNumbers.push(tempNum);
}
}
}
function createPool() {
for (var i = 0; i < max; i++) {
pool.push(i);
}
}
function selectFromPool() {
if (pool.length <= 0) return false;
var selectedIndex = Math.floor(Math.random() * pool.length);
var selectedValue = pool[selectedIndex];
pool = pool.slice(selectedIndex, selectedIndex+1);
return selectedValue;
}
Is this a better, less fragile way of doing it? Or is there some proof that the while
loop will never be infinite because of the pseudo-random nature of computer generated random numbers?