C语言实现全排列

使用方法：回溯法

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 ——百度百科

全排列回溯的基本思想：对当前位置依次进行与后面所有位置的一个交换，然后对交换后的当前位置之后的元素进行一个全排列，全排列完毕后，进行回溯：将当前位置与之前交换的位置重新调换，形成原来的排列，然后继续进行下一次交换。

比如我们想要对[1, 2, 3, 4, 5]进行排列，首先确定第一位数，可以是1， 2， 3 ， 4 ，5中任意一个，下图中我们与3进行交换，那么交换后的后四个数就是[2, 1, 4, 5]，然后对这个数组进行全排列(递归)，最后回溯之后就会回到[1, 2, 3, 4, 5]（每次排列都会回溯，所以最外层回溯的时候的排列和起初一定是一样的），接下来把4作为首位，需要排列的数就是[2, 3, 1, 5]，依次类推。

image-20210406142817183

全部代码如下：

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

void permute(int *list, int begin, int size); // 实现全排列的函数
void swap(int *a, int *b); // 交换数组中两个数的值

int num = 0; // 记录全排列的次数

int main()
{
    int n;
    int *list;
    printf("Input the size of the number list: ");
    scanf("%d", &n);
    list = (int*)calloc(n, sizeof(int)); // 动态数组
    // 初始化
    printf("Input the number list:\n");
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &list[i]);
    }

    permute(list, 0, n);

    printf("The total number of permutation is %d", num);
    free(list); // 释放
}

void permute(int *list, int begin, int size)
{
    if (begin >= size) {
        // a permutation is found
        num++;
        for (int i = 0; i < size; i++)
        {
            printf("%d ", list[i]);
        }
        printf("\n");
        return;
    }
    for (int k = begin; k < size; k++)
    {
        if (k != begin) swap(&list[begin], &list[k]);
        permute(list, begin+1, size);
        if (k != begin) swap(&list[begin], &list[k]);
    }
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}