Skip to content

Generating permutations of large arrays is complex

Published on in JavaScript

Last updated on

That's because it would take a very long time, and at some point you would have so many permutations that they wouldn't fit in an array.

Table of contents

Skip table of contents

Starting point

By "array permutations" I'm referring to my blog post from yesterday: Generating array permutations with all lengths in JS.

Here's the code:

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

getPermutations([1, 2, 3])
//=> [[1],  [2],  [1, 2],  [3],  [1, 3],  [2, 3],  [1, 2, 3]]

RangeErrors

The code throws if the input array's length is too long. In Firefox the limit is 20:

getPermutations(Array.from({ length: 19 })) // OK
getPermutations(Array.from({ length: 20 })) // RangeError
  • In Firefox, the error message is "too many function arguments."
  • In Chrome, Edge, Safari and Node.js, the error message is "Maximum call stack size exceeded."

Firefox's error message seems more helpful since the problem is that permutations.push() is called with too many arguments. In Firefox the limit is 500,000 items:

;[].push(...Array(500_000)) // OK
;[].push(...Array(500_001)) // RangeError

Avoiding RangeErrors

We could try to avoid the problem by avoiding the spread syntax altogether:

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

+    permutations.forEach((permutation) =>
+      permutations.push(permutation.concat(item))
+    )
+    permutations.push([item])

     return permutations
   }, [])

(I thought that this would also increase performance, but it doesn't seem to. Makes sense though: we do avoid iterating through newPermutations which is good, but now we are calling permutations.push() many more times with only one argument.)

It's slow

Now larger input arrays work, but getting permutations for large input arrays is increasingly slow:

console.time()
getPermutations(Array.from({ length: 20 }))
console.timeEnd() //=> ~200ms (on my machine)

console.time()
getPermutations(Array.from({ length: 21 }))
console.timeEnd() //=> ~400ms (on my machine)

console.time()
getPermutations(Array.from({ length: 22 }))
console.timeEnd() //=> ~800ms (on my machine)

console.time()
getPermutations(Array.from({ length: 23 }))
console.timeEnd() //=> ~1800ms (on my machine)

console.time()
getPermutations(Array.from({ length: 24 }))
console.timeEnd() //=> ~4200ms (on my machine)

Ain't nobody got time to wait that long!

The input array's length is still limited

In Firefox, the maximum length of an array seems to be 2 ** 32 - 1:

Array(2 ** 32 - 1) // OK
Array(2 ** 32) // RangeError: invalid array length

The length of the array returned by getPermutations(items) is incidentally 2 ** items.length - 1:

getPermutations(Array.from({ length: 1 })).length === 2 ** 1 - 1 // true
getPermutations(Array.from({ length: 2 })).length === 2 ** 2 - 1 // true
getPermutations(Array.from({ length: 3 })).length === 2 ** 3 - 1 // true
// ...
getPermutations(Array.from({ length: 10 })).length === 2 ** 10 - 1 // true
getPermutations(Array.from({ length: 11 })).length === 2 ** 11 - 1 // true
getPermutations(Array.from({ length: 12 })).length === 2 ** 12 - 1 // true
// ...and so on

(Math for calculating the total number of permutations.)

In other words, the maximum length of the input array is 32.

But input arrays that long would be impractical since getting all permutations would take way too long. Plus there would be quite many permutations: 2 ** 32 - 1 = 4,294,967,295. Over 4 billion!

Think of alternatives

Okay, so the input array's length is limited to 32 (in Firefox at least), and getting all permutations would take a very long time, so think:

  • Do you need to generate all permutations?
  • Do you need to retain all permutations?

Some pointers:

  • If you only need permutations that are e.g. 2 or 3 items long, there's no point in generating longer permutations.
  • If you are looking for a single permutation that matches a certain criterion, terminate the process after finding your solution.
    • Not possible if using an array reducer; use for loops and the break statement instead.
  • If you are looking for multiple permutations that match a certain criterion, skip non-matching permutations early, i.e. don't store them in the accumulator array.