TypeScript中如何用递归实现动态多层嵌套for循环的笛卡尔积？

递归实现方案 #

思路 #

通过递归逐步拆解问题：每次取数组的第一个元素，递归计算剩余元素的笛卡尔积，再将当前元素的每个值与剩余部分的每个组合拼接，最终得到所有可能的笛卡尔积组合。若需要和原固定循环的输出顺序一致，只需将输入数组反转后传入。

TypeScript代码实现 #

// 定义Option类型替代any，增强类型安全
interface Option {
  name: string;
  option: string;
}

function cartesianProduct(arr: { type: string; values: Option[] }[]): Option[][] {
  // 递归终止条件：空数组返回包含空数组的数组
  if (arr.length === 0) return [[]];

  const [first, ...rest] = arr;
  // 递归计算剩余元素的笛卡尔积
  const restCombinations = cartesianProduct(rest);

  // 将当前元素的每个值与剩余组合拼接
  return first.values.flatMap(value => 
    restCombinations.map(comb => [value, ...comb])
  );
}

// 示例输入
const arr = [
  {
    type: "color",
    values: [
      { name: "Color", option: "Black" },
      { name: "Color", option: "Blue" },
    ],
  },
  {
    type: "size",
    values: [
      { name: "Size", option: "XS" },
      { name: "Size", option: "M" },
    ],
  },
];

// 若需与原固定循环的输出顺序一致，反转输入数组
const result = cartesianProduct([...arr].reverse());
console.log(result);

输出验证 #

上述代码运行后，输出结果与你提供的期望输出完全一致，且支持任意长度的输入数组，无需修改代码适配层数。

发帖前需补充的细节 #

• TypeScript版本说明：flatMap是ES2019的特性，若你的TS版本较低，需说明是否需要兼容旧版本，可提供替代实现（如用reduce+concat替换flatMap）。
• 输出顺序要求：明确是否必须保持原固定循环中“从最后一个元素到第一个元素”的组合顺序，还是允许按输入数组正序生成组合。
• 边界情况处理：说明是否需要处理values为空数组的场景，比如当某一层无选项时，是否返回空数组还是跳过该层。
• 性能需求：是否需要处理大规模数据？递归在极端场景下可能有栈溢出风险，若有性能要求，可补充是否需要迭代版实现。
• 类型约束细节：说明是否已有明确的values对象类型定义，是否需要强类型支持而非使用any。

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