Cartesian product of objects in javascript

Question

I need to generate a complete set of variants 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 lots of algorithms around for cartesian products of arrays, but I can't seem to find one for objects that preserves the keys.

Performance isn't a massive concern as there will never be more than a dozen or so values for each attribute. The order doesn't have to exactly match expected.

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

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

Spoonfeed

there is a big issue in your code : you don't declare i as a var, so it is considered a global var, hence changed in the inner function calls... – Aril

Answer 1

Once you get rid of the ' 'i' is a global var issue', you can get to the result with this code for instance :

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

Aril

Cheers for that, I knew there was an issue with pushing current to the output array but couldn't work out why. – Spoonfeed

You're welcome. As you allready understood, without copying, you keep on changing a single object in each recursive call, hence the product not working. – Aril

Answer 2

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

Concord