Shuffling an Array in JS

by kirupa | 19 June 2012

Let's say you have an array whose data is the numbers 1 through 8 stored sequentially as visualized below:


This is a companion discussion topic for the original entry at http://www.kirupa.com/html5/shuffling_array_js.htm

Thanks a lot for this explanation, it really helped me!!
Keep up the good work!
Regards,
Javi.

1 Like

Glad you liked it :slight_smile:

Thank you, this was really helpful. I am wondering how you would prevent the output of a permutation that has previously been outputted?

That’s a fun question, @marisaofworld :stuck_out_tongue: I tried a few approaches using something similar to what I had in the Removing Duplicate Items from an Array approach and came up with the following:

Array.prototype.shuffle = function() {
  let input = this;
  
  for (let i = input.length-1; i >=0; i--) {
  
    let randomIndex = Math.floor(Math.random()*(i+1)); 
    let itemAtIndex = input[randomIndex]; 
    
    input[randomIndex] = input[i]; 
    input[i] = itemAtIndex;
  }
  return input;
}

let tempArray = [1, 2, 3];

let uniqueTable = {};

// test out a bunch of arrays
for (let i = 0; i < 50; i++) {
  tempArray.shuffle();
  
  // create a flattened string of array values
  let flattened = tempArray.join("-");
  
  // test for uniqueness using this flattened string
  if (uniqueTable[flattened] === undefined) {
    uniqueTable[flattened] = "set";
    console.log(i + " " + tempArray);
  }
} 

Some of the other JS experts here may come up with some additional and better solutions :triangular_ruler:

Cheers,
Kirupa :slight_smile:

Kirupa’s solution here does suffer from having to repeat itself. And it is possible that the loop doesn’t find a new solution or gets stuck for a long time trying to find the next one (depending on how its run).

Ideally you’ll want to have a known set of solutions then pull from those randomly. And that’s something we can do :wink:

It can potentially take a lot of work to figure out all the solutions at once, so we can reduce the initial load by only calculating each solution when they’re requested. Each solution will be represented initially by a number starting with 0 up to the number of solutions - 1. Then, given any number in that set, a unique solution can be derived.

For array permutations like this, the number of solutions (variations in the shuffling of the array) is the factorial of the length of the array. Given that, we can make an array with all the values 0 up to the factorial and those values will represent the solutions. Then, as a new solution is requested, that value is removed from the array leaving only the unseen solutions.

A fun way to handle this on-demand value taking is with generators. We can write a loop that would produce all the variations at once but by using a yield, we can make it so the values produced are only calculated each time the caller of the generator asks for it. The loop in the generator will get paused and will only resume on the next request.

Time for some code:

// helpers
function factorial (n) {
    return n > 1 ? n * factorial(n - 1) : 1
}

function swap (arr, i, j) {
    if (i === j) return
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}
// shuffle generator
function * getShuffles (source) {
    let count = source.length
    let total = factorial(count)
    let values = [...Array(total).keys()]
    while (values.length) {
        let result = source.slice()
        let randIndex = Math.floor(Math.random() * values.length)
    	let value = values.splice(randIndex, 1)[0]
        let div = total
        for (let i = 0; i < count - 1; i++) {
            div /= count - i
            swap(result, i, i + Math.floor(value/div))
            value %= div
        }
        yield result
    }
}

With a generator, we call it first to get an iterator, then use the iterator to get multiple yielded values by calling next() and checking the value property the returned object.

let shuffleIter = getShuffles([1, 2, 3])
console.log(shuffleIter.next().value) // [3, 2, 1]
console.log(shuffleIter.next().value) // [1, 3, 2]
console.log(shuffleIter.next().value) // [2, 3, 1]
// ...

When the iterator has expended all of its permutations (since there is a limited set before you have to start repeating if you want more) the value will be undefined and the done property in the object returned by next() will be true. To get more shuffles, you’ll have to call the generator again and get a new iterator with a new set of randomized shuffles.

You can also get all the iterations at once by spreading the iterator in an array (if you want an array or arrays) or using a for…of loop.

for (let shuffle of getShuffles([1, 2, 3])) {
    console.log(shuffle)
}
/* outputs
[3, 1, 2]
[2, 1, 3]
[1, 3, 2]
[2, 3, 1]
[1, 2, 3]
[3, 2, 1]
*/
1 Like

senocular, that is an elegant solution. Also well explained.

1 Like

Agreed! That is a nice solution @senocular :slight_smile: