Random array selection without selecting twice in

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?

Answer 1

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());

Answer 2

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];
    }
} ());

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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