2

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.

Nick Ramsbottom
  • 583
  • 1
  • 6
  • 17
  • 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 Oct 26 '17 at 09: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 Oct 26 '17 at 09:59
  • 1
    Possible duplicate of [JavaScript - Generating combinations from n arrays with m elements](https://stackoverflow.com/questions/15298912/javascript-generating-combinations-from-n-arrays-with-m-elements) – musefan Oct 26 '17 at 09:59
  • thanks for your input everyone, `cartesian product` was the subject I needed to start reading into more! – Nick Ramsbottom Oct 26 '17 at 10:11
  • 1
    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 Oct 26 '17 at 10:52
  • I'll have a go at that! at the moment it's the only way I can think of doing it – Nick Ramsbottom Oct 26 '17 at 10:54

1 Answers1

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.

enter image description here

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]));
Mihai Alexandru-Ionut
  • 47,092
  • 13
  • 101
  • 128
  • 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. – oravecz Apr 08 '18 at 19:01
  • 1
    @oravecz - It's all those `concat` calls, each of which creates a new array. Surely they can't be necessary... – T.J. Crowder Aug 25 '18 at 16:09