Cartesian product of javascript object properties

Question

I have an object of the following form (simplified test case below)

var test = {
        shirts: {
            sizes: ['large', 'medium']
            ,colors:['red', 'blue']
        }
        , trousers: {
            type: ['formal', 'casual']
            , pattern: ['plaid', 'stripes']
        }
    };

I want to generate a cartesian product of the properties so that the output is an array of the following form:

// desired output

[ {shirts:{sizes:'large', color:'red'}, trousers:{type:'formal', pattern:'plaid'}}
  ,{shirts:{sizes:'large', color:'red'}, trousers:{type:'formal', pattern:'stripes'}}
  ,{shirts:{sizes:'large', color:'red'}, trousers:{type:'casual', pattern:'plaid'}}
  , {shirts:{sizes:'large', color:'red'}, trousers:{type:'casual', pattern:'stripes'}}
  ,{shirts:{sizes:'large', color:'blue'}, trousers:{type:'formal', pattern:'plaid'}}
..... and so on  ]

How can I achieve this? I worked up the following code (based on a modification of code for cartesian product of array from another SO post) but I seem to be tying myself in knots trying to get this to work.

 function myCartesianProduct(input, current) {
    if (!input) { return []; }


    var head = input[Object.keys(input)[0]];

    var tail = objSlice(input);

    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 (Object.keys(tail).length) {   //if tail.length
                var productOfTail =
                        myCartesianProduct(tail, newCurrent);
                output = output.concat(productOfTail);

            } else {
                output.push(newCurrent);

            }
        }
    }
    return output;
}


function objSlice(obj) {
    var slicedObj = angular.copy(obj);  // copy object using angularJs copy method
    delete slicedObj[Object.keys(slicedObj)[0]]; //delete the first key
    return slicedObj;
};

function copy(obj) {
        var res = {};
        for (var p in obj) res[p] = obj[p];
        return res;
    }

console.log(myCartesianProduct(test));

Thanks in advance for your help with this!

See http://stackoverflow.com/questions/12303989/cartesian-product-of-multiple-arrays-in-javascript — Paul, Nov 02 '14 at 09:19
@Paul, this case is different. I did see the other posts on this (and created the code based on a modification), but there is a difference in that in this case, we have nested object properties as opposed to array of arrays. — Jarnal, Nov 02 '14 at 09:24
Yes, I was thinking perhaps you could combine Object.keys() on sub-objects with the function for cartesian product of arrays in the other question, and then restructure the output from an array of arrays to an array of objects, with, say `map` — Paul, Nov 02 '14 at 09:27

score 9 · Accepted Answer · answered Nov 02 '14 at 09:56

Ok, let's start with a function that generates a product of given arrays:

function product(args) {
    if(!args.length)
        return [[]];
    var prod = product(args.slice(1)), r = [];
    args[0].forEach(function(x) {
        prod.forEach(function(p) {
            r.push([x].concat(p));
        });
    });
    return r;
}

The next one uses product to convert something like {a:[1,2], b:[3,4]} into [{a:1,b:3},{a:1,b:4},{a:2,b:3},{a:2,b:4}]:

function objectProduct(obj) {
    var keys = Object.keys(obj),
        values = keys.map(function(x) { return obj[x] });

    return product(values).map(function(p) {
        var e = {};
        keys.forEach(function(k, n) { e[k] = p[n] });
        return e;
    });
}

For your test data, you have to apply it twice:

var result = {};
Object.keys(test).forEach(function(k) {
    result[k] = objectProduct(test[k])
});

result = objectProduct(result);

This gives you the output you wanted.

Cartesian product of javascript object properties

1 Answers1

Linked