Cartesian product of objects in javascript

Question

I need to create a complete set of options based on a list of N attributes, while keeping the attribute name intact.

var input = [ { 'colour' : ['red', 'green'] }, { 'material' : ['cotton', 'wool', 'silk'] }, { 'shape' : ['round', 'square', 'rectangle'] } ]; var expected = [ { 'colour': 'red', 'material': 'cotton', 'shape': 'round' }, { 'colour': 'red', 'material': 'cotton', 'shape': 'square' }, { 'colour': 'red', 'material': 'cotton', 'shape': 'rectangle' }, { 'colour': 'red', 'material': 'wool', 'shape': 'round' }, { 'colour': 'red', 'material': 'wool', 'shape': 'square' }, { 'colour': 'red', 'material': 'wool', 'shape': 'rectangle' }, { 'colour': 'red', 'material': 'silk', 'shape': 'round' }, { 'colour': 'red', 'material': 'silk', 'shape': 'square' }, { 'colour': 'red', 'material': 'silk', 'shape': 'rectangle' }, { 'colour': 'green', 'material': 'cotton', 'shape': 'round' }, { 'colour': 'green', 'material': 'cotton', 'shape': 'square' }, { 'colour': 'green', 'material': 'cotton', 'shape': 'rectangle' }, { 'colour': 'green', 'material': 'wool', 'shape': 'round' }, { 'colour': 'green', 'material': 'wool', 'shape': 'square' }, { 'colour': 'green', 'material': 'wool', 'shape': 'rectangle' }, { 'colour': 'green', 'material': 'silk', 'shape': 'round' }, { 'colour': 'green', 'material': 'silk', 'shape': 'square' }, { 'colour': 'green', 'material': 'silk', 'shape': 'rectangle' } ]; 

There are many algorithms for the Cartesian products of arrays, but I cannot find them for objects that store keys.

Performance is not a big concern, since there will never be more than a dozen values ​​for each attribute. Order must not exactly match expected .

I made an initial attempt based on standard algorithms for lists, but I'm afraid:

 function cartesianProduct(input, current) { if (!input || input.length < 1) { return []; } var head = input[0]; var tail = input.slice(1); var output = []; for (var key in head) { for (var i = 0; i < head[key].length; i++) { if (typeof current == 'undefined') { var current = {}; } current[key] = head[key][i]; var productOfTail = cartesianProduct(tail, current); output.push(current); console.log(current); } } return output; } console.log(cartesianProduct(input)); 

Answer 1

Once you get rid of "i", this is a global problem with var ", you can get the result with this code, for example:

 var input = [ { 'colour' : ['red', 'green'] }, { 'material' : ['cotton', 'wool', 'silk'] }, { 'shape' : ['round', 'square', 'rectangle'] } ]; function cartesianProduct(input, current) { if (!input || !input.length) { return []; } var head = input[0]; var tail = input.slice(1); var output = []; for (var key in head) { for (var i = 0; i < head[key].length; i++) { var newCurrent = copy(current); newCurrent[key] = head[key][i]; if (tail.length) { var productOfTail = cartesianProduct(tail, newCurrent); output = output.concat(productOfTail); } else output.push(newCurrent); } } return output; } function copy(obj) { var res = {}; for (var p in obj) res[p] = obj[p]; return res; } console.log(cartesianProduct(input)); 

Answer 2

Here is a solution using Ramda.js

 const input = [ { 'colour': ['red', 'green'] }, { 'material': ['cotton', 'wool', 'silk'] }, { 'shape': ['round', 'square', 'rectangle'] } ] const cartesianProductList = (Xs) => ( R.reduce( (Ys, X) => ( R.map(R.apply(R.append), R.xprod(X, Ys)) ), [[]], Xs ) ) const xPairs = (x, xs) => ( R.map(R.pair(x), xs) ) const cartesianProductObject = (objs) => ( R.pipe( R.mergeAll, R.toPairs, R.map(R.apply(xPairs)), cartesianProductList, R.map(R.fromPairs), )(objs) ) console.log(cartesianProductObject(input)) 

 <script src="//cdnjs.cloudflare.com/ajax/libs/ramda/0.25.0/ramda.min.js"></script>