Skip to content

Finding array item combinations for 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 combinations that they wouldn't fit in an array.

Table of contents

Skip table of contents

Starting point

By "array item combinations" I'm referring to my blog post from yesterday: Finding all possible combinations of array items in JS.

Here's the code:

const getCombinations = (items) =>
  items.reduce((combos, item) => {
    const newCombos = combos.map((combo) => combo.concat(item))
    combos.push([item], ...newCombos)
    return combos
  }, [])

getCombinations([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:

getCombinations(Array.from({ length: 19 })) // OK
getCombinations(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 combos.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 getCombinations = (items) =>
   items.reduce((combos, item) => {
-    const newCombos = combos.map((combo) => combo.concat(item))
-    combos.push([item], ...newCombos)

+    combos.forEach((combo) => combos.push(combo.concat(item)))
+    combos.push([item])

     return combos
   }, [])

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

It's slow

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

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

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

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

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

console.time()
getCombinations(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 getCombinations(items) is incidentally 2 ** items.length - 1:

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

(Math for calculating the total number of combinations.)

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

But input arrays that long would be impractical since getting all combinations would take way too long. Plus there would be quite many combinations: 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 combinations would take a very long time, so think:

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

Some pointers:

  • If you only need combinations that are e.g. 2 or 3 items long, there's no point in generating longer combinations.
  • If you are looking for a single combination 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 combinations that match a certain criterion, skip non-matching combinations early, i.e. don't store them in the accumulator array.