JS全组合实现 - 沐码小站

经常混迹思否，社区里偶有同学问组合的实现，可能是结合各种各样的实际问题。

一、需求

全组合的问题大概类似：
输入为一个数组，包含多个子数组：

[[1,2],  ['a','b']]

输出，输入所有子数组的全组合：

[[1,"a"],[2,"a"],[1,"b"],[2,"b"]]

二、实现思路

在介绍实现思路前先介绍一下笛卡尔积（摘自百度百科）：

笛卡尔乘积是指在数学中，两个集合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)}。

全组合的实现，可以借鉴笛卡尔积的求法，实现思路如下：

如果输入list长度为0，则直接返回空数组
如果输入list长度大于等于1，则直接返回list[0]的每一项构成的单元素数组组成的数组，比如[[1,2]] => [[1],[2]]，记为result。对于list的第二项以及以后的每一项，都依次和result做笛卡尔积，并把笛卡尔积的每一项（类似[[ 1 ],'a' ]）中的第二项（值）追加到第一项（数组）后面，收集到一个新数组里，用这个数组替换result，只到list遍历完成。

三、代码实现

1. for循环实现

function combination (list) {
	let result = []  
  if (!list.length) return 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])
        subResult.push(...tailList)
      }
      result = subResult
    }
  }
  return result
}

2. 函数式编程实现
如果你熟悉JS数组的高阶函数，应该不难看懂。相比for循环，代码少几行，简洁，但是对于一些同学来说可读性可能并不一定好。

function combination(list) {
  return list.reduce((result, subList) => {
    return subList.reduce((subResult, item) => {
      let tail = result.length ? result.map(l => [...l, item]) : [[item]]
      return subResult.concat(tail)
    }, [])
  }, [])
}