9

So I have a variable length array filled with variable length arrays. Something like this for example:

var arr2d = [
    ['red', 'blue'],
    ['cotton','polyester','silk'],
    ['large','medium','small']
]

I am trying to get all possible combinations of one from each array. so the answer should look something like this:

var answer = [
    ['red', 'cotton', 'large'],
    ['red', 'cotton', 'medium'],
    ['red', 'cotton', 'small'],
    ['red', 'polyester', 'large'],
    .
    .
    .
]

I've looked into the other answer on this topic but all of them are in java (I need javascript) and they were looking for all combinations and not limited to the combinations of length === arr2d.length. I've looked at this for almost 2 hours and still I cannot think of a way to do this recursively. It's one of those head explosion scenarios because both the arrays vary in length (I have an array of these 2d arrays that I must get the combinations for). In the example I've laid out there are only 18 possiblities, but in practice it could be thousands.

  • 1
    Possible duplicate of [Cartesian product of multiple arrays in JavaScript](https://stackoverflow.com/questions/12303989/cartesian-product-of-multiple-arrays-in-javascript) – Robby Cornelissen Nov 15 '18 at 04:16

2 Answers2

25

Another option when using recursive functions is to maintain your state in the arguments of the function. This can sometimes make the function easier to understand:

var arr2d = [['red', 'blue'],['cotton','polyester','silk'],['large','medium','small']]

function combos(list, n = 0, result = [], current = []){
    if (n === list.length) result.push(current)
    else list[n].forEach(item => combos(list, n+1, result, [...current, item]))
 
    return result
}

console.log(combos(arr2d))
Mark
  • 90,562
  • 7
  • 108
  • 148
5

Here's a recursive solution. The idea is to take the first array of elements, find the combinations recursively on the remaining array of elements, and then combine the results:

const arr2d = [
  ['red', 'blue'],
  ['cotton', 'polyester', 'silk'],
  ['large', 'medium', 'small']
];

function combinations(arr) {
  if (arr.length === 0) return [[]];
  let res = [], [first, ...rest] = arr;
  let remaining = combinations(rest);
  first.forEach(e => {
    remaining.forEach(smaller => {
      res.push([e].concat(smaller));
    });
  });
  return res;
}

console.log(combinations(arr2d));
slider
  • 12,810
  • 1
  • 26
  • 42
  • 1
    Fast and so short! Thank you so much! –  Nov 15 '18 at 03:21
  • I have just learned that this operation is called the cartesian product. –  Nov 15 '18 at 03:29
  • 1
    Mark Meyer gave us a 5 line solution. Just letting you know for your own personal use. –  Nov 15 '18 at 03:38
  • wait, if @CapitalJusticeWarrior says he needs all possibilities, then on top of the solutions you'll need to rorate the initial array to get all 54 possibilites. let result = []; for (let i=0; i – Sergey Pleshakov Nov 15 '18 at 03:45
  • and if index of all elems within array matter (for example [ 'medium', 'blue', 'large' ],[ 'large', 'medium', 'blue' ],[ 'blue', 'medium', 'large' ],), that's even more to consider – Sergey Pleshakov Nov 15 '18 at 03:50
  • @SergeyPleshakov We're not interested in *permutations* (where order would matter). So I believe the total final results here are `2 * 3 * 3 = 18`. – slider Nov 15 '18 at 03:53