用JavaScrip实现笛卡尔积

2019年11月18日

定义

笛卡尔乘积是指在数学中,两个集合X和Y的笛卡尔积(Cartesian product),又称直积,表示为X × Y,第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员。

表达式

A×B = {(x,y)|x∈A∧y∈B}
设A,B为集合,用A中元素为第一元素,B中元素为第二元素构成有序对,所有这样的有序对组成的集合叫做A与B的笛卡尔积,记作AxB.
笛卡尔积的符号化为:
A×B={(x,y)|x∈A∧y∈B}
例如,A={a,b}, B={0,1,2},则
A×B={(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}
B×A={(0, a), (0, b), (1, a), (1, b), (2, a), (2, b)}

js实现思路

对于两个数组很好解决,只需要循环即可,多重数组笛卡尔积只需要两个数组的基础上进行累计乘积就好了。

function cartesianProduct(...args) {
  let len = args.length;
  if (len <= 1) return args[0];
  let curPos = 0;
  let result = [];
  while (len--) {
    if (result.length === 0) {
      result = args[curPos];
    } else {
      const arr = [];
      result.forEach(prev => {
        args[curPos].forEach(cur => {
          arr.push(`${prev}-${cur}`);
        });
      });
      result = [].concat(arr);
    }
    curPos += 1;
  }

  return result;
}

如果使用ES6的reduce函数,会让代码更精简和直观

reduce版

function cartesianProduct(...args) {
  return args.reduce((prev, cur) => {
    const arr = [];
    prev.forEach(cp1 => {
      cur.forEach(cp2 => {
        arr.push(`${cp1}-${cp2}`);
      });
    });
    return arr;
  });
}

// 测试
cartesianProduct([1, 2, 3], ["a", "b", "c"], ["11", "22", "33"])
0 条评论