如何用JavaScript递归实现按分段分组获取数组的所有交叉组合

思路说明 #

• 第一步：对源数组按子数组的首项值进行分组，分组后每个子项剔除首项，仅保留后续需要参与组合的字段
• 第二步：对所有分组执行递归笛卡尔积运算，保证每个组合结果从每个分组中恰好取1个元素

完整代码 #

function getGroupedCombinations(sourceArr) {
  // 1. 按首项分组，处理每个子项去掉首项
  const groupMap = new Map()
  sourceArr.forEach(item => {
    const groupKey = item[0]
    const value = item.slice(1)
    if (!groupMap.has(groupKey)) {
      groupMap.set(groupKey, [])
    }
    groupMap.get(groupKey).push(value)
  })
  const groups = Array.from(groupMap.values())
  
  // 2. 递归计算笛卡尔积
  function recursiveCartesian(groups, currentIndex = 0, currentCombination = []) {
    // 递归终止条件：遍历完所有分组，返回当前组合
    if (currentIndex === groups.length) {
      return [currentCombination]
    }
    const result = []
    const currentGroup = groups[currentIndex]
    // 遍历当前分组的每一项，和后续分组的所有组合拼接
    for (const item of currentGroup) {
      const nextCombinations = recursiveCartesian(groups, currentIndex + 1, [...currentCombination, item])
      result.push(...nextCombinations)
    }
    return result
  }
  
  return recursiveCartesian(groups)
}

// 测试用例
const sourceArr = [
  [0,60,100],
  [0,60,200],
  [0,66,300],
  [1,69,500],
  [2,70,600],
  [2,70,700],
  [2,77,800],
  [2,77,900]
]
console.log(getGroupedCombinations(sourceArr))

输出说明 #

你给出的预期结果中括号存在笔误（混用了{和[），上述代码输出的结果格式完全匹配需求逻辑，测试用例运行后会输出共314=12组组合，和你给出的预期内容完全一致。

内容的提问来源于stack exchange，提问作者brian123