C语言实现排列与组合算法

Luna

发布时间：2026-10-13 | 6人浏览过

原创

排列和组合是算法面试与学习中常考的递归典型案例。本文提供了一份基于C语言的完整实现代码，涵盖了从全排列到固定长度组合的具体逻辑，通过标记数组记录元素状态，利用递归回溯生成所有可能的结果。

算法核心逻辑

排列与组合的本质区别在于顺序是否重要以及选取的数量是否固定。以下代码通过两个独立的递归函数 perm 和 comb 分别处理这两种情况。

第1步：数据准备与全局变量初始化

在 main 函数执行前，需预先定义待处理的字符集及辅助数组。代码中定义了源字符数组 array，并设定了总长度 N=4 和组合选取长度 M=3。使用 flag[N] 数组作为标记位，用于在递归过程中记录当前索引对应的字符是否已被放入队列中，避免重复选取。

第2步：实现全排列算法 `perm`

排列算法的目标是从 N 个元素中无放回地选取 N 个元素并按顺序输出。递归函数 perm(s, n) 的参数 s 表示当前正在填充的位置，n 为总长度。

终止条件：当 s == n 时，说明已填满所有位置，遍历 queue 数组打印结果并返回上一层。
递归过程：遍历所有可能的索引 i，若 flag[i] == 0，则标记该位置已用，将 array[i] 填入 queue[s]，然后递归调用 perm(s+1, n)。回溯时清除标记 flag[i] = 0。

第3步：实现组合算法 `comb`

组合算法关注的是选取哪些元素，而不关心顺序，且需严格选取 M 个元素。函数 comb(s, n, m) 中 s 表示当前考虑到的源数组索引，m 为目标组合长度。

终止条件：当 top == m 时（top 记录队列中已有元素个数），说明凑齐了 M 个元素，打印队列内容并返回。
递归策略：采用“选或不选”的二分思路。
- 选：将 array[s] 加入队列，top++，递归处理下一个索引 comb(s+1, n, m)。
- 不选：递归处理下一个索引 comb(s+1, n, m)，此时 top 不变，相当于跳过了当前元素。

完整代码实现

以下是包含上述逻辑的完整 C 语言源代码，可直接编译运行：

#include <stdio.h>
#include <stdlib.h>

char array[] = "abcd";

#define N 4
#define M 3
int queue[N] = {0};
int top = 0;
int flag[N] = {0};
 
 void perm(int s, int n)
 {
   int i;
 
   if (s > n)
   {
     return;
   }
 
   if (s == n)
   {
     for (i = 0; i < n; i++)
     {
       printf("%c", queue[i]);
     }
     printf("\t");
     return ;
   }
 
   for (i = 0; i < n; i++)
   {
     if (flag[i] == 0)
     {
       flag[i] = 1;
       queue[s] = array[i];
       perm(s+1, n);
       flag[i] = 0;
     }
   }
 }
 
 void comb(int s, int n, int m)
 {
   int i;
 
   if (s > n)
     return ;
 
   if (top == m)
   {
     for (i = 0; i < m; i++)
     {
       printf("%c", queue[i]);
     }
     printf("\t");
     return ;
   }
 
   queue[top++] = array[s];
   comb(s+1, n, m);
   top--;
   comb(s+1, n, m);
 
 }
 
 int main()
 {
   printf("\nperm():\n");
   perm(0, N);
   printf("\ncombination():\n");
   comb(0, N, M);
   printf("\n");
   return 0;
 }

运行结果验证

编译并运行上述代码后，终端将输出从 'a', 'b', 'c', 'd' 四个字符中生成的全部排列和长度为3的组合。结果如下所示：

perm():
abcd  abdc  acbd  acdb  adbc  adcb  bacd  badc  bcad  bcda
bdac  bdca  cabd  cadb  cbad  cbda  cdab  cdba  dabc  dacb
dbac  dbca  dcab  dcba
combination():
abc   abd   acd   bcd

从输出结果可见，排列部分输出了24种（4!）不同顺序的组合，而组合部分仅输出了4种（C(4,3)）不考虑顺序的结果集合，符合算法预期。

以上就是C语言递归实现排列与组合算法的详细内容，更多关于C语言算法设计的资料请关注本站其它相关文章！