Javascript : Exclude an element from a random set - (curiosity)

Question

I have a question regarding javascript Math.random():

I have (for a game I'm building) to randomly generate every number from a given set (i.e. from 0 to 1000) and every time I have to generate a number, I have to check if that number has already been "generated".

The solution is pretty easy thinking about a simple algorithm that checks if the random integer is already present in the generated set. It loops generating numbers until it can't find it. A snippet below:

/* ... */
for(var i = 0; i<upperBound; i++){
    var randN = Math.floor(Math.random()*upperBound);
    while(myRandomNumbers.contains(randN)){
        loops++;
        randN = Math.floor(Math.random()*upperBound);
    }
    myRandomNumbers.push(randN);
}
/* ... */

running example here

I'd like to know: is this the best way to achieve this? or are there any ways, instead of looping until it generates a "good" number, to exclude a particular set in the random generation?

Thanks a lot everyone!

Maybe [this answer](http://stackoverflow.com/questions/3796786/random-number-generator-without-dupes-in-javascript) will help. Or [this one](http://stackoverflow.com/questions/2380019/generate-8-unique-random-numbers-between-1-and-100). — user113716, Jan 14 '11 at 15:16

score 3 · Accepted Answer · answered Jan 14 '11 at 15:20

3

Generate the set of numbers in order.
Sort the list randomly.

Here's an example using a naive, biased sort:

for (var nums=[],i=0;i<1000;++i) nums[i]=i+1;
nums.sort(function(){ return Math.random()-0.5 });

Then you can just pop() numbers off of nums to get the next 'random' number, guaranteed to never have been used before.

answered Jan 14 '11 at 15:20

Phrogz

296,393
112
651
745

As noted in the answer, this won't give a very random distribution, and will have different bias in different browsers. The Fisher-Yates shuffle isn't that much more code and will do much better. – Tim Down Jan 14 '11 at 15:37
See the `shuffle()` function in the file I linked to for an implementation of Fisher-Yates. – Phrogz Jan 14 '11 at 15:57

Shawn Chin · Answer 2 · 2011-01-14T15:26:46.320

1

If your range of number is not prohibitively large, you could simply generate a list with all the numbers, randomise it, then pick it off one by one.

Here's a quick hack of your sample implementation to show this method in action: http://www.jsfiddle.net/ZTLt9/8/

edited Jan 14 '11 at 15:26

answered Jan 14 '11 at 15:18

Shawn Chin

84,080
19
162
191

score 1 · Answer 3 · answered Jan 14 '11 at 15:30

I'd create an array and randomly shuffle it:

function shuffle(arr) {
    var shuffled = arr.slice(0), i = arr.length, temp, index;
    while (i--) {
        index = Math.floor(i * Math.random());
        temp = shuffled[index];
        shuffled[index] = shuffled[i];
        shuffled[i] = temp;
    }
    return shuffled;
}

// Create the array
var i = 1000, arr = [];
while (i--) arr[i] = i;

// Shuffle it
arr = shuffle(arr);

score 0 · Answer 4 · answered Jan 14 '11 at 15:18

What about an array of booleans 1001 big.

When you want to check of the number has been generated, all you need to do is check the number at that position in the array:

if (!arr[randomnumber]){
    arr[randomnumber] = true;
}

At the end, you can scan the array to find the numbers you need.

This has the added side effect of sorting your numbers, as the scan will pick them out in order.

Something similar to this was the subject of one of my blog posts: http://www.jameswiseman.com/blog/2010/05/27/generate-and-sort-lottery-numbers/

Herohtar · Answer 5 · 2011-01-14T15:45:51.530

The best way would probably be to generate an array of numbers, then shuffle it using the Fisher-Yates shuffle.

Here is the JavaScript example given in the Wikipedia article:

var n = a.length;
for(var i = n - 1; i > 0; i--) {
    var j = Math.floor(Math.random() * (i + 1));
    var tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

(This assumes you have an array 'a' that contains the items you wish to shuffle.)

Javascript : Exclude an element from a random set - (curiosity)

5 Answers5