Home

How to do array combinations in Javascript

It’s somewhat frequent that we need to generate all combinations of exactly one item of two different JavaScript arrays. That’s most commonly accomplished with nested for loops:

function combineTwoArrays() {
  const combined = [];

  for (let item1 of array1) {
    for (let item2 of array2) {
      combined.push(item1 + item2);
    }
  }
  return combined;
}

// combineTwoArrays(['a','b'], ['c'])
// ['ac', 'bc']

Nice and easy, right?

But what happens when you want to combine three arrays?
What about four? Do you keep nesting for loops?
What if you have 30 arrays?
What if you don’t know how many arrays you will need to combine?

Bellow we have recursive and iterative solutions for generating combinations of one from each array, provided an arbitrary number of arrays.

Recursive solution

function combineRecursive(...arrays) {
  if (!arrays || arrays.length < 2) {
    throw new Error('Cannot combine less than 2 arrays.');
  }

  if (arrays.length > 2) {
    return combineRecursive(arrays[0], combineRecursive(...arrays.slice(1)));
  }

  // arrays.length is exactly 2
  const combinations = [];
  for (const word0 of arrays[0]) {
    for (const word1 of arrays[1]) {
      combinations.push(word0 + word1);
    }
  }
  return combinations;
}

// combineRecursive(["a"], ["b"], ["c", "d"])
// ['abc', 'abd'];

Iterative solution

function combineIterative(...arrays) {
  if (!arrays || arrays.length < 2) {
    throw new Error('Cannot combine less than 2 arrays.');
  }

  let allCombined = arrays[0];
  let tracker = 1; // tracks which array we are combining
  while (tracker < arrays.length) {
    const newCombined = [];
    for (const word0 of allCombined) {
      for (const word1 of arrays[tracker]) {
        newCombined.push(word0 + word1);
      }
    }
    tracker++;
    allCombined = newCombined;
  }

  return allCombined;
}

// combineIterative(["a"], ["b"], ["c", "d"])
// ['abc', 'abd'];

Performance

Both solutions offer similar performance and have the same algorithmic complexity:

> node ./benchmark/suite.js

combineRecursive 2 arrays of 10 items x 291,010 ops/sec ±0.41% (93 runs sampled)
combineIterative  2 arrays of 10 items x 282,999 ops/sec ±1.12% (88 runs sampled)
Fastest for 2x10 is combineRecursive 2 arrays of 10 items

combineRecursive 3 arrays of 10 items x 26,655 ops/sec ±0.57% (88 runs sampled)
combineIterative  3 arrays of 10 items x 25,847 ops/sec ±0.53% (93 runs sampled)
Fastest for 3x10 is combineRecursive 3 arrays of 10 items

combineRecursive 10 arrays of 3 items x 173 ops/sec ±1.35% (72 runs sampled)
combineIterative  10 arrays of 3 items x 179 ops/sec ±1.69% (79 runs sampled)
Fastest for 3x10 is combineIterative  10 arrays of 3 items

Full code, tests and benchmarks can be found here.