前端工程实践中的笛卡尔积(直积)生成

笛卡尔积(直积)(Cartesian Product)的定义

给定多个集合：

A = [a1, a2]
B = [b1, b2, b3]
C = [c1, c2]

它们的笛卡尔积定义为：

A × B × C = 
    [
        [a1, b1, c1], 
        [a1, b1, c2],
        [a1, b2, c1], 
        [a1, b2, c2],
        ...
    ]

本质：

从每一个集合中各取一个元素，组成一个元组，枚举所有可能。

传统实现方式的问题

最常见的 JavaScript 实现是：

function cartesianProduct(...arrays) {
    return arrays.reduce(
        (acc, cur) => acc.flatMap(a => cur.map(b => [...a, b])),
        [[]]
    );
}

随之产生的问题

假设：

维度数 = d
每个维度平均大小 = k

那么：

结果数量 = k^d
时间复杂度 = O(k^d)
空间复杂度 = O(k^d)

只要数据量稍微大一点，这种写法一定会OOM。

工程中的真实需求是什么？

在实际工程中，我们通常：

不需要全部结果、不允许一次性生成全集
只需要：
- 前 N 个
- 或者随机抽取 N 个

所以核心问题变成了：

如何在不生成完整笛卡尔积的情况下，有序 / 随机地产生部分结果？

可中断的笛卡尔积生成 - 生成器(Generator) 方案

基本思想

深度优先遍历（DFS）
每走到一条完整路径，就 yield 一个结果
外部只取需要的前 N 个

基础实现

static getFirstNCartesianProduct<T>(arrays: T[][], count: number): T[][] {
    const results: T[][] = [];

    function* generate(index = 0, current: T[] = []): Generator<T[]> {
        if (index === arrays.length) {
            yield current;
            return;
        }

        for (const item of arrays[index]) {
            yield* generate(index + 1, [...current, item]);
        }
    }

    const generator = generate();

    while (results.length < count) {
        const next = generator.next();
        if (next.done) break;
        results.push(next.value);
    }

    return results;
}

并不是一次性返回所有结果，而是：

暂停函数执行
把 value 交给调用方
下次 .next() 时从暂停点继续

`yield*` 的作用

yield* generate(nextIndex, nextState);

等价于：

“把子生成器产生的所有 yield，原样转交给当前生成器”

非常关键的一点：

yield* 并不是一次性返回数组
它是 逐个转发子生成器的 yield

用最简单的例子理解

function* inner() {
  yield 1;
  yield 2;
}

function* outer() {
  yield 0;
  yield* inner();
  yield 3;
}

const g = outer()

连续调用g.next()，依次输出的是：

而不是：

0
[1,2]
3

为什么 Generator 方案适合“顺序笛卡尔积”

Generator 方案天然适合：

按字典序
按 DFS 顺序
稳定、可复现

但它有一个限制：

不适合“直接随机访问第 K 个组合”

这正好引出了另一类方案。

随机笛卡尔积：混合进制（Mixed-radix）枚举

核心思想

假设：

arrays = [
  [A, B, C],   // 3
  [1, 2],      // 2
  [x, y, z]    // 3
]

那么每一个组合都可以看成一个 混合进制数：

[ i0, i1, i2 ]
其中：
0 ≤ i0 < 3
0 ≤ i1 < 2
0 ≤ i2 < 3

static _generateRandomCombination = <T>(
  arrays: T[][],
  maxIndex: number[]
): T[] => {
  return maxIndex.map((len, i) =>
    arrays[i][Math.floor(Math.random() * len)]
  );
};

特点：

O(维度数)
不需要生成全集
非常适合随机采样

受控随机采样主函数

从给定的多维数组中随机生成或计算笛卡尔积中指定数量的样本组合。
根据样本数量与总组合数量的比例，自动选择策略：

直接展开完整笛卡尔积（小规模）
随机采样 + 去重（小样本）
随机采样（允许重复，大样本）

static randomCartesianProduct = <T>(
  arrays: T[][],
  numSamples: number
): T[][] => {
  const maxIndex = arrays.map(arr => arr.length);
  const totalCombinations = maxIndex.reduce((acc, val) => acc * val, 1);

  // 情况 1：空间较小，直接展开
  if (numSamples > 0.6 * totalCombinations || totalCombinations < 10000) {
    return this.randomChild(
      this.cartesianProduct(...arrays),
      numSamples
    );
  }

  // 情况 2：样本量较小，去重采样
  else if (numSamples < 0.2 * totalCombinations) {
    const result: T[][] = [];
    const seen = new Set<string>();

    while (result.length < numSamples) {
      const combination = this._generateRandomCombination(arrays, maxIndex);
      const key = JSON.stringify(combination);

      if (!seen.has(key)) {
        seen.add(key);
        result.push(combination);
      }
    }
    return result;
  }

  // 情况 3：中间区间，允许重复，性能优先
  else {
    const result: T[][] = [];
    for (let i = 0; i < numSamples; i++) {
      result.push(this._generateRandomCombination(arrays, maxIndex));
    }
    return result;
  }
};

工程级笛卡尔积策略总结

需求	推荐方案
顺序、可复现	Generator（DFS + yield）
只取前 N 个	Generator + 截断
随机抽样	混合进制随机
样本接近全集	直接生成全集再 shuffle
数据量巨大	Generator / Mixed-radix

总结

这是一套使用在
https://www.xfan.top/index.php/2024/03/18/novelai-prompts-task-writer/
中的计算方法，用以解决大量提示词的顺序、随机组合问题。
参与笛卡尔积计算的集合是上一步排列、组合生成的，通常有十几至几十个集合，每个集合可能包含多达数十个元素，样本空间可能超出Number类型可存储的上限，计算相关