Finding All Combinations (Cartesian product) of JavaScript array values

Solution 1:

This is not permutations, see permutations definitions from Wikipedia.

But you can achieve this with recursion:

var allArrays = [
  ['a', 'b'],
  ['c'],
  ['d', 'e', 'f']
]

function allPossibleCases(arr) {
  if (arr.length == 1) {
    return arr[0];
  } else {
    var result = [];
    var allCasesOfRest = allPossibleCases(arr.slice(1)); // recur with the rest of array
    for (var i = 0; i < allCasesOfRest.length; i++) {
      for (var j = 0; j < arr[0].length; j++) {
        result.push(arr[0][j] + allCasesOfRest[i]);
      }
    }
    return result;
  }

}

console.log(allPossibleCases(allArrays))

You can also make it with loops, but it will be a bit tricky and will require implementing your own analogue of stack.

Solution 2:

I suggest a simple recursive generator function as follows:

// Generate cartesian product of given iterables:
function* cartesian(head, ...tail) {
  let remainder = tail.length ? cartesian(...tail) : [[]];
  for (let r of remainder) for (let h of head) yield [h, ...r];
}

// Example:
const first  = ['a', 'b', 'c', 'd'];
const second = ['e'];
const third  = ['f', 'g', 'h', 'i', 'j'];

console.log(...cartesian(first, second, third));

Solution 3:

You don't need recursion, or heavily nested loops, or even to generate/store the whole array of permutations in memory.

Since the number of permutations is the product of the lengths of each of the arrays (call this numPerms), you can create a function getPermutation(n) that returns a unique permutation between index 0 and numPerms - 1 by calculating the indices it needs to retrieve its characters from, based on n.

How is this done? If you think of creating permutations on arrays each containing: [0, 1, 2, ... 9] it's very simple... the 245th permutation (n=245) is "245", rather intuitively, or:

arrayHundreds[Math.floor(n / 100) % 10]
+ arrayTens[Math.floor(n / 10) % 10]
+ arrayOnes[Math.floor(n / 1) % 10]

The complication in your problem is that array sizes differ. We can work around this by replacing the n/100, n/10, etc... with other divisors. We can easily pre-calculate an array of divisors for this purpose. In the above example, the divisor of 100 was equal to arrayTens.length * arrayOnes.length. Therefore we can calculate the divisor for a given array to be the product of the lengths of the remaining arrays. The very last array always has a divisor of 1. Also, instead of modding by 10, we mod by the length of the current array.

Example code is below:

var allArrays = [first, second, third, ...];

// Pre-calculate divisors
var divisors = [];
for (var i = allArrays.length - 1; i >= 0; i--) {
   divisors[i] = divisors[i + 1] ? divisors[i + 1] * allArrays[i + 1].length : 1;
}

function getPermutation(n) {
   var result = "", curArray;

   for (var i = 0; i < allArrays.length; i++) {
      curArray = allArrays[i];
      result += curArray[Math.floor(n / divisors[i]) % curArray.length];
   }

   return result;
}

Solution 4:

Provided answers looks too difficult for me. So my solution is:

var allArrays = new Array(['a', 'b'], ['c', 'z'], ['d', 'e', 'f']);

function getPermutation(array, prefix) {
  prefix = prefix || '';
  if (!array.length) {
    return prefix;
  }

  var result = array[0].reduce(function(result, value) {
    return result.concat(getPermutation(array.slice(1), prefix + value));
  }, []);
  return result;
}

console.log(getPermutation(allArrays));

Solution 5:

You could take a single line approach by generating a cartesian product.

result = items.reduce(
    (a, b) => a.reduce(
        (r, v) => r.concat(b.map(w => [].concat(v, w))),
        []
    )
);

var items = [['a', 'b', 'c', 'd'], ['e'], ['f', 'g', 'h', 'i', 'j']],
    result = items.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []));
	
console.log(result.map(a => a.join(' ')));

.as-console-wrapper { max-height: 100% !important; top: 0; }