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
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 thebreak
statement instead.
- Not possible if using an array reducer;
use
- 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.