Combining array values using recursion even if they're empty

Question

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

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. — Md Ashaduzzaman, Oct 29 '14 at 11:54

score 3 · Accepted Answer · answered Oct 29 '14 at 12:05

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.

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

Combining array values using recursion even if they're empty

1 Answers1

Demo 1

Demo 2