当前位置：首页 > C > 正文

C语言组合数学算法（从零开始掌握排列组合的编程实现）

主机测评网
C
2025-12-12
353

在计算机科学和算法竞赛中，C语言组合数学算法是一个非常基础又重要的主题。无论是解决密码学问题、概率计算，还是进行数据采样，组合与排列都是核心工具。本文将用通俗易懂的方式，带你从零开始理解并用 C 语言实现常见的组合数学算法。

什么是组合与排列？

- 排列（Permutation）：从 n 个不同元素中取出 m 个元素，按照一定顺序排成一列。例如：从 {A, B, C} 中选 2 个排列，有 AB、BA、AC、CA、BC、CB 共 6 种。

- 组合（Combination）：从 n 个不同元素中取出 m 个元素，不考虑顺序。例如：从 {A, B, C} 中选 2 个组合，只有 AB、AC、BC 共 3 种。

C语言组合数学算法（从零开始掌握排列组合的编程实现） C语言组合数学算法排列组合C语言实现递归生成组合 C语言回溯算法第1张

1. 计算组合数 C(n, k)

组合数公式为：

C(n, k) = n! / (k! × (n - k)!)

但直接计算阶乘容易溢出，我们可以使用递推关系优化：

#include <stdio.h>// 使用动态规划计算组合数 C(n, k)long long combination(int n, int k) {    if (k > n - k) k = n - k; // 利用对称性减少计算    long long res = 1;    for (int i = 0; i < k; i++) {        res = res * (n - i) / (i + 1);    }    return res;}int main() {    int n = 5, k = 2;    printf("C(%d, %d) = %lld\n", n, k, combination(n, k));    return 0;}

这段代码避免了大数阶乘，通过逐项相乘除来保持中间结果较小，非常适合初学者理解和使用。这也是排列组合C语言实现中最常用的方法之一。

2. 递归生成所有组合

有时我们不仅需要知道组合数量，还需要列出所有可能的组合。这时可以使用递归生成组合的方法。

#include <stdio.h>void generate_combinations(int n, int k, int start, int current[], int index) {    // 如果已经选够 k 个元素，输出当前组合    if (index == k) {        for (int i = 0; i < k; i++) {            printf("%d ", current[i]);        }        printf("\n");        return;    }    // 从 start 开始尝试每个数字    for (int i = start; i <= n; i++) {        current[index] = i;        generate_combinations(n, k, i + 1, current, index + 1);    }}int main() {    int n = 4, k = 2;    int current[10]; // 假设 k 不超过 10    printf("所有从 1 到 %d 中选 %d 个数的组合：\n", n, k);    generate_combinations(n, k, 1, current, 0);    return 0;}

这个程序会输出：

1 21 31 42 32 43 4

3. 使用回溯法生成排列

排列要求顺序不同即视为不同结果，因此我们需要记录哪些元素已被使用。这正是C语言回溯算法的经典应用场景。

#include <stdio.h>#include <stdbool.h>void permute(int arr[], int n, bool used[], int current[], int index) {    if (index == n) {        for (int i = 0; i < n; i++) {            printf("%d ", current[i]);        }        printf("\n");        return;    }    for (int i = 0; i < n; i++) {        if (!used[i]) {            used[i] = true;            current[index] = arr[i];            permute(arr, n, used, current, index + 1);            used[i] = false; // 回溯        }    }}int main() {    int arr[] = {1, 2, 3};    int n = sizeof(arr) / sizeof(arr[0]);    bool used[n];    int current[n];    for (int i = 0; i < n; i++) used[i] = false;    printf("数组 {1, 2, 3} 的所有排列：\n");    permute(arr, n, used, current, 0);    return 0;}