Random array selection without selecting twice in JavaScript

Question

So, I am attempting to select a random entry from an array, and then make it so that particular entry will not be selected again until every entry has been selected. Basically, I don't want to see any of the same entries, until all of the entries in the array have been selected.

So if this were my array…

keywords =
[
 "ppc",
 "games",
 "advertise",
 "meta",
 "home",
 "gaming",
 "welcome"
]
var keyword = keywords[Math.floor(Math.random()*keywords.length)]
document.write(keyword);

I would not want to see an output of:

meta, advertise, home, meta, gaming, welcome, ppc, welcome

since meta was selected a second time before everything had been selected once. I would like to see something more like:

meta, advertise, gaming,ppc, welcome, home, games, advertise, ppc,

since this did not select any entry multiple times before every entry had been randomly selected.( the second loop started at the second "advertise" in case you didn't catch the differences.

But as you can see from the code that I have posted above, I do not know how to do this. I have seen examples where the entries that were randomly selected, were actually deleted from the array entirely but this is not what I want to do. I just want every entry to be selected once, and then for the process to be restarted.

Does anyone know the code for this?

possible duplicate of [array of random numbers](http://stackoverflow.com/questions/4373306/array-of-random-numbers) — Matt Ball, Aug 20 '11 at 17:19

score 8 · Answer 1 · edited May 23 '17 at 12:02

You could use the Array.sort() function to sort it randomly.

// random sort function
function shuffle(a, b)
{
   return Math.random() > 0.5 ? -1 : 1;
}

var keywords = ["ppc", "games", "advertise", "meta", "home", "gaming", "welcome"];

var randomKeywords = keywords.sort(shuffle); // new instance of a sorted randomly copy of the array

alert(randomKeywords);

update:

A better solution for shuffling is using Fisher-Yates Shuffle, as found in this answer.

function shuffle(array)
{
  var m = array.length, t, i;
  while (m > 0) 
  {
 i = Math.floor(Math.random() * m--);
 t = array[m];
 array[m] = array[i];
 array[i] = t;
  }
  return array;
}

var keywords = ["ppc", "games", "advertise", "meta", "home", "gaming", "welcome"];

shuffle(keywords); // shuffles the array

alert(keywords);

This doesn't work for me with Firefox and Opera on Linux. I need to take away the `-1` in `shuffle()`. If how sort handles `0` from the sorting function is implementation dependent then how about `return (Math.random() > 0.5) ? -1 : 1;` in the body of `shuffle()`? — sparklewhiskers, Sep 18 '12 at 06:35

score 5 · Answer 2 · answered Aug 20 '11 at 17:29

A very simplistic way to do this would be to use splice every times you select a random element and once the array is empty re-fill it with the original values.

Example :

(function () {
    var arr = [];

    window.getRandomThing = function () {
        if (arr.length === 0) {
            refill();
        }

        return arr.splice(Math.random() * arr.length, 1)[0];
    };

    function refill () {
        arr = [1,2,3,4,5];
    }
} ());

user113716 · Answer 3 · 2011-08-20T17:44:14.687

You can make a copy of the original Array, then use .splice() to grab a value at a random index, and remove it from the copy Array.

Because the copy is being reduced by one each time, you can simply do it while( copy.length ).

Example: http://jsfiddle.net/fMXTF/

var keywords = [
 "ppc",
 "games",
 "advertise",
 "meta",
 "home",
 "gaming",
 "welcome"
];

var copy = keywords.slice();

while( copy.length ) {

    var keyword = copy.splice( Math.floor(Math.random()*copy.length), 1 );
    document.write(keyword + '<br>');

}

Notice that the random number is based off copy.length, which, because of the .splice(), is reduced by 1 in each iteration. Therefore it ensures the random number is always based on the current length of the copy.

score 1 · Answer 4 · answered Aug 20 '11 at 17:18

If you don't mind the array changing you could randomize the order of the elements in the array and then print the array from first element to last.

OR

You could make another array of values 1 to N (where n is the number of elements). Randomize the order of that array and then use that as an index to the array as you iterate over it from the first to last.

score 0 · Answer 5 · edited May 23 '17 at 11:46

0

Stolen from user113716, but optimized it a bit.

var arr = [
    "ppc",
    "games",
    "advertise",
    "meta",
    "home",
    "gaming",
    "welcome"];

Array.prototype.shuffle = Array.prototype.shuffle || function () {
    var copy = this.slice(), arr = [];
    while (copy.length) arr.push(copy.splice((Math.random() * copy.length) << 0));
    return arr;
};

alert(arr.shuffle());

edited May 23 '17 at 11:46

Community

1
1

answered Apr 19 '13 at 15:50

yckart

32,460
9
122
129

score 0 · Answer 6 · answered Aug 20 '11 at 17:20

0

Store the numbers (indices) you've seen in a hash, then when you try look at a new word you can check the hash, if you've already seen it, generate a new number. Make sure to check to see if the hash length is the same as the array length though.

This avoids altering the array.

answered Aug 20 '11 at 17:20

HaloZero

475
4
15

But suppose you have an array of 1000 indices, the probability of finding a unique indice would grow exponentially with each iteration. For the last selection you would have a 1 in 1000 chance of ending the function. So the loop would be iterating an extra 1000 times, maybe even more. This also becomes more of a problem when you add indices. Your picking function could take minutes to end. – Krythic Apr 11 '17 at 02:29
The best solution is to pick a random indice, then swap that indice to the end of the array with the one you picked, then loop again using (array.Length - 1 - i) You're guaranteed an optimal selection of O/n. – Krythic Apr 11 '17 at 02:33

Random array selection without selecting twice in JavaScript

6 Answers6

Linked