current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite

I have a function that combines arrays to build a cartesian product (as taken from Finding All Combinations of JavaScript array values).

How would I adjust the function below to get the function working when there are empty arrays too?

var array_1 = [['a', 'b'], ['c', 'z'], ['d', 'e', 'f']];
var array_2 = [[], ['b', 'z'], ['d', 'e', 'f']];

function allPossibleCases(arr) {
  if (arr.length === 0) {
    return [];
  } 
  else if (arr.length ===1){
    return arr[0];
  }
  else {
    var result = [];
    var allCasesOfRest = allPossibleCases(arr.slice(1));  // recur with the rest of array
    for (var c in allCasesOfRest) {
      for (var i = 0; i < arr[0].length; i++) {
        result.push(arr[0][i] + allCasesOfRest[c]);
      }
    }
    return result;
  }
}

var result_1 = allPossibleCases(array_1);
// outputs ["acd", "bcd", "azd", "bzd", "ace", "bce", "aze", "bze", "acf", "bcf", "azf", "bzf"];

var result_2 = allPossibleCases(array_2);
// current output [];
// desired output ["bd", "be", "bf", "zd", "ze", "zf"];
share|improve this question
    
just out of curiosity, why is that the desired output? The Cartesian product of an empty set with anything else is itself an empty set, so result_2 is mathematically correct. –  The Paramagnetic Croissant Oct 29 '14 at 11:36
    
Anyway, if you really need this, you could just do var result2 = allPossibleCases(array_2.filter(function (v) { return v.length; }));. –  The Paramagnetic Croissant Oct 29 '14 at 11:37
    
Create a new array having no empty array and pass it as the parameter of allPossibleCases function. –  Ashad Shanto Oct 29 '14 at 11:54

1 Answer 1

up vote 3 down vote accepted

Finding the Cartesian product of two sets is really simple:

function product(f, xs, ys) {
    var zs = [];

    var m = xs.length;
    var n = ys.length;

    for (var i = 0; i < m; i++) {
        var x = xs[i];

        for (var j = 0; j < n; j++) {
            var y = ys[j];
            var z = f(x, y);
            zs.push(z);
        }
    }

    return zs;
}

For example, if you want the cartesian product of ["a","b"] and ["c","z"]:

var xs = ["a","b"];
var ys = ["c","z"];
var zs = product(add, xs, ys); // ["ac", "az", "bc", "bz"]

function add(a, b) {
    return a + b;
}

If you want to find the cartesian product of more than one set then you could use reduce:

var xss = [["a","b"],["c","z"],["d","e","f"]];

var xs = xss.reduce(productAdd); // ["acd","ace","acf",
                                 //  "azd","aze","azf",
                                 //  "bcd","bce","bcf",
                                 //  "bzd","bze","bzf"]

function productAdd(xs, ys) {
    return product(add, xs, ys);
}

However you would need to filter out empty sets:

var yss = [[],["b","z"],["d","e","f"]];

var ys = yss.filter(nonEmpty).reduce(productAdd); // ["bd","be","bf",
                                                  //  "zd","ze","zf"]

function nonEmpty(xs) {
    return xs.length > 0;
}

function productAdd(xs, ys) {
    return product(add, xs, ys);
}

The reason we need to do this is pretty simple. Anything multiplied with 0 is 0. Hence we remove all the zeros in the list of sets which we are multiplying.

Demo 1

var xss = [["a","b"],["c","z"],["d","e","f"]];

var xs = xss.reduce(productAdd);

alert(JSON.stringify(xs));

function productAdd(xs, ys) {
    return product(add, xs, ys);
}

function add(a, b) {
    return a + b;
}

function product(f, xs, ys) {
    var zs = [];

    var m = xs.length;
    var n = ys.length;

    for (var i = 0; i < m; i++) {
        var x = xs[i];

        for (var j = 0; j < n; j++) {
            var y = ys[j];
            var z = f(x, y);
            zs.push(z);
        }
    }

    return zs;
}

Demo 2

var yss = [[],["b","z"],["d","e","f"]];

var ys = yss.filter(nonEmpty).reduce(productAdd);

alert(JSON.stringify(ys));

function nonEmpty(xs) {
    return xs.length > 0;
}

function productAdd(xs, ys) {
    return product(add, xs, ys);
}

function add(a, b) {
    return a + b;
}

function product(f, xs, ys) {
    var zs = [];

    var m = xs.length;
    var n = ys.length;

    for (var i = 0; i < m; i++) {
        var x = xs[i];

        for (var j = 0; j < n; j++)
            zs.push(f(x, ys[j]));
    }

    return zs;
}

Hope that helps.

share|improve this answer
    
Fantastic answer. This solves the problem perfectly. Thank you. –  gosseti Oct 29 '14 at 12:17
    
When running this on an array of empty arrays, e.g. empty_array.filter(nonEmpty).reduce(productAdd), I get a Uncaught TypeError: Reduce of empty array with no initial value in console. How would I tackle this? –  gosseti Oct 29 '14 at 12:40
    
I'm assuming that empty_array is something like [[],[],[]]. If so then empty_array.filter(nonEmpty) is an array with no values (i.e. []). You get an error because you can't get the product of nothing. The product of [[],[],[]] is [] (i.e. 0 * 0 * 0 = 0). However, the product of [] doesn't exist. Therefore, the solution is to not filter the list (i.e. don't do .filter(nonEmpty)). However this brings us back to square 1. Hence instead, do: function productOf(xss) { var yss = xss.filter(nonEmpty); return yss.length ? yss.reduce(productAdd) : yss; } & productOf(empty_array). –  Aadit M Shah Oct 29 '14 at 13:12
    
That's working great. Thanks again, Aadit. –  gosseti Oct 29 '14 at 15:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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