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

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

  目录