178

How would you implement the Cartesian product of multiple arrays in JavaScript?

As an example,

cartesian([1, 2], [10, 20], [100, 200, 300]) 

should return

[
  [1, 10, 100],
  [1, 10, 200],
  [1, 10, 300],
  [2, 10, 100],
  [2, 10, 200]
  ...
]
7

36 Answers 36

228

2020 Update: 1-line (!) answer with vanilla JS

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;

Update:

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.

Update 2020:

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!

Example

This is the exact example from your question:

let output = cartesian([1,2],[10,20],[100,200,300]);

Output

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 ] ]

Demo

See demos on:

Syntax

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.

Conclusion

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.

Don't code like it's 1995

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:

26
  • 22
    "Don't code like it's 1995" - no need to be unpleasant, not everyone has caught up yet.
    – Godwhacker
    Aug 1, 2017 at 14:54
  • 13
    This is fine however fails when fed with ['a', 'b'], [1,2], [[9], [10]] which will yield [ [ 'a', 1, 9 ], [ 'a', 1, 10 ], [ 'a', 2, 9 ], [ 'a', 2, 10 ], [ 'b', 1, 9 ], [ 'b', 1, 10 ], [ 'b', 2, 9 ], [ 'b', 2, 10 ] ] as a result. I mean won't keep the type of items of [[9], [10]].
    – Redu
    Aug 27, 2017 at 15:29
  • 8
    Don't code like it's 2017. Use .flatMap instead of concat+map :-)
    – Bergi
    Sep 3, 2020 at 21:07
  • 4
    a, b, d, e, leave those names to your favourite JS mangler, meaningful ones could help to understand the logic here :) Plus, where has c gone? Nice one though, impressive solution!
    – sp00m
    Oct 15, 2020 at 17:15
  • 4
    I note your latest (...a) => a.reduce((a, b) => a.flatMap(d => b.map(e => [d, e].flat()))); does not work in the degenerate case of one argument -- rather than return a list of lists, it just returns the original input list. Feb 14, 2021 at 20:29
93

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/

8
  • There is a typo in this answer, there shouldn't be a ", true" (maybe lodash has changed since you made this post?) May 29, 2015 at 14:36
  • @ChrisJefferson the second param to flatten is to make the flattening shallow. It is mandatory here!
    – viebel
    May 31, 2015 at 7:39
  • 4
    Sorry, this is a lodash / underscore incompatibility, they swapped around the flag. May 31, 2015 at 14:17
  • 1
    So when flattening, use true with underscore and use false with lodash to ensure shallow flattening. Aug 16, 2015 at 12:58
  • How do modify this function so it would accept array of arrays?
    – user4338202
    Oct 21, 2015 at 20:41
60

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

3
  • 2
    Fails for cartesianProduct([[[1],[2],[3]], ['a', 'b'], [['gamma'], [['alpha']]], ['zii', 'faa']]) as it flattens ['gamma'] to 'gamma' and [['alpha']] to ['alpha']
    – Lzh
    Nov 15, 2017 at 19:14
  • because .concat(y) instead of .concat([ y ])
    – Mulan
    Nov 4, 2018 at 13:11
  • @Thankyou you can edit the answer directly instead of commenting, just did it so no need now :P Jan 30, 2020 at 2:41
41

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]]

6
  • Do you mind to explain what's happening on this one? Thanks a lot!
    – LeandroP
    Feb 22, 2019 at 19:45
  • 1
    Thanks for teaching us a pretty wonderful example of using generator function + tail recursion + double-layer loops! But the position of the first for-loop in the code needs to be changed to make the order of the output sub-arrays correct. Fixed code: function* cartesian(head, ...tail) { for (let h of head) { const remainder = tail.length > 0 ? cartesian(...tail) : [[]]; for (let r of remainder) yield [h, ...r] } }
    – ooo
    Mar 17, 2019 at 14:00
  • 1
    @ooo If you want to reproduce the order of the cartesian product tuples given by OP's comment, then your modification is correct. However, the order of the tuples within the product is usually not relevant, e.g. mathematically the result is an unordered set. I chose this order because it requires much less recursive calls and is therefore a bit more performant - I didn't run a benchmark though.
    – le_m
    Mar 21, 2019 at 17:16
  • Erratum: In my comment above, "tail recursion" should be "recursion" (not a tail call in this case).
    – ooo
    Apr 1, 2019 at 4:31
  • 2
    I like this version the most, by all means. It uses a generator, it's just as compact as the most popular answer (and more compact than the accepted one) all while using readable variable names, and as the only answer I've tried so far it doesn't flatten nested arrays, which is an undesired side effect of the other answers! Only "drawback" is the different order, which to me really isn't.
    – panda-byte
    Sep 7, 2022 at 12:54
31

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.

6
  • 1
    Thanks @ckoz for your detailed answer. Why wouldn't you use the reduce function of array?
    – viebel
    Sep 6, 2012 at 20:56
  • 2
    @viebel why do you want to use reduce? for one, reduce has very poor support for older browsers (see: developer.mozilla.org/en-US/docs/JavaScript/Reference/…), and in any case does that crazy code from that other answer actually look readable to you? it doesn't to me. sure it's shorter, but once minified this code would be around the same length, easier to debug/optimize, secondly all those "reduce" solutions break down to the same thing, except they have a closure lookup (theoretically slower), it's also harder to design so it handles infinite sets...
    – ckozl
    Sep 6, 2012 at 21:32
  • 7
    I created a 2+ times faster and (imo) cleaner version: pastebin.com/YbhqZuf7 It achieves the speed boost by not using result = result.concat(...) and by not using args.slice(1). Unfortunately, I wasn't able to find a way to get rid of curr.slice() and the recursion.
    – Pauan
    Jan 1, 2014 at 7:30
  • 2
    @Pauan nice job, nice reduction of hot-spots on the whole for in the league of a 10%-50% performance boost based on what I'm seeing. I can't speak as to the "cleanliness" though, I feel your version is actually more difficult to follow due to use of closure scope variables. But generally speaking, more performant code is harder to follow. I wrote the original version for readability, I wish I had more time so that I could engage you in a performance throw down ;) maybe later...
    – ckozl
    Jan 4, 2014 at 11:39
  • this really is one of those problems Jul 24, 2015 at 23:51
25

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]
// ]

2
  • 2
    This one turns out to be the most efficient pure JS code under this topic. It takes like ~600msecs to finish on 3 x 100 item arrays to produce an array of length 1M.
    – Redu
    Oct 2, 2016 at 23:50
  • 2
    Works for cartesianProduct([[[1],[2],[3]], ['a', 'b'], [['gamma'], [['alpha']]], ['zii', 'faa']]); without flattening original values
    – Lzh
    Nov 15, 2017 at 19:18
21

Here is a one-liner using the native ES2019 flatMap. No libraries needed, just a modern browser (or transpiler):

data.reduce((a, b) => a.flatMap(x => b.map(y => [...x, y])), [[]]);

It's essentially a modern version of viebel's answer, without lodash.

4
  • Sure no library was needed. But it's also, not the most readable code ever. It's a trade-off. Aug 18, 2020 at 17:28
  • Readability has more to do in this case with my choice of using the spread operator I think, and not so much with the choice of not using a library. I don't think lodash leads to more readable code at all. Aug 19, 2020 at 13:50
  • I prefer this answer over the 2020 version in rsp's top-voted answer, since this also works correctly when only one array is given, like data = [["hello"]];
    – trincot
    Oct 6, 2022 at 9:02
  • 2
    Readability has also to do with the variable names. a, b, x and y are all generic non-descriptive names. If actual descriptive names where used readability would improve. arrays.reduce((product, array) => product.flatMap(combination => array.map(item => [...combination, item])), [[]]) Though like you can see it does become a bit longer.
    – 3limin4t0r
    Oct 27, 2022 at 10:57
14

functional programming

This question is tagged functional-programming so let's take a look at the List monad:

One application for this monadic list is representing nondeterministic computation. List can hold results for all execution paths in an algorithm...

Well that sounds like a perfect fit for cartesian. JavaScript gives us Array and the monadic binding function is Array.prototype.flatMap, so let's put them to use -

const cartesian = (...all) => {
  const loop = (t, a, ...more) =>
    a === undefined
      ? [ t ]
      : a.flatMap(x => loop([ ...t, x ], ...more))
  return loop([], ...all)
}

console.log(cartesian([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]

more recursion

Other recursive implementations include -

const cartesian = (a, ...more) =>
  a == null
    ? [[]]
    : cartesian(...more).flatMap(c => a.map(v => [v,...c]))

for (const p of cartesian([1,2], [10,20], [100,200,300]))
  console.log(JSON.stringify(p))
.as-console-wrapper { min-height: 100%; top: 0; }

[1,10,100]
[2,10,100]
[1,20,100]
[2,20,100]
[1,10,200]
[2,10,200]
[1,20,200]
[2,20,200]
[1,10,300]
[2,10,300]
[1,20,300]
[2,20,300]

Note the different order above. You can get lexicographic order by inverting the two loops. Be careful not avoid duplicating work by calling cartesian inside the loop like Nick's answer -

const bind = (x, f) => f(x)

const cartesian = (a, ...more) =>
  a == null
    ? [[]]
    : bind(cartesian(...more), r => a.flatMap(v => r.map(c => [v,...c])))

for (const p of cartesian([1,2], [10,20], [100,200,300]))
  console.log(JSON.stringify(p))
.as-console-wrapper { min-height: 100%; top: 0; }

[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]

generators

Another option is to use generators. A generator is a good fit for combinatorics because the solution space can become very large. Generators offer lazy evaluation so they can be paused/resumed/canceled at any time -

function* cartesian(a, ...more) {
  if (a == null) return yield []
  for (const v of a)
    for (const c of cartesian(...more)) // ⚠️
      yield [v, ...c]
}
  
for (const p of cartesian([1,2], [10,20], [100,200,300]))
  console.log(JSON.stringify(p))
.as-console-wrapper { min-height: 100%; top: 0; }

[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]

Maybe you saw that we called cartesian in a loop in the generator. If you suspect that can be optimized, it can! Here we use a generic tee function that forks any iterator n times -

function* cartesian(a, ...more) {
  if (a == null) return yield []
  for (const t of tee(cartesian(...more), a.length)) // ✅
    for (const v of a)
      for (const c of t) // ✅
        yield [v, ...c]
}

Where tee is implemented as -

function tee(g, n = 2) {
  const memo = []
  function* iter(i) {
    while (true) {
      if (i >= memo.length) {
        const w = g.next()
        if (w.done) return
        memo.push(w.value)
      }
      else yield memo[i++]
    }
  }
  return Array.from(Array(n), _ => iter(0))
}

Even in small tests cartesian generator implemented with tee performs twice as fast.

13

Here is a recursive way that uses an ECMAScript 2015 generator function so you don't have to create all of the tuples at once:

function* cartesian() {
    let arrays = arguments;
    function* doCartesian(i, prod) {
        if (i == arrays.length) {
            yield prod;
        } else {
            for (let j = 0; j < arrays[i].length; j++) {
                yield* doCartesian(i + 1, prod.concat([arrays[i][j]]));
            }
        }
    }
    yield* doCartesian(0, []);
}

console.log(JSON.stringify(Array.from(cartesian([1,2],[10,20],[100,200,300]))));
console.log(JSON.stringify(Array.from(cartesian([[1],[2]],[10,20],[100,200,300]))));

3
  • This won't work when one of the arrays have array items such as cartesian([[1],[2]],[10,20],[100,200,300])
    – Redu
    Oct 2, 2016 at 16:19
  • @Redu Answer has been updated to support array arguments.
    – heenenee
    Oct 2, 2016 at 19:09
  • Yes .concat() built in spread operator sometimes might become deceitful.
    – Redu
    Oct 2, 2016 at 19:40
12

This is a pure ES6 solution using arrow functions

function cartesianProduct(arr) {
  return arr.reduce((a, b) =>
    a.map(x => b.map(y => x.concat(y)))
    .reduce((a, b) => a.concat(b), []), [[]]);
}

var arr = [[1, 2], [10, 20], [100, 200, 300]];
console.log(JSON.stringify(cartesianProduct(arr)));

9

Using a typical backtracking with ES6 generators,

function cartesianProduct(...arrays) {
  let current = new Array(arrays.length);
  return (function* backtracking(index) {
    if(index == arrays.length) yield current.slice();
    else for(let num of arrays[index]) {
      current[index] = num;
      yield* backtracking(index+1);
    }
  })(0);
}
for (let item of cartesianProduct([1,2],[10,20],[100,200,300])) {
  console.log('[' + item.join(', ') + ']');
}
div.as-console-wrapper { max-height: 100%; }

Below there is a similar version compatible with older browsers.

function cartesianProduct(arrays) {
  var result = [],
      current = new Array(arrays.length);
  (function backtracking(index) {
    if(index == arrays.length) return result.push(current.slice());
    for(var i=0; i<arrays[index].length; ++i) {
      current[index] = arrays[index][i];
      backtracking(index+1);
    }
  })(0);
  return result;
}
cartesianProduct([[1,2],[10,20],[100,200,300]]).forEach(function(item) {
  console.log('[' + item.join(', ') + ']');
});
div.as-console-wrapper { max-height: 100%; }

8

A coffeescript version with lodash:

_ = require("lodash")
cartesianProduct = ->
    return _.reduceRight(arguments, (a,b) ->
        _.flatten(_.map(a,(x) -> _.map b, (y) -> x.concat(y)), true)
    , [ [] ])
8

A single line approach, for better reading with indentations.

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

It takes a single array with arrays of wanted cartesian items.

var data = [[1, 2], [10, 20], [100, 200, 300]],
    result = data.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; }

1
  • 1
    I had to add a guard statement to correctly handle the case where the array has a single element: if (arr.length === 1) return arr[0].map(el => [el]); Aug 31, 2018 at 13:22
4

In my particular setting, the "old-fashioned" approach seemed to be more efficient than the methods based on more modern features. Below is the code (including a small comparison with other solutions posted in this thread by @rsp and @sebnukem) should it prove useful to someone else as well.

The idea is following. Let's say we are constructing the outer product of N arrays, a_1,...,a_N each of which has m_i components. The outer product of these arrays has M=m_1*m_2*...*m_N elements and we can identify each of them with a N-dimensional vector the components of which are positive integers and i-th component is strictly bounded from above by m_i. For example, the vector (0, 0, ..., 0) would correspond to the particular combination within which one takes the first element from each array, while (m_1-1, m_2-1, ..., m_N-1) is identified with the combination where one takes the last element from each array. Thus in order to construct all M combinations, the function below consecutively constructs all such vectors and for each of them identifies the corresponding combination of the elements of the input arrays.

function cartesianProduct(){
    const N = arguments.length;

    var arr_lengths = Array(N);
    var digits = Array(N);
    var num_tot = 1;
    for(var i = 0; i < N; ++i){
        const len = arguments[i].length;
        if(!len){
            num_tot = 0;
            break;
        }
        digits[i] = 0;
        num_tot *= (arr_lengths[i] = len);
    }

    var ret = Array(num_tot);
    for(var num = 0; num < num_tot; ++num){

        var item = Array(N);
        for(var j = 0; j < N; ++j){ item[j] = arguments[j][digits[j]]; }
        ret[num] = item;

        for(var idx = 0; idx < N; ++idx){
            if(digits[idx] == arr_lengths[idx]-1){
                digits[idx] = 0;
            }else{
                digits[idx] += 1;
                break;
            }
        }
    }
    return ret;
}
//------------------------------------------------------------------------------
let _f = (a, b) => [].concat(...a.map(a => b.map(b => [].concat(a, b))));
let cartesianProduct_rsp = (a, b, ...c) => b ? cartesianProduct_rsp(_f(a, b), ...c) : a;
//------------------------------------------------------------------------------
function cartesianProduct_sebnukem(a) {
    var i, j, l, m, a1, o = [];
    if (!a || a.length == 0) return a;

    a1 = a.splice(0, 1)[0];
    a = cartesianProduct_sebnukem(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;
}
//------------------------------------------------------------------------------
const L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
const args = [L, L, L, L, L, L];

let fns = {
    'cartesianProduct': function(args){ return cartesianProduct(...args); },
    'cartesianProduct_rsp': function(args){ return cartesianProduct_rsp(...args); },
    'cartesianProduct_sebnukem': function(args){ return cartesianProduct_sebnukem(args); }
};

Object.keys(fns).forEach(fname => {
    console.time(fname);
    const ret = fns[fname](args);
    console.timeEnd(fname);
});

with node v6.12.2, I get following timings:

cartesianProduct: 427.378ms
cartesianProduct_rsp: 1710.829ms
cartesianProduct_sebnukem: 593.351ms
1
  • good stuff, sometimes a cartesian products may involve a HUGE input/output and most recursion based method would fail. Even some method that put a crazy large object (>4GB) in the memory would also fail too if not using generators. This ordinary method is the way to go.
    – Valen
    Jul 22, 2022 at 15:18
4

For those who needs TypeScript (reimplemented @Danny's answer)

/**
 * Calculates "Cartesian Product" sets.
 * @example
 *   cartesianProduct([[1,2], [4,8], [16,32]])
 *   Returns:
 *   [
 *     [1, 4, 16],
 *     [1, 4, 32],
 *     [1, 8, 16],
 *     [1, 8, 32],
 *     [2, 4, 16],
 *     [2, 4, 32],
 *     [2, 8, 16],
 *     [2, 8, 32]
 *   ]
 * @see https://stackoverflow.com/a/36234242/1955709
 * @see https://en.wikipedia.org/wiki/Cartesian_product
 * @param arr {T[][]}
 * @returns {T[][]}
 */
function cartesianProduct<T> (arr: T[][]): T[][] {
  return arr.reduce((a, b) => {
    return a.map(x => {
      return b.map(y => {
        return x.concat(y)
      })
    }).reduce((c, d) => c.concat(d), [])
  }, [[]] as T[][])
}
1
  • This only supports homogeneous types; where all values in the arrays are of the same type.
    – Martijn Pieters
    Mar 21 at 15:19
4

Modern JavaScript in just a few lines. No external libraries or dependencies like Lodash.

function cartesian(...arrays) {
  return arrays.reduce((a, b) => a.flatMap(x => b.map(y => x.concat([y]))), [ [] ]);
}

console.log(
  cartesian([1, 2], [10, 20], [100, 200, 300])
    .map(arr => JSON.stringify(arr))
    .join('\n')
);

4

You could reduce the 2D array. Use flatMap on the accumulator array to get acc.length x curr.length number of combinations in each loop. [].concat(c, n) is used because c is a number in the first iteration and an array afterwards.

const data = [ [1, 2], [10, 20], [100, 200, 300] ];

const output = data.reduce((acc, curr) =>
  acc.flatMap(c => curr.map(n => [].concat(c, n)))
)

console.log(JSON.stringify(output))

(This is based on Nina Scholz's answer)

4

Here's a recursive one-liner that works using only flatMap and map:

const inp = [
  [1, 2],
  [10, 20],
  [100, 200, 300]
];

const cartesian = (first, ...rest) => 
  rest.length ? first.flatMap(v => cartesian(...rest).map(c => [v].concat(c))) 
              : first;

console.log(cartesian(...inp));

3

A few of the answers under this topic fail when any of the input arrays contains an array item. You you better check that.

Anyways no need for underscore, lodash whatsoever. I believe this one should do it with pure JS ES6, as functional as it gets.

This piece of code uses a reduce and a nested map, simply to get the cartesian product of two arrays however the second array comes from a recursive call to the same function with one less array; hence.. a[0].cartesian(...a.slice(1))

Array.prototype.cartesian = function(...a){
  return a.length ? this.reduce((p,c) => (p.push(...a[0].cartesian(...a.slice(1)).map(e => a.length > 1 ? [c,...e] : [c,e])),p),[])
                  : this;
};

var arr = ['a', 'b', 'c'],
    brr = [1,2,3],
    crr = [[9],[8],[7]];
console.log(JSON.stringify(arr.cartesian(brr,crr))); 

3

No libraries needed! :)

Needs arrow functions though and probably not that efficient. :/

const flatten = (xs) => 
    xs.flat(Infinity)

const binaryCartesianProduct = (xs, ys) =>
    xs.map((xi) => ys.map((yi) => [xi, yi])).flat()

const cartesianProduct = (...xss) =>
    xss.reduce(binaryCartesianProduct, [[]]).map(flatten)
      
console.log(cartesianProduct([1,2,3], [1,2,3], [1,2,3]))

3

A more readable implementation

function productOfTwo(one, two) {
  return one.flatMap(x => two.map(y => [].concat(x, y)));
}

function product(head = [], ...tail) {
  if (tail.length === 0) return head;
  return productOfTwo(head, product(...tail));
}

const test = product(
  [1, 2, 3],
  ['a', 'b']
);

console.log(JSON.stringify(test));

1
  • [].concat(x, y) could also be [x, y].flat(). Also, one could write [[1, 2, 3], ['a', 'b']].reduce(productOfTwo) to avoid recursion. Dec 14, 2022 at 10:40
3

Another, even more simplified, 2021-style answer using only reduce, map, and concat methods:

const cartesian = (...arr) => arr.reduce((a,c) => a.map(e => c.map(f => e.concat([f]))).reduce((a,c) => a.concat(c), []), [[]]);

console.log(cartesian([1, 2], [10, 20], [100, 200, 300]));

2
  • in all honesty - I have no idea what's happening here, but it seems to be working fine even for complex objects (unlike some solutions that worked only for strings). I'd appreciate you using some more descriptive names (as opposed to a, c, f, etc) - especially that they overlap each other. What I mean by that is that they have different scopes, but same names, so it's hard to understand.
    – WrRaThY
    Mar 3, 2022 at 4:38
  • ps. typescript types wouldn't hurt as well. so Array<Array<any>> as input (and so on for other variables) as opposed to... well, nothing
    – WrRaThY
    Mar 3, 2022 at 4:40
2

For those happy with a ramda solution:

import { xprod, flatten } from 'ramda';

const cartessian = (...xs) => xs.reduce(xprod).map(flatten)

Or the same without dependencies and two lego blocks for free (xprod and flatten):

const flatten = xs => xs.flat();

const xprod = (xs, ys) => xs.flatMap(x => ys.map(y => [x, y]));

const cartessian = (...xs) => xs.reduce(xprod).map(flatten);

2

Similar in spirit to others, but highly readable imo.

function productOfTwo(a, b) {
  return a.flatMap(c => b.map(d => [c, d].flat()));
}
[['a', 'b', 'c'], ['+', '-'], [1, 2, 3]].reduce(productOfTwo);
1

Just for a choice a real simple implementation using array's reduce:

const array1 = ["day", "month", "year", "time"];
const array2 = ["from", "to"];
const process = (one, two) => [one, two].join(" ");

const product = array1.reduce((result, one) => result.concat(array2.map(two => process(one, two))), []);
1

A simple "mind and visually friendly" solution.

enter image description here


// t = [i, length]

const moveThreadForwardAt = (t, tCursor) => {
  if (tCursor < 0)
    return true; // reached end of first array

  const newIndex = (t[tCursor][0] + 1) % t[tCursor][1];
  t[tCursor][0] = newIndex;

  if (newIndex == 0)
    return moveThreadForwardAt(t, tCursor - 1);

  return false;
}

const cartesianMult = (...args) => {
  let result = [];
  const t = Array.from(Array(args.length)).map((x, i) => [0, args[i].length]);
  let reachedEndOfFirstArray = false;

  while (false == reachedEndOfFirstArray) {
    result.push(t.map((v, i) => args[i][v[0]]));

    reachedEndOfFirstArray = moveThreadForwardAt(t, args.length - 1);
  }

  return result;
}

// cartesianMult(
//   ['a1', 'b1', 'c1'],
//   ['a2', 'b2'],
//   ['a3', 'b3', 'c3'],
//   ['a4', 'b4']
// );

console.log(cartesianMult(
  ['a1'],
  ['a2', 'b2'],
  ['a3', 'b3']
));
1

Yet another implementation. Not the shortest or fancy, but fast:

function cartesianProduct() {
    var arr = [].slice.call(arguments),
        intLength = arr.length,
        arrHelper = [1],
        arrToReturn = [];

    for (var i = arr.length - 1; i >= 0; i--) {
        arrHelper.unshift(arrHelper[0] * arr[i].length);
    }

    for (var i = 0, l = arrHelper[0]; i < l; i++) {
        arrToReturn.push([]);
        for (var j = 0; j < intLength; j++) {
            arrToReturn[i].push(arr[j][(i / arrHelper[j + 1] | 0) % arr[j].length]);
        }
    }

    return arrToReturn;
}
1
  • This works for large arrays, unlike the one-liner.
    – Lance
    Jul 5, 2021 at 9:46
1

A simple, modified version of @viebel's code in plain Javascript:

function cartesianProduct(...arrays) {
  return arrays.reduce((a, b) => {
    return [].concat(...a.map(x => {
      const next = Array.isArray(x) ? x : [x];
      return [].concat(b.map(y => next.concat(...[y])));
    }));
  });
}

const product = cartesianProduct([1, 2], [10, 20], [100, 200, 300]);

console.log(product);
/*
[ [ 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 ] ];
*/
1
f=(a,b,c)=>a.flatMap(ai=>b.flatMap(bi=>c.map(ci=>[ai,bi,ci])))

This is for 3 arrays.
Some answers gave a way for any number of arrays.
This can easily contract or expand to less or more arrays.
I needed combinations of one set with repetitions, so I could have used:

f(a,a,a)

but used:

f=(a,b,c)=>a.flatMap(a1=>a.flatMap(a2=>a.map(a3=>[a1,a2,a3])))
1

A non-recursive approach that adds the ability to filter and modify the products before actually adding them to the result set.

Note: the use of .map rather than .forEach. In some browsers, .map runs faster.

function crossproduct(arrays, rowtest, rowaction) {
  // Calculate the number of elements needed in the result
  var result_elems = 1,
    row_size = arrays.length;
  arrays.map(function(array) {
    result_elems *= array.length;
  });
  var temp = new Array(result_elems),
    result = [];

  // Go through each array and add the appropriate
  // element to each element of the temp
  var scale_factor = result_elems;
  arrays.map(function(array) {
    var set_elems = array.length;
    scale_factor /= set_elems;
    for (var i = result_elems - 1; i >= 0; i--) {
      temp[i] = (temp[i] ? temp[i] : []);
      var pos = i / scale_factor % set_elems;
      // deal with floating point results for indexes,
      // this took a little experimenting
      if (pos < 1 || pos % 1 <= .5) {
        pos = Math.floor(pos);
      } else {
        pos = Math.min(array.length - 1, Math.ceil(pos));
      }
      temp[i].push(array[pos]);
      if (temp[i].length === row_size) {
        var pass = (rowtest ? rowtest(temp[i]) : true);
        if (pass) {
          if (rowaction) {
            result.push(rowaction(temp[i]));
          } else {
            result.push(temp[i]);
          }
        }
      }
    }
  });
  return result;
}

console.log(
crossproduct([[1, 2], [10, 20], [100, 200, 300]],null,null)
)

1
  • I made you a snippet. Perhaps add calls with rowtests and rowactions ? Also where did you see forEach is slower than map?
    – mplungjan
    Sep 8, 2022 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.