C语言数字全排列生成器

前言

从0开始记录我的学习历程，我会尽我所能，写出最最大白话的文章，希望能够帮到你，谢谢。

提示：文章作者为初学者，有问题请评论指正，感谢。

这个代码的功能是生成并打印出从1到N的所有整数的全排列，并计算总共有多少种排列方式能想出这个代码的人也是个人才。0.o

#include <stdio.h>
#define N 3
int x[N];
int count = 0;
 
void dump() {
    int i = 0;
    for (i = 0; i < N; i++) {
        printf("%d", x[i]);
    }
    printf("\n");
}
 
void swap(int a, int b) {
    int t = x[a];
    x[a] = x[b];
    x[b] = t;
}
 
void run(int n) {
    int i;
    if (N - 1 == n) {
        dump();
        count++;
        return;
    }
    for (i = n; i < N; i++) { 
        swap(n, i);
        run (n +1);
        swap(n, i);
    }
}
 
int main() {
    int i;
    for (i = 0; i < N; i++) {
        x[i] = i + 1;
    }
    run(0);
    printf("* Total: %d\n", count);
    return 0;
}

1. 全局变量定义:

   • int x[N]; 用于存储当前排列的一个数组，N为9，即数组长度为9。
   • int count = 0; 用于计数生成的全排列总数。

2. 函数dump:

   • 功能是打印当前数组x的内容，即输出一个全排列。

3. 函数swap:

   • 实现两个元素在数组x中的交换，用于在生成排列时进行元素位置的交换。

4. 函数run (关键递归函数):

   • 输入参数 n 表示当前正在处理数组中的第n+1个位置。
   • 当n等于N-1时，说明已经填到了最后一个位置，调用dump函数打印当前排列，并将计数器count++，然后返回。
   • 否则，对于数组中从位置n开始的每个元素，都尝试将其放在当前位置n上，通过swap交换元素位置，然后递归调用run(n + 1)处理下一个位置。递归调用结束后，再次交换回来，恢复数组状态，这是回溯的过程，确保尝试所有可能的排列组合。

5. 主函数main:

   • 初始化数组x，使其从1到9依次填充。
   • 调用run(0)开始递归生成全排列。
   • 最后，打印出总共生成的全排列数量，即count的值。

 当N=3时  整个代码的流程：

1. main函数:

   • n = 0，调用run(0)。

2. run(0):

   • n = 0，基准情况未满足，进入for循环。
   • 第一次迭代：i = 0。
     • 调用swap(0, 0)，数组不变，因为没有交换。
     • 调用run(1)。
       • n = 1，基准情况未满足，进入for循环。
       • 第一次迭代：i = 1。
         • 调用swap(1, 1)，数组不变，因为没有交换。
         • 调用run(2)。
           • n = 2，基准情况满足，调用dump()打印[1, 2, 3]，count++。
           • 回溯，swap(1, 1)，数组不变。
         • 第二次迭代：i = 2。
           • 调用swap(1, 2)，数组变为[1, 3, 2]。
           • 调用run(2)。
             • n = 2，基准情况满足，调用dump()打印[1, 3, 2]，count++。
             • 回溯，swap(1, 2)，数组变为[1, 2, 3]。
         • for循环结束，返回到run(1)。
       • for循环结束，返回到run(0)。
   • 第二次迭代：i = 1。
     • 调用swap(0, 1)，数组变为[2, 1, 3]。
     • 调用run(1)。
       • 与之前类似，但数组起始状态为[2, 1, 3]。
   • 第三次迭代：i = 2。
     • 调用swap(0, 2)，数组变为[3, 1, 2]。
     • 调用run(1)。
       • 与之前类似，但数组起始状态为[3, 1, 2]。
   • for循环结束，返回到run(0)。

 图解