Generating array permutations of all lengths in JS

Example: converting [1, 2, 3] into [[1],  [2],  [1, 2],  [3],  [1, 3],  [2, 3],  [1, 2, 3]].

Table of contents

Why?

I recall needing this a few times, maybe when solving Advent of Code puzzles.

Plus I really like my solution. I find it straightforward, maybe even obvious now. But it took me a while to come up with it – my first attempts were much more complex and didn't even work properly – and maybe that's why I'm keen on this simple solution.

Example input and output

const array = [1, 2, 3, 4]
getPermutations(array)
/* =>
  [
    [1],
    [2],
    [1, 2],
    [3],
    [1, 3],
    [2, 3],
    [1, 2, 3],
    [4],
    [1, 4],
    [2, 4],
    [1, 2, 4],
    [3, 4],
    [1, 3, 4],
    [2, 3, 4],
    [1, 2, 3, 4],
  ]
*/

Code

const getPermutations = (items) =>
  items.reduce((permutations, item) => {
    const newPermutations = permutations.map((permutation) =>
      permutation.concat(item)
    )
    permutations.push([item], ...newPermutations)
    returnpermutations
  }, [])

Probably not the most efficient solution, but straightforward and easy. And no for loops!

Order of permutations

The order of the final permutations change if you change the order of the push method's arguments:

 

 






 

 const items = [1, 2, 3]

items.reduce((permutations, item) => {
  const newPermutations = permutations.map((permutations) =>
    permutations.concat(item)
  )
  permutations.push([item], ...newPermutations)
  return permutations
}, [])
//=> [[1],  [2],  [1, 2],  [3],  [1, 3],  [2, 3],  [1, 2, 3]]

// versus

items.reduce((permutations, item) => {
  const newPermutations = permutations.map((permutations) =>
    permutations.concat(item)
  )
  permutations.push(...newPermutations, [item])
  return permutations
}, [])
//=> [[1],  [1, 2],  [2],  [1, 3],  [1, 2, 3],  [2, 3],  [3]]

In some cases the order might matter.

Beware too large input arrays

The code doesn't work if the input array's length is 20+:

getPermutations(Array.from({ length: 19 })) // OK
getPermutations(Array.from({ length: 20 })) // RangeError

More details in Part 2: Generating permutations of large arrays is complex.

Mutation

Notice how I'm mutating the accumulator array (permutations) in the reducer function?

Mutations can be bad, but in this case they are okay, because local mutations are all right.