Generation cartesian product objects from array values

Question

I'm building an array of objects out of the permutations of the entries in some arrays. My first stab at the code is below, it should help to illustrate what I'm trying to achieve:

permutationsArray = (array1, array2, array3) => {
  const arrayOfObjects = [];
    for (let i = 0; i < array1.length; i++) {
      for (let j = 0; j < array2.length; j++) {
        for (let k = 0; k < array3.length; k++) {
          arrayOfObjects.push({
            aConstant: 'some constant',
            key1: array1[i],
            key2: array2[j],
            key3: array3[k],
          });
        }
      }
    }
  return arrayOfObjects;
};

I'm really unhappy with having nested for loops to achieve this. Alternatives I have looked at are:

Use nested mapping and flatten the tree created
Attempt a recursive system similar to this solution here

I'm looking for input as to whether I'm going in the right direction with solving this. Ideally I want to get to the point where I can supply as many arrays as I wanted.

A big problem I'm seeing is how to name the keys with recursion.

This might help with key names: var obj = { aConstant: 'some constant'}; obj['key' + 1] = array1[i]; where 1 can be based on a counter — musefan
– musefan, Commented Oct 26, 2017 at 9:57
If you aways have three arrays, then nested loops is the best way. Otherwise look for a good JS implementation of Cartesian product — MBo
– MBo, Commented Oct 26, 2017 at 9:59
Possible duplicate of JavaScript - Generating combinations from n arrays with m elements — musefan
– musefan, Commented Oct 26, 2017 at 9:59
thanks for your input everyone, cartesian product was the subject I needed to start reading into more! — Nick Ramsbottom
– Nick Ramsbottom, Commented Oct 26, 2017 at 10:11
I don't know if it's optimal way but you can test it with sets of different array and calculate the time processed. — Mihai Alexandru-Ionut
– Mihai Alexandru-Ionut, Commented Oct 26, 2017 at 10:52

Mihai Alexandru-Ionut · Accepted Answer · 2017-10-26 16:35:08Z

3

First of all, that's not a problem with permutations, it's exactly Cartesian product.

In set theory (and, usually, in other parts of mathematics), a Cartesian product is a mathematical operation that returns a set from multiple sets.

You can achieve that using ES6 features like map and reduce methods.

function cartesianProduct(...arrays) {
  return [...arrays].reduce((a, b) =>
    a.map(x => b.map(y => x.concat(y)))
    .reduce((a, b) => a.concat(b), []), [[]]);
}
console.log(cartesianProduct([1, 2], [3, 4], [5, 6]));

edited Oct 26, 2017 at 16:35

answered Oct 26, 2017 at 10:06

Mihai Alexandru-Ionut

48.6k14 gold badges106 silver badges132 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

oravecz Over a year ago

Has anyone seen an implementation of n-fold cartesian product that is memory efficient? This implementation fails for my 6 input sets that result in 10MM combinations.

T.J. Crowder Over a year ago

@oravecz - It's all those concat calls, each of which creates a new array. Surely they can't be necessary...

Collectives™ on Stack Overflow

Generation cartesian product objects from array values

1 Answer 1

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Linked

Related