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

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

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

Cheers,

Kirupa

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

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