Menu
Original 2017 Answer: 2-line answer with vanilla JS: (see updates below)
All of the answers here are overly complicated, most of them take 20 lines of code or even more.
This example uses just two lines of vanilla JavaScript, no lodash, underscore or other libraries:
let f = (a, b) => [].concat(...a.map(a => b.map(b => [].concat(a, b))));
let cartesian = (a, b, ...c) => b ? cartesian(f(a, b), ...c) : a;
This is the same as above but improved to strictly follow the Airbnb JavaScript Style Guide - validated using ESLint with eslint-config-airbnb-base:
const f = (a, b) => [].concat(...a.map(d => b.map(e => [].concat(d, e))));
const cartesian = (a, b, ...c) => (b ? cartesian(f(a, b), ...c) : a);
Special thanks to ZuBB for letting me know about linter problems with the original code.
Since I wrote this answer we got even better builtins, that can finally let us reduce (no pun intended) the code to just 1 line!
const cartesian =
(...a) => a.reduce((a, b) => a.flatMap(d => b.map(e => [d, e].flat())));
Special thanks to inker for suggesting the use of reduce.
Special thanks to Bergi for suggesting the use of the newly added flatMap.
Special thanks to ECMAScript 2019 for adding flat and flatMap to the language!
This is the exact example from your question:
let output = cartesian([1,2],[10,20],[100,200,300]);
This is the output of that command:
[ [ 1, 10, 100 ],
[ 1, 10, 200 ],
[ 1, 10, 300 ],
[ 1, 20, 100 ],
[ 1, 20, 200 ],
[ 1, 20, 300 ],
[ 2, 10, 100 ],
[ 2, 10, 200 ],
[ 2, 10, 300 ],
[ 2, 20, 100 ],
[ 2, 20, 200 ],
[ 2, 20, 300 ] ]
See demos on:
The syntax that I used here is nothing new. My example uses the spread operator and the rest parameters - features of JavaScript defined in the 6th edition of the ECMA-262 standard published on June 2015 and developed much earlier, better known as ES6 or ES2015. See:
The new methods from the Update 2020 example was added in ES2019:
It makes code like this so simple that it's a sin not to use it. For old platforms that don't support it natively you can always use Babel or other tools to transpile it to older syntax - and in fact my example transpiled by Babel is still shorter and simpler than most of the examples here, but it doesn't really matter because the output of transpilation is not something that you need to understand or maintain, it's just a fact that I found interesting.
There's no need to write hundred of lines of code that is hard to maintain and there is no need to use entire libraries for such a simple thing, when two lines of vanilla JavaScript can easily get the job done. As you can see it really pays off to use modern features of the language and in cases where you need to support archaic platforms with no native support of the modern features you can always use Babel, TypeScript or other tools to transpile the new syntax to the old one.
JavaScript evolves and it does so for a reason. TC39 does an amazing job of the language design with adding new features and the browser vendors do an amazing job of implementing those features.
To see the current state of native support of any given feature in the browsers, see:
To see the support in Node versions, see:
To use modern syntax on platforms that don't support it natively, use Babel or TypeScript:
Here is a functional solution to the problem (without any mutable variable!) using reduce and flatten, provided by underscore.js:
function cartesianProductOf() {
return _.reduce(arguments, function(a, b) {
return _.flatten(_.map(a, function(x) {
return _.map(b, function(y) {
return x.concat([y]);
});
}), true);
}, [ [] ]);
}
// [[1,3,"a"],[1,3,"b"],[1,4,"a"],[1,4,"b"],[2,3,"a"],[2,3,"b"],[2,4,"a"],[2,4,"b"]]
console.log(cartesianProductOf([1, 2], [3, 4], ['a'])); <script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.9.1/underscore.js"></script>Remark: This solution was inspired by http://cwestblog.com/2011/05/02/cartesian-product-of-multiple-arrays/
Here's a modified version of @viebel's code in plain Javascript, without using any library:
function cartesianProduct(arr) {
return arr.reduce(function(a,b){
return a.map(function(x){
return b.map(function(y){
return x.concat([y]);
})
}).reduce(function(a,b){ return a.concat(b) },[])
}, [[]])
}
var a = cartesianProduct([[1, 2,3], [4, 5,6], [7, 8], [9,10]]);
console.log(JSON.stringify(a));The following efficient generator function returns the cartesian product of all given iterables:
// Generate cartesian product of given iterables:
function* cartesian(head, ...tail) {
const remainder = tail.length > 0 ? cartesian(...tail) : [[]];
for (let r of remainder) for (let h of head) yield [h, ...r];
}
// Example:
console.log(...cartesian([1, 2], [10, 20], [100, 200, 300]));It accepts arrays, strings, sets and all other objects implementing the iterable protocol.
Following the specification of the n-ary cartesian product it yields
[] if one or more given iterables are empty, e.g. [] or ''
[[a]] if a single iterable containing a single value a is given.All other cases are handled as expected as demonstrated by the following test cases:
// Generate cartesian product of given iterables:
function* cartesian(head, ...tail) {
const remainder = tail.length > 0 ? cartesian(...tail) : [[]];
for (let r of remainder) for (let h of head) yield [h, ...r];
}
// Test cases:
console.log([...cartesian([])]); // []
console.log([...cartesian([1])]); // [[1]]
console.log([...cartesian([1, 2])]); // [[1], [2]]
console.log([...cartesian([1], [])]); // []
console.log([...cartesian([1, 2], [])]); // []
console.log([...cartesian([1], [2])]); // [[1, 2]]
console.log([...cartesian([1], [2], [3])]); // [[1, 2, 3]]
console.log([...cartesian([1, 2], [3, 4])]); // [[1, 3], [2, 3], [1, 4], [2, 4]]
console.log([...cartesian('')]); // []
console.log([...cartesian('ab', 'c')]); // [['a','c'], ['b', 'c']]
console.log([...cartesian([1, 2], 'ab')]); // [[1, 'a'], [2, 'a'], [1, 'b'], [2, 'b']]
console.log([...cartesian(new Set())]); // []
console.log([...cartesian(new Set([1]))]); // [[1]]
console.log([...cartesian(new Set([1, 1]))]); // [[1]]It seems the community thinks this to be trivial and/or easy to find a reference implementation. However, upon brief inspection I couldn't find one, … either that or maybe it's just that I like re-inventing the wheel or solving classroom-like programming problems. Either way its your lucky day:
function cartProd(paramArray) {
function addTo(curr, args) {
var i, copy,
rest = args.slice(1),
last = !rest.length,
result = [];
for (i = 0; i < args[0].length; i++) {
copy = curr.slice();
copy.push(args[0][i]);
if (last) {
result.push(copy);
} else {
result = result.concat(addTo(copy, rest));
}
}
return result;
}
return addTo([], Array.prototype.slice.call(arguments));
}
>> console.log(cartProd([1,2], [10,20], [100,200,300]));
>> [
[1, 10, 100], [1, 10, 200], [1, 10, 300], [1, 20, 100],
[1, 20, 200], [1, 20, 300], [2, 10, 100], [2, 10, 200],
[2, 10, 300], [2, 20, 100], [2, 20, 200], [2, 20, 300]
]
Full reference implementation that's relatively efficient… 😁
On efficiency: You could gain some by taking the if out of the loop and having 2 separate loops since it is technically constant and you'd be helping with branch prediction and all that mess, but that point is kind of moot in JavaScript.
Here's a non-fancy, straightforward recursive solution:
function cartesianProduct(a) { // a = array of array
var i, j, l, m, a1, o = [];
if (!a || a.length == 0) return a;
a1 = a.splice(0, 1)[0]; // the first array of a
a = cartesianProduct(a);
for (i = 0, l = a1.length; i < l; i++) {
if (a && a.length)
for (j = 0, m = a.length; j < m; j++)
o.push([a1[i]].concat(a[j]));
else
o.push([a1[i]]);
}
return o;
}
console.log(cartesianProduct([[1, 2], [10, 20], [100, 200, 300]]));
// [
// [1,10,100],[1,10,200],[1,10,300],
// [1,20,100],[1,20,200],[1,20,300],
// [2,10,100],[2,10,200],[2,10,300],
// [2,20,100],[2,20,200],[2,20,300]
// ]If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With