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返回值

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