Finding All Combinations (Cartesian product) of JavaScript array values

Question

How can I produce all of the combinations of the values in N number of JavaScript arrays of variable lengths?

Let's say I have N number of JavaScript arrays, e.g.

var first = ['a', 'b', 'c', 'd'];
var second = ['e'];
var third = ['f', 'g', 'h', 'i', 'j'];

(Three arrays in this example, but its N number of arrays for the problem.)

And I want to output all the combinations of their values, to produce

aef
aeg
aeh
aei
aej
bef
beg
....
dej

---

EDIT: Here's the version I got working, using ffriend's accepted answer as the basis.

var allArrays = [['a', 'b'], ['c', 'z'], ['d', 'e', 'f']];
 function allPossibleCases(arr) {
 if (arr.length === 0) {
 return [];
 } 
 else if (arr.length ===1){
 return arr[0];
 }
 else {
 var result = [];
 var allCasesOfRest = allPossibleCases(arr.slice(1)); // recur with the rest of array
 for (var c in allCasesOfRest) {
 for (var i = 0; i < arr[0].length; i++) {
 result.push(arr[0][i] + allCasesOfRest[c]);
 }
 }
 return result;
 }
}
var results = allPossibleCases(allArrays);
 //outputs ["acd", "bcd", "azd", "bzd", "ace", "bce", "aze", "bze", "acf", "bcf", "azf", "bzf"]

Answer 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.

Answer 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));

• Andrew: This is indeed beautiful. For those of you who want to use an unknown number of inputs and store the result in an array, you can do: const product = [...cartesian.apply(this, [first, second, third, fourth, etc])]
• Sukima: @Andrew why .apply and not splat the arguments to cartesian? const product = [...cartesian(...unknownNumberOfInputs)];
• mplungjan: Beautiful. How to modify to satisfy this version where the permutations of single, double etc strings are required

Answer 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;
}

• Gary Green: Very nice. There is a typo here though, results should show result -- I notice you loop backwards for calculating the divisors, I assume the position of the divisor in the array is important?
• David Tang: @Gary, thanks for picking that up. The order of the divisors matters because the first one depends on the second, the second depends on the third, etc... So by looping backwards I can build this up more easily.
• Cybercartel: @Box9: Does this function works with 1 array? Isn't it (n*n) - (n-1)?
• David Tang: @epitaph, it should still work with 1 array. divisors will only have one element: [1], and so it will always divide by 1, and mod by the array length - in effect, doing nothing.
• Cybercartel: If it works on 1 array and the result (n*n)-(n-1) can I use it to make a cost matrix? For example for the travelsalesman problem?

Answer 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));

• Thomas: Hi. How can this be modified to return an array of arrays instead of array of strings? So instead of ["acd","ace","acf" ...] to return [["a","c",d"], ["a","c","e"] ....]

Answer 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; }

Answer 6

Copy of le_m's Answer to take Array of Arrays directly:

function *combinations(arrOfArr) {
 let [head, ...tail] = arrOfArr
 let remainder = tail.length ? combinations(tail) : [[]];
 for (let r of remainder) for (let h of head) yield [h, ...r];
}

Hope it saves someone's time.

• DarkNeuron: You could have used le_m's as such: cartesian(...arrOfArr)

Answer 7

You can use a typical backtracking:

function cartesianProductConcatenate(arr) {
 var data = new Array(arr.length);
 return (function* recursive(pos) {
 if(pos === arr.length) yield data.join('');
 else for(var i=0; i<arr[pos].length; ++i) {
 data[pos] = arr[pos][i];
 yield* recursive(pos+1);
 }
 })(0);
}

I used generator functions to avoid allocating all the results simultaneously, but if you want you can

[...cartesianProductConcatenate([['a', 'b'], ['c', 'z'], ['d', 'e', 'f']])];
// ["acd","ace","acf","azd","aze","azf","bcd","bce","bcf","bzd","bze","bzf"]

Answer 8

Easiest way to find the Combinations

const arr1= [ 'a', 'b', 'c', 'd' ];
const arr2= [ '1', '2', '3' ];
const arr3= [ 'x', 'y', ];
const all = [arr1, arr2, arr3];
const output = all.reduce((acc, cu) => { 
 let ret = [];
 acc.map(obj => {
 cu.map(obj_1 => {
 ret.push(obj + '-' + obj_1) 
 });
 });
 return ret;
 })
console.log(output);

• Bergi: This fails on an empty array.

Answer 9

If you're looking for a flow-compatible function that can handle two dimensional arrays with any item type, you can use the function below.

const getUniqueCombinations = <T>(items : Array<Array<T>>, prepend : Array<T> = []) : Array<Array<T>> => {
 if(!items || items.length === 0) return [prepend];
 let out = [];
 for(let i = 0; i < items[0].length; i++){
 out = [...out, ...getUniqueCombinations(items.slice(1), [...prepend, items[0][i]])];
 }
 return out;
}

A visualisation of the operation:

in:

[
 [Obj1, Obj2, Obj3],
 [Obj4, Obj5],
 [Obj6, Obj7]
]

out:

[
 [Obj1, Obj4, Obj6 ],
 [Obj1, Obj4, Obj7 ],
 [Obj1, Obj5, Obj6 ],
 [Obj1, Obj5, Obj7 ],
 [Obj2, Obj4, Obj6 ],
 [Obj2, Obj4, Obj7 ],
 [Obj2, Obj5, Obj6 ],
 [Obj2, Obj5, Obj7 ],
 [Obj3, Obj4, Obj6 ],
 [Obj3, Obj4, Obj7 ],
 [Obj3, Obj5, Obj6 ],
 [Obj3, Obj5, Obj7 ]
]

Answer 10

You could create a 2D array and reduce it. Then use flatMap to create combinations of strings in the accumulator array and the current array being iterated and concatenate them.

const data = [ ['a', 'b', 'c', 'd'], ['e'], ['f', 'g', 'h', 'i', 'j'] ]
const output = data.reduce((acc, cur) => acc.flatMap(c => cur.map(n => c + n)) )
console.log(output)

• BlasterGod: How can you obtain the list in ARRAY format and not strings? So instead of "abc" to have it return as array ["a","b","c"]
• adiga: @BlasterGod that's a Cartesian product. I have answered that with a similar approach here: stackoverflow.com/a/57597533/3082296

Answer 11

2021 version of David Tang's great answer
Also inspired with Neil Mountford's answer

• fast (x2+ faster than most answers)
• works with any data types

const getAllCombinations = (arraysToCombine) => {
 const divisors = [];
 let permsCount = 1;
 for (let i = arraysToCombine.length - 1; i >= 0; i--) {
 divisors[i] = divisors[i + 1] ? divisors[i + 1] * arraysToCombine[i + 1].length : 1;
 permsCount *= (arraysToCombine[i].length || 1);
 }
 const getCombination = (n, arrays, divisors) => arrays.reduce((acc, arr, i) => {
 acc.push(arr[Math.floor(n / divisors[i]) % arr.length]);
 return acc;
 }, []);
 const combinations = [];
 for (let i = 0; i < permsCount; i++) {
 combinations.push(getCombination(i, arraysToCombine, divisors));
 }
 return combinations;
};
console.log(getAllCombinations([['a', 'b'], ['c', 'z'], ['d', 'e', 'f']]));

Benchmarks: https://jsbench.me/gdkmxhm36d/1

Answer 12

Here's a version adapted from the above couple of answers, that produces the results in the order specified in the OP, and returns strings instead of arrays:

function *cartesianProduct(...arrays) {
 if (!arrays.length) yield [];
 else {
 const [tail, ...head] = arrays.reverse();
 const beginning = cartesianProduct(...head.reverse());
 for (let b of beginning) for (let t of tail) yield b + t;
 }
}
const first = ['a', 'b', 'c', 'd'];
const second = ['e'];
const third = ['f', 'g', 'h', 'i', 'j'];
console.log([...cartesianProduct(first, second, third)])

Answer 13

You could use this function too:

const result = (arrayOfArrays) => arrayOfArrays.reduce((t, i) => { let ac = []; for (const ti of t) { for (const ii of i) { ac.push(ti + '/' + ii) } } return ac })
result([['a', 'b', 'c', 'd'], ['e'], ['f', 'g', 'h', 'i', 'j']])
// which will output [ 'a/e/f', 'a/e/g', 'a/e/h','a/e/i','a/e/j','b/e/f','b/e/g','b/e/h','b/e/i','b/e/j','c/e/f','c/e/g','c/e/h','c/e/i','c/e/j','d/e/f','d/e/g','d/e/h','d/e/i','d/e/j']

Of course you can remove the + '/' in ac.push(ti + '/' + ii) to eliminate the slash from the final result. And you can replace those for (... of ...) with forEach functions (plus respective semicolon before return ac), whatever of those you are more comfortable with.

• DarkNeuron: You could also minify one of the other answers :) The goal is not to have it on one line. Readable code is a goal in itself.

Answer 14

An array approach without recursion:

const combinations = [['1', '2', '3'], ['4', '5', '6'], ['7', '8']];
let outputCombinations = combinations[0]
combinations.slice(1).forEach(row => {
 outputCombinations = outputCombinations.reduce((acc, existing) =>
 acc.concat(row.map(item => existing + item))
 , []);
});
console.log(outputCombinations);

Answer 15

let arr1 = [`a`, `b`, `c`];
let arr2 = [`p`, `q`, `r`];
let arr3 = [`x`, `y`, `z`];
let result = [];
arr1.forEach(e1 => {
 arr2.forEach(e2 => {
 arr3.forEach(e3 => {
 result[result.length] = e1 + e2 + e3;
 });
 });
});
console.log(result);
/*
output:
[
 'apx', 'apy', 'apz', 'aqx',
 'aqy', 'aqz', 'arx', 'ary',
 'arz', 'bpx', 'bpy', 'bpz',
 'bqx', 'bqy', 'bqz', 'brx',
 'bry', 'brz', 'cpx', 'cpy',
 'cpz', 'cqx', 'cqy', 'cqz',
 'crx', 'cry', 'crz'
]
*/

• jasie: Thank you for this code snippet, which might provide some limited, immediate help. A proper explanation would greatly improve its long-term value by showing why this is a good solution to the problem and would make it more useful to future readers with other, similar questions. Please edit your answer to add some explanation, including the assumptions you’ve made.

Answer 16

A solution without recursion, which also includes a function to retrieve a single combination by its id:

function getCombination(data, i) {
 return data.map(group => {
 let choice = group[i % group.length]
 i = (i / group.length) | 0;
 return choice;
 });
}
function* combinations(data) {
 let count = data.reduce((sum, {length}) => sum * length, 1);
 for (let i = 0; i < count; i++) {
 yield getCombination(data, i);
 }
}
let data = [['a', 'b', 'c', 'd'], ['e'], ['f', 'g', 'h', 'i', 'j']];
for (let combination of combinations(data)) {
 console.log(...combination);
}