How would you keep a Math.random() in javascript from picking the same numbers multiple times?

Question

I have an array var words = []//lots of different words in it. I have a Math.floor(Math.random()*words.length) that chooses a random word from the array. This is run in a loop that runs for a random number of times (between 2 and 200 times). I would like to make sure that the random numbers do not get chosen more than once during the time that that loop runs. How would you suggest doing this?

Answer 1

There's multiple ways of doing this.

You can shuffle the entire collection, and just grab items from one end. This will ensure you won't encounter any one item more than once (or rather, more than the number of times it occured in the original input array) during one whole iteration.

This, however, requires you to either modify in-place the original collection, or to create a copy of it.

If you only intend to grab a few items, there might be a different way.

You can use a hash table or other type of dictionary, and just do a check if the item you picked at random in the original collection already exists in the dictionary. If it doesn't, add it to the dictionary and use it. If it already exists in the dictionary, pick again.

This approach uses storage proportional to the number of items you need to pick.

Also note that this second approach is a bit bad performance-wise when you get to the few last items in the list, as you can risk hunting for the items you still haven't picked for quite a number of iterations, so this is only a viable solution if the items you need to randomly pick are far fewer than the number of items in the collection.

Answer 2

There are several different approaches, which are more or less effective depending on how much data you have, and how many items you want to pick:

• Remove items from the array once they have been picked.
• Shuffle the array and get the first items.
• Keep a list of picked items and compare against new picks.
• Loop through the items and pick values randomly based on the probability to be picked.

Answer 3

There are several solutions to this.

What you could do is use .splice() on your array to remove the item which is hit by words.

Then you can iterate over your array until it's empty. If you need to keep the array pristine you can create a copy of it first and iterate over the copy.

var words = ['apple', 'banana', 'cocoa', 'dade', 'elephant'];
while (words.length > 0) {
    var i    = Math.floor(Math.random()*words.length);
    var word = words.splice(i, 1)[0];
}

Or something to that effect.

Answer 4

I'd try using a map (Object literal) instead of an Array with keys being indexes:

var words = [ /* ... */ ] , map = { } , length = words.length ;
for(var n = 0 ; n < length ; n++) map[n] = words[n] ;

then make a function to pick a random entry based on the length, delete the entry (hence the index) and adjust the length:

function pickRandomEntry() {

    var random = Math.floor( Math.random() * length ) ;

    var entry = map[random] ;

        delete map[random] ;
        length-- ;

    return entry ;

}

with this approach, you have to check for an undefined return value (since random might return the same number) and run the function again until it returns an actual value; or, make an array of picked indexes to filter the random numbers (which will however slow performance in case of long iteration cycles).

HTH

Answer 5

I'd shuffle the array as follows and then iterate over the shuffled array. There's no expensive array splice calls and the shuffling routine consists of swapping two values in the array n times where n is the length of the array, so it should scale well:

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;
}

console.log(shuffle(["one", "two", "three", "four"]));

Answer 6

this is how you can do it without shuffling the whole array

a = "abcdefghijklmnopq".split("");
c = 0;
r = [];

do {
   var len = a.length - c;
   var rnd = Math.floor(Math.random() * len);
   r.push(a[rnd]);
   a[rnd] = a[len - 1];
} while(++c < 5);

console.log(r);

the idea is to pick from 0..(length - step) elements and then shift the picked element towards the end.

Answer 7

Here is a way with prime numbers and modulo that seems to do the trick without moving the original array or adding a hash:

<html>
<head>
</head>
<body>
 <a href="javascript:" onclick="shuffle(['48','49','50','51','52','53','54','55','56','57','58','59','60','61','62','63','64','65','66','67','68','69','70','71','72','73','74','75','76','77','78','79','80','81','82','83','84','85','86','87','88','89','90','91','92','93','94','1','2','3','4','5','6','7','8','9','10','11','12','13','14','15','16','17','18','19','20','21','22','23','24','25','26','27','28','29','30','31','32','33','34','35','36','37','38','39','40','41','42','43','44','45','46','47','95','96','97','98','99'])">shuffle</a>
 <div id="res"></div>
 <script>
    function shuffle(words){
        var l = words.length,i = 1,primes = [43,47,53,59,61,67,71,73,79],//add more if needed
        prime = primes[parseInt(Math.random()*primes.length, 10)],
        temp = [];
        do{
            temp.push((i * prime) % l);
        }while(++i <= l);
        console.log(temp.join(','));
        console.log(temp.sort().join(','));
    }
 </script>
</body>
</html>