如何计算排列组合C++

在C++中计算排列组合通常可以使用两种方法：直接计算和使用数学公式。对于直接计算，可以通过递归的方式实现排列，而对于组合，则可以通过求幂的方式实现。此外，也可以直接利用数学公式进行计算，例如nCr = n! / [r! * (n-r)!]，其中"!"表示阶乘。

1. **递归实现排列（Permutation）**：

#include <iostream>

void permute(int arr[], int l, int r, std::vector<std::vector<int>>& result) {
    if (l == r) {
        result.push_back(std::vector<int>(arr, arr + r + 1));
    } else {
        for (int i = l; i <= r; i++) {
            std::swap(arr[l], arr[i]);
            permute(arr, l + 1, r, result);
            std::swap(arr[l], arr[i]); // backtrack
        }
    }
}

std::vector<std::vector<int>> getPermutations(int arr[], int n) {
    std::vector<std::vector<int>> result;
    permute(arr, 0, n - 1, result);
    return result;
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(*arr);
    std::vector<std::vector<int>> permutations = getPermutations(arr, n);
    
    for (const auto& perm : permutations) {
        for (int num : perm) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

2. **使用数学公式计算组合（Combination）**：

#include <iostream>

long long factorial(int n) {
    long long result = 1;
    for (int i = 2; i <= n; ++i) {
        result *= i;
    }
    return result;
}

long long nCr(int n, int r) {
    return factorial(n) / (factorial(r) * factorial(n - r));
}

int main() {
    int n = 5, r = 2;
    std::cout << "Number of combinations " << n << "C" << r << " = " << nCr(n, r) << std::endl;
    return 0;
}

请注意，上述代码示例中的阶乘实现和组合的计算方法在数值较大时可能会导致溢出。在实际应用中，可以使用更大范围的数据类型如`long long`或者使用库函数（例如`boost::multiprecision`）来处理大数。