javascript - 使用递归组合数组值，即使它们是空的

Question

我有一个函数可以组合数组来构建笛卡尔积(取自 Finding All Combinations of JavaScript array values)。

当也有空数组时，我如何调整下面的函数才能使函数正常工作？

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

Answer 1

求两个集合的笛卡尔积非常简单:

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

例如，如果您想要 ["a","b"] 和 ["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;
}

如果你想找到多个集合的笛卡尔积，那么你可以使用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);
}

但是您需要过滤空集:

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

我们需要这样做的原因很简单。任何与 0 相乘的结果都是 0。因此，我们删除了要相乘的集合列表中的所有零。

演示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;
}

演示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;
}

希望对您有所帮助。