如何生成数组所有组合并限制每个分组最多仅出现一个元素

实现思路 #

首先将原始数组按groupId分组，每组的可选规则为：要么不选该组的任何元素，要么选该组内的任意一个元素。对所有组的可选结果做笛卡尔积后，排除全不选的空组合，即可得到所有符合要求的合法组合。

以你给出的示例数组为例：

• foo组共3个元素，可选状态有4种：不选、选1、选2、选3
• bar组共2个元素，可选状态有3种：不选、选4、选5
• zoo组共1个元素，可选状态有2种：不选、选6
  总组合数为 4*3*2 - 1 = 23 种，减去的1是所有组都不选的空组合。

代码实现 #

function getValidCombinations(list) {
  // 按groupId分组
  const groupMap = {};
  list.forEach(item => {
    if (!groupMap[item.groupId]) groupMap[item.groupId] = [];
    groupMap[item.groupId].push(item);
  });
  const groups = Object.values(groupMap);

  // 递归计算所有组的可选组合笛卡尔积
  let result = [[]];
  for (const group of groups) {
    const temp = [];
    for (const prevComb of result) {
      // 情况1：当前组不选任何元素
      temp.push([...prevComb]);
      // 情况2：当前组选一个元素
      for (const item of group) {
        temp.push([...prevComb, item]);
      }
    }
    result = temp;
  }

  // 过滤空组合
  return result.filter(comb => comb.length > 0);
}

测试示例 #

const myArray = [
  { groupId: "foo", value: 1 },
  { groupId: "foo", value: 2 },
  { groupId: "foo", value: 3 },
  { groupId: "bar", value: 4 },
  { groupId: "bar", value: 5 },
  { groupId: "zoo", value: 6 },
];

const validCombinations = getValidCombinations(myArray);
console.log(validCombinations.length); // 输出23，符合预期

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