JavaScript中多数组的条件笛卡尔积实现问题

问题说明 #

给定：

• 参数列表：let params = [[1,2,3], ["A","B","C"], [10,11,12]]
• 配对限制规则：let pairRestrictions = {0:{2:{1:["A","B"]}}}
  规则解释：
• 键0：第一个参数的索引
• 键2：当第一个参数取值为2时
• 键1：对应限制的第二个参数的索引
• 数组["A","B"]：第二个参数仅允许取这两个值

需要实现函数generateCombinations(params, pairRestrictions)，生成params的笛卡尔积并遵循上述限制，返回符合要求的组合数组。

预期输出 #

let result = [
  [1, 'A', 10], [1, 'A', 11], [1, 'A', 12],
  [1, 'B', 10], [1, 'B', 11], [1, 'B', 12],
  [1, 'C', 10], [1, 'C', 11], [1, 'C', 12],
  [2, 'A', 10], [2, 'A', 11], [2, 'A', 12],
  [2, 'B', 10], [2, 'B', 11], [2, 'B', 12],
  [3, 'A', 10], [3, 'A', 11], [3, 'A', 12],
  [3, 'B', 10], [3, 'B', 11], [3, 'B', 12],
  [3, 'C', 10], [3, 'C', 11], [3, 'C', 12]
]

当前代码（无限制逻辑） #

已实现普通笛卡尔积生成，但未集成限制规则：

function recur(combinations = [], i) {
  let res = [];
  if (i === params.length) {
    return combinations;
  }
  for (let p in params[i]) {
    let combinationsCopy = [];
    for (let c in combinations) {
      combinationsCopy.push(combinations[c].concat(params[i][p]));
    }
    res = res.concat(combinationsCopy);
  }
  return recur(res, i + 1);
}
recur(
    params[0].map((x) => [x]),
    1
);

解决方案 #

通过在递归生成组合的过程中添加限制校验，筛选符合规则的取值：

function generateCombinations(params, pairRestrictions) {
  function recur(currentCombos, currentIndex) {
    if (currentIndex === params.length) {
      return currentCombos;
    }

    const nextParamValues = params[currentIndex];
    const validCombos = [];

    for (const combo of currentCombos) {
      let allowedValues = [...nextParamValues];

      // 检查当前组合是否触发对当前参数的限制
      for (const [prevParamIdx, valueRules] of Object.entries(pairRestrictions)) {
        const prevValue = combo[prevParamIdx];
        if (valueRules[prevValue] && valueRules[prevValue][currentIndex]) {
          allowedValues = valueRules[prevValue][currentIndex];
          break;
        }
      }

      // 检查当前组合是否违反已有限制（当前参数作为被限制的前置参数）
      let isComboValid = true;
      for (const [restrictedParamIdx, valueRules] of Object.entries(pairRestrictions)) {
        if (restrictedParamIdx == currentIndex) {
          for (const [prevValue, targetRules] of Object.entries(valueRules)) {
            for (const [targetIdx, allowedVals] of Object.entries(targetRules)) {
              if (targetIdx < currentIndex) {
                const targetValue = combo[targetIdx];
                if (combo[prevParamIdx] == prevValue && !allowedVals.includes(targetValue)) {
                  isComboValid = false;
                  break;
                }
              }
            }
            if (!isComboValid) break;
          }
          if (!isComboValid) break;
        }
      }

      if (!isComboValid) continue;

      // 添加所有允许的取值到组合中
      for (const val of allowedValues) {
        validCombos.push([...combo, val]);
      }
    }

    return recur(validCombos, currentIndex + 1);
  }

  const initialCombos = params[0].map(val => [val]);
  return recur(initialCombos, 1);
}

// 测试示例
const params = [[1,2,3], ["A","B","C"], [10,11,12]];
const pairRestrictions = {0:{2:{1:["A","B"]}}};
console.log(generateCombinations(params, pairRestrictions));

核心逻辑 #

1. 限制筛选：在每次添加新参数值前，先通过pairRestrictions判断当前组合是否触发限制，筛选出允许的取值集合。
2. 反向校验：检查当前组合是否违反了以当前参数为前置条件的限制规则，避免生成不符合要求的组合。
3. 递归生成：从第一个参数的单元素组合开始，逐步递归扩展，只保留符合限制的组合。

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