c++中如何计算组合数C(n,m)_c++求排列组合方法汇总_技术教程

应避免用std::tgamma或阶乘公式直接计算大数组合数，而采用迭代乘除法控制中间值；unsigned long long可安全计算至C(67,33)，超限需用boost::multiprecision::cpp_int等高精度方案。

直接用 `std::tgamma` 计算大数 C(n, m) 容易精度丢失

当 n 超过 20 左右，用阶乘公式 C(n,m) = n! / (m! * (n-m)!) 直接算 double 或 long double 会迅速溢出或失真。比如 std::tgamma(n+1) 在 n=171 就返回 inf（超出 double 表示范围）。更糟的是，中间结果远大于最终结果，导致有效数字被截断。

实际应避免全阶乘：改用迭代乘除，边乘边除，控制中间值在合理范围内。

从 max(m, n-m) 开始向上累乘分子，向下累除分母，减少迭代次数
用 unsigned long long 可安全算到 C(67, 33) ≈ 1.4e19（接近 ULLONG_MAX）
超过这个范围必须上高精度（如 boost::multiprecision::cpp_int 或手写数组）

用 `unsigned long long` 迭代实现安全整数版 `C(n,m)`

这是最常用、零依赖、兼顾速度与可读性的方案。核心是把组合数拆成连乘积：C(n,m) = ∏_{i=1}^m (n - m + i) / i，并保证每一步除法整除（数学上成立）。

unsigned long long comb(unsigned n, unsigned m) {
    if (m > n) return 0;
    if (m > n - m) m = n - m; // 利用对称性减少循环
    unsigned long long res = 1;
    for (unsigned i = 0; i < m; ++i) {
        res = res * (n - i) / (i + 1); // 先乘后除，整除成立
    }
    return res;
}

注意：res * (n - i) 这一步仍可能溢出——所以务必在 n 较大时加溢出检查，或改用 __builtin_mul_overflow（GCC/Clang）。

需要支持 `n > 67`？用 `boost::multiprecision::cpp_int`

标准库不提供大整数，但 boost::multiprecision 是事实上的补充。它支持任意精度整数，且语法几乎和原生类型一致，适合科学计算或算法验证场景。

需链接 -lboost_system（部分平台），头文件为：

#include 
using namespace boost::multiprecision;
cpp_int comb_big(unsigned n, unsigned m) {
    if (m > n) return 0;
    if (m > n - m) m = n - m;
    cpp_int res = 1;
    for (unsigned i = 0; i < m; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}

性能比 ULLONG_MAX 版慢 10–100 倍，但换来的是完全无溢出风险。调试时可直接 std::cout 打印完整十进制结果。

`std::next_permutation` 和 `std::next_combination` 不是标准库函数

很多人搜“C++ 排列组合库函数”，误以为有类似 std::next_combination 的东西。实际上只有 std::next_permutation（用于生*排列），而组合没有对应标准函数。

若需枚举所有大小为 m 的子集（即所有组合），常见做法是：

用 std::vector mask(n, false)，设前 m 位为 true，再用 std::next_permutation(mask.begin(), mask.end()) 枚举所有掩码
每次循环中，遍历 mask 收集下标，构造一个组合
注意：该方法时间复杂度 O(C(n,m) × n)，仅适用于 n ≤ 30 且 m 不极端的情况