# Shuffling an Array in JS

**URL:** <https://forum.kirupa.com/t/shuffling-an-array-in-js/399225>\
**Category:** programming\
**Created:** [December 2, 2014, 12:51am UTC](https://forum.kirupa.com/t/shuffling-an-array-in-js/399225 "2014-12-02T00:51:09Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [December 2, 2014, 12:51am UTC](https://forum.kirupa.com/t/shuffling-an-array-in-js/399225/1 "2014-12-02T00:51:10Z")

</div>

by [kirupa](http://www.kirupa.com/me/index.htm) | 19 June 2012

Let's say you have an [array](http://www.kirupa.comarrays_javascript.htm) 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](http://www.kirupa.com/html5/shuffling_array_js.htm)

---

<div class="post-metadata">

**Author:** ![javisp](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/javisp/32/8656_2.png) [@javisp](https://forum.kirupa.com/u/javisp)\
**Post date:** [August 30, 2017, 12:03pm UTC](https://forum.kirupa.com/t/shuffling-an-array-in-js/399225/2 "2017-08-30T12:03:44Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [August 30, 2017, 3:07pm UTC](https://forum.kirupa.com/t/shuffling-an-array-in-js/399225/3 "2017-08-30T15:07:44Z")

</div>

Glad you liked it 🙂

---

<div class="post-metadata">

**Author:** ![marisaofworld](https://avatars.discourse-cdn.com/v4/letter/m/b4bc9f/32.png) [@marisaofworld](https://forum.kirupa.com/u/marisaofworld)\
**Post date:** [October 1, 2019, 11:00am UTC](https://forum.kirupa.com/t/shuffling-an-array-in-js/399225/4 "2019-10-01T11:00:18Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [October 2, 2019, 12:29am UTC](https://forum.kirupa.com/t/shuffling-an-array-in-js/399225/5 "2019-10-02T00:29:15Z")

</div>

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](https://www.kirupa.com/html5/removing_duplicate_items_from_an_array.htm) 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 🙂

---

<div class="post-metadata">

**Author:** ![senocular](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/senocular/32/7217_2.png) [@senocular](https://forum.kirupa.com/u/senocular)\
**Post date:** [October 2, 2019, 6:17am UTC](https://forum.kirupa.com/t/shuffling-an-array-in-js/399225/6 "2019-10-02T06:17:47Z")

</div>

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:

```javascript
// 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
}

```

```javascript
// 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.

```javascript
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.

```javascript
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]
*/

```

---

<div class="post-metadata">

**Author:** ![REB\_412](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/reb_412/32/9233_2.png) [@REB\_412](https://forum.kirupa.com/u/REB_412)\
**Post date:** [October 2, 2019, 11:15pm UTC](https://forum.kirupa.com/t/shuffling-an-array-in-js/399225/7 "2019-10-02T23:15:38Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [October 3, 2019, 12:06am UTC](https://forum.kirupa.com/t/shuffling-an-array-in-js/399225/8 "2019-10-03T00:06:52Z")

</div>

Agreed! That is a nice solution @senocular🙂