JS中的笛卡尔乘积

笛卡尔乘积定义

• 笛卡尔乘积是指在数学中，两个集合X和Y的笛卡尔积（Cartesian product），又称直积，表示为X×Y，第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员。
• 假设集合A={a, b}，集合B={0, 1, 2}，则两个集合的笛卡尔积为{(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}。
• 摘自百度百科

js实现笛卡尔乘积

const list = [
  ['热', '冷', '冰'],
  ['大', '中', '小'],
  ['全糖', '半糖'],
  ['现喝', '打包'],
];

// 根据 list 计算所有组合结果
let arr = [
  '热大全糖现喝', '热大全糖打包', '热大半糖现喝',
  '热大半糖打包', '热中全糖现喝', '热中全糖打包',
  '热中半糖现喝', '热中半糖打包', '热小全糖现喝',
  '热小全糖打包', '热小半糖现喝', '热小半糖打包',
  '冷大全糖现喝', '冷大全糖打包', '冷大半糖现喝',
  '冷大半糖打包', '冷中全糖现喝', '冷中全糖打包',
  '冷中半糖现喝', '冷中半糖打包', '冷小全糖现喝',
  '冷小全糖打包', '冷小半糖现喝', '冷小半糖打包',
  '冰大全糖现喝', '冰大全糖打包', '冰大半糖现喝',
  '冰大半糖打包', '冰中全糖现喝', '冰中全糖打包',
  '冰中半糖现喝', '冰中半糖打包', '冰小全糖现喝',
  '冰小全糖打包', '冰小半糖现喝', '冰小半糖打包'
]

• 思路

  1. 从原数组中取出前两项数组相互组合得到组合结果1
  2. 再利用组合结果1与原数组第三项数组相互组合得到结果2
  3. 依此类推，组合完原数组的所有数组项得到最终组合结果

• 实现代码

  // 法一
  const result = list.reduce((previousValue, currentValue) => {
    const next = [];
    for (let a of previousValue) {
      for (let b of currentValue) {
        next.push(a + b);
      }
    }
    return next;
  });
  console.log('result', result);
  
  // 法二
  const result2 = list.reduce((previousValue, currentValue) => {
    return previousValue.reduce((ret, a) => {
        ret.push(...currentValue.map(b => a + b));
        return ret;
    }, []);
  });
  console.log('result2',result2);
  
  // 法三
  function combination (list) {
  	let result = []  
    if (!list.length) return result // list长度为0时直接返回result
    for (let subList of list) {
      if (!result.length) {
        result = subList.map(item => [item])
      } else {
        let subResult = []
        for (let r of result) {
          let tailList = subList.map(item => r + item) // [...r,item]
          subResult.push(...tailList)
        }
        result = subResult
      }
    }
    return result
  }
  console.log("combination",combination(list))

Tips：reduce()语法

• reduce()语法

  arr.reduce(callback,[initialValue]) 
  // callback 回调函数
  // initialValue 初始值

• callback函数包含四个参数：

  • previousValue：上一次调用callback时的返回值。在第一次调用时，若指定了初始值initialValue，其值则为initialValue，否则为数组索引为0的元素array[0]
  • currentValue：数组中正在处理的元素。在第一次调用时，若指定了初始值initialValue，其值则为数组索引为0的元素·，否则为array[1]
  • currentIndex：数组中正在处理的元素的索引。若指定了初始值initialValue，则起始索引号为0，否则从索引1起始。
  • array：用于遍历的数组

• initialValue(可选)

  • 作为第一次调用callback函数时参数previousValue的值。若指定了初始值initialValue，则currentValue则将使用数组第一个元素；否则previousValue将使用数组第一个元素，而currentValue将使用数组第二个元素

• reduce返回值

  • 回调函数遍历整个数组后的结果