组合数学字典序C++实现

组合数学字典序C++实现

#include <iostream>
#include <vector>

using namespace std;

// 计算组合数
long long calculateCombination(int n, int k) {
    if (k == 0 || k == n) {
        return 1;
    }

    // 使用动态规划计算组合数
    vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));
    
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= min(i, k); ++j) {
            if (j == 0 || j == i) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
    }

    return dp[n][k];
}

// 输出字典序第m个组合
void generateCombination(int n, int k, long long m) {
    for (int i = 0; i < n; ++i) {
        if (m == 0) {
            // 已经生成完毕
            break;
        }

        // 计算当前位置选择的数值
        long long count = calculateCombination(n - 1 - i, k - 1);

        // 如果当前位置选择的数值小于等于m，表示选择当前位置的数值
        if (count <= m) {
            cout << i + 1 << " ";
            --k;
            m -= count;
        }
    }

    cout << endl;
}

int main() {
    int n, k;
    long long m;

    // 输入n、k、m
    cin >> n >> k >> m;

    // 输出字典序第m个组合
    generateCombination(n, k, m);

    return 0;
}