CombinatoricsKit 排列、组合、全排列与笛卡尔积工具类 (TypeScript)

CombinatoricsKit.ts

/**
 * 集合操作工具类
 * 支持排列、组合、笛卡尔积和全排列操作
 */
class CombinatoricsKit<T> {
  private elements: T[];

  // #region 构造函数
  /**
   * 构造函数
   * @param elements 集合元素数组
   */
  constructor(elements: T[] = []) {
    // 使用副本防止外部修改
    this.elements = [...elements];
  }
  // #endregion

  // #region 排列相关方法
  /**
   * 计算排列数 P(n,m) = n!/(n-m)!
   * @param m 选取的元素数量
   * @returns 排列数
   */
  permutationCount(m: number): number {
    if (m < 0 || m > this.elements.length) {
      throw new Error(`Invalid value for m: ${m}. Must be between 0 and ${this.elements.length}.`);
    }

    return this.factorial(this.elements.length) / this.factorial(this.elements.length - m);
  }

  /**
   * 生成所有可能的排列（从n个元素中取m个并考虑顺序）
   * @param m 选取的元素数量
   * @returns 所有可能排列的数组
   */
  permutations(m: number): T[][] {
    if (m < 0 || m > this.elements.length) {
      throw new Error(`Invalid value for m: ${m}. Must be between 0 and ${this.elements.length}.`);
    }

    const result: T[][] = [];

    // 辅助函数：生成排列
    const generatePermutation = (arr: T[], current: T[] = []): void => {
      if (current.length === m) {
        result.push([...current]);
        return;
      }

      for (let i = 0; i < arr.length; i++) {
        const newArr = [...arr.slice(0, i), ...arr.slice(i + 1)];
        current.push(arr[i]);
        generatePermutation(newArr, current);
        current.pop();
      }
    };

    generatePermutation([...this.elements]);
    return result;
  }
  // #endregion

  // #region 组合相关方法
  /**
   * 计算组合数 C(n,m) = n!/(m!(n-m)!)
   * @param m 选取的元素数量
   * @returns 组合数
   */
  combinationCount(m: number): number {
    if (m < 0 || m > this.elements.length) {
      throw new Error(`Invalid value for m: ${m}. Must be between 0 and ${this.elements.length}.`);
    }

    return this.factorial(this.elements.length) /
      (this.factorial(m) * this.factorial(this.elements.length - m));
  }

  /**
   * 生成所有可能的组合（从n个元素中取m个，不考虑顺序）
   * @param m 选取的元素数量
   * @returns 所有可能组合的数组
   */
  combinations(m: number): T[][] {
    if (m < 0 || m > this.elements.length) {
      throw new Error(`Invalid value for m: ${m}. Must be between 0 and ${this.elements.length}.`);
    }

    const result: T[][] = [];

    // 辅助函数：生成组合
    const generateCombination = (startIndex: number, current: T[] = []): void => {
      if (current.length === m) {
        result.push([...current]);
        return;
      }

      for (let i = startIndex; i < this.elements.length; i++) {
        current.push(this.elements[i]);
        generateCombination(i + 1, current);
        current.pop();
      }
    };

    generateCombination(0);
    return result;
  }

  /**
   * 计算全部子组合的数量（长度从 0 到 n 的所有组合）
   * @returns 所有子组合的数量
   */
  allSubCombinationsCount(): number {
    let totalCount = 0;
    for (let m = 0; m <= this.elements.length; m++) {
      totalCount += this.combinationCount(m);
    }
    return totalCount;
  }

  /**
   * 生成所有子组合（长度从 1 到 n 的所有组合）
   * @returns 所有子组合的数组
   */
  allSubCombinations(): T[][] {
    const result: T[][] = [];
    for (let m = 1; m <= this.elements.length; m++) {
      result.push(...this.combinations(m));
    }
    return result;
  }
  // #endregion

  // #region 全排列与子排列方法
  /**
   * 计算全排列数 P(n,n) = n!
   * @returns 全排列数
   */
  fullPermutationCount(): number {
    return this.permutationCount(this.elements.length);
  }

  /**
   * 生成全排列（从n个元素中取n个的所有排列）
   * @returns 全排列数组
   */
  fullPermutation(): T[][] {
    return this.permutations(this.elements.length);
  }

  /**
   * 计算所有子排列的数量（长度从 1 到 n 的所有排列）
   * @returns 所有子排列的数量
   */
  allSubPermutationsCount(): number {
    let totalCount = 0;
    for (let m = 1; m <= this.elements.length; m++) {
      totalCount += this.permutationCount(m);
    }
    return totalCount;
  }

  /**
   * 生成所有子排列（长度从 1 到 n 的所有排列）
   * @returns 所有子排列的数组
   */
  allSubPermutations(): T[][] {
    const result: T[][] = [];
    for (let m = 1; m <= this.elements.length; m++) {
      result.push(...this.permutations(m));
    }
    return result;
  }
  // #endregion

  // #region 笛卡尔积计算
  /**
   * 计算多个集合的笛卡尔积
   * @param sets 要计算笛卡尔积的集合数组
   * @returns 笛卡尔积结果
   */
  static cartesianProduct<U>(...sets: U[][]): U[][] {
    if (sets.length === 0) return [[]];

    const result: U[][] = [];
    const helper = (index: number, current: U[] = []): void => {
      if (index === sets.length) {
        result.push([...current]);
        return;
      }

      for (const item of sets[index]) {
        current.push(item);
        helper(index + 1, current);
        current.pop();
      }
    };

    helper(0);
    return result;
  }
  // #endregion

  // #region 私有辅助方法
  /**
   * 辅助方法：计算阶乘
   * @param n 要计算阶乘的数
   * @returns 阶乘结果
   */
  private factorial(n: number): number {
    if (n < 0) throw new Error("Factorial not defined for negative numbers");
    if (n <= 1) return 1;

    let result = 1;
    for (let i = 2; i <= n; i++) {
      result *= i;
    }
    return result;
  }
  // #endregion
}

test.ts

const charSet = new CombinatoricsKit(['A', 'B', 'C', 'D']);

// 排列示例：从4个字符中取2个的排列
console.log("排列 P(4,2):");
console.log("理论数量:", charSet.permutationCount(2));
console.log("排列结果:", charSet.permutations(2));

// 全排列示例
console.log("\n全排列:");
console.log("理论数量:", charSet.fullPermutationCount());
console.log("全排列结果:", charSet.fullPermutation());

// 子排列示例
console.log("\n子排列:");
console.log("理论数量:", charSet.allSubPermutationsCount());
console.log("所有子排列结果:", charSet.allSubPermutations());


// 组合示例：从4个字符中取2个的组合
console.log("\n组合 C(4,2):");
console.log("理论数量:", charSet.combinationCount(2));
console.log("组合结果:", charSet.combinations(2));

// 子组合示例
console.log("\n子组合:");
console.log("理论数量:", charSet.allSubCombinationsCount());
console.log("所有子组合结果:", charSet.allSubCombinations());

// 笛卡尔积示例
console.log("\n笛卡尔积:");
const product = CombinatoricsKit.cartesianProduct(
  ['A', 'B'],
  ['1', '2'],
  ['X', 'Y']
);
console.log("理论数量:", 2 * 2 * 2); // 8
console.log("笛卡尔积结果:", product);

排列、组合、笛卡尔积、全排列总结

1. 排列（Permutation）

定义

• 从 $n$ 个不同元素中取出 $m$ 个（$m \leq n$）并按顺序排列。
• 数学公式：
  $$
  P(n, m) = \frac{n!}{(n - m)!}
  $$

特点

• 顺序敏感：[A, B] 和 [B, A] 是不同的排列。
• 元素不重复：默认每个元素仅使用一次（除非允许重复）。
• 结果数量：随 $m$ 和 $n$ 增长而爆炸式增加。

应用场景

• 密码生成：如从字符集中生成固定长度的密码（如6位数字）。
• 路径规划：旅行商问题中所有可能的路径顺序。
• 特征排序：机器学习中特征的重要性排序。

注意事项

• 若元素有重复（如 [1, 1, 2]），需去重处理。
• 大规模排列计算可能占用大量内存和时间。

2. 组合（Combination）

定义

• 从 $n$ 个不同元素中取出 $m$ 个（$m \leq n$），不考虑顺序。
• 数学公式：
  $$
  C(n, m) = \frac{n!}{m!(n - m)!}
  $$

特点

• 顺序无关：[A, B] 和 [B, A] 视为相同组合。
• 元素不重复：默认每个元素仅使用一次。
• 结果数量：比排列少，但随 $n$ 增长仍可能很大。

应用场景

• 特征选择：从多个特征中选择子集训练模型。
• 抽样分析：统计学中随机抽样（如从100人中选10人）。
• 游戏设计：如扑克牌的牌型组合。

注意事项

• 若允许重复元素（如 [A, A, B]），需使用组合数公式 $ C(n + m - 1, m) $。
• 组合数在 $m = n/2$ 时达到最大值。

3. 笛卡尔积（Cartesian Product）

定义

• 从多个集合中各取一个元素组成元组。
• 数学公式：
  若集合 $A, B, C$，其笛卡尔积为：
  $$
  A \times B \times C = {(a, b, c) \mid a \in A, b \in B, c \in C}
  $$

特点

• 跨集合组合：元素来自不同集合（如 A=[1,2], B=['a','b']）。
• 顺序敏感：(1, 'a') 和 ('a', 1) 是不同结果（若集合顺序不同）。
• 结果数量：等于各集合大小的乘积（如 $ |A| \times |B| \times |C| $）。

应用场景

• 数据库连接：多表关联查询（如 SQL 的 CROSS JOIN）。
• 参数组合测试：软件测试中生成所有参数组合。
• 网格搜索：机器学习中超参数调优。

注意事项

• 结果数量随集合数量指数级增长（如 10 个二值参数的组合数为 $ 2^{10} = 1024 $）。
• 需注意集合间的依赖关系（如某些参数组合无效）。

4. 全排列（Full Permutation）

定义

• 从 $n$ 个不同元素中取出全部 $n$ 个元素的所有排列。
• 数学公式：
  $$
  P(n, n) = n!
  $$

特点

• 顺序敏感：所有排列均考虑顺序。
• 元素不重复：每个元素恰好使用一次。
• 结果数量：增长极快（如 $10! = 3,628,800$）。

应用场景

• 密码破解：枚举所有可能的密码排列。
• 路径优化：旅行商问题中所有可能的访问顺序。
• 创意生成：从关键词中生成所有可能的语句排列。

注意事项

• 若元素有重复（如 [1, 1, 2]），需去重（如用 set 或递归剪枝）。
• 大规模全排列计算需优化算法（如回溯法剪枝）。

5. 对比总结表

维度	排列	组合	笛卡尔积	全排列	全组合
定义	有序选取 $m$ 个元素	无序选取 $m$ 个元素	跨集合选取各一个元素	有序选取全部 $n$ 个元素	无序选取全部 $n$ 个元素
公式	$ \frac{n!}{(n-m)!} $	$ \frac{n!}{m!(n-m)!} $	$	A	\times
顺序敏感	✅	❌	✅	✅	❌
元素来源	同一集合	同一集合	不同集合	同一集合	同一集合
结果数量	快速增长	比排列少	指数级增长	极快增长	1
典型场景	密码生成、路径规划	特征选择、抽样	数据库连接、参数测试	密码破解、路径优化	集合整体选择

6. 实际案例对比

案例1：密码生成

• 排列：从字符集 [A,B,C] 中生成3位密码（如 ABC, ACB, ...），共 $3! = 6$ 种。
• 组合：从字符集 [A,B,C] 中选2个字符（如 AB, AC, BC），共 $C(3,2)=3$ 种。
• 笛卡尔积：从 [A,B] 和 [1,2] 中生成组合（如 (A,1), (A,2), ...），共 $2 \times 2 = 4$ 种。
• 全排列：从 [A,B,C] 中生成所有3位密码，共 $3! = 6$ 种。