算法基础：全排列问题

约定不等于承诺〃 2022-12-17 05:56 115阅读 0赞

全排列是常见的一种场景，对于缺乏更好技巧的时候，作为暴力破解的思路，结合深度遍历使用对初入门者非常有效，代价就是时间复杂度很高。这篇文章介绍一下使用临位对换法来解决全排列的思路和方法。

--------------------

### 文章目录 ###

*  全排列
 *  常见解法
 *  限制与说明
 *  函数定义与理解
 *  实现模拟
 *  调用示例

--------------------

# 全排列 #

>  *  排列：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。
>  *  全排列：当m=n时所有的排列叫全排列。

>  *  公式：全排列数f(n)=n! (0的全排列0!为1)

--------------------

# 常见解法 #

通常存在如下几种方法解决此此类问题，本文示例主要使用临位对换法进行模拟的实现。

*  字典序法
 *  递增进位制数法
 *  递减进位制数法
 *  邻位对换法

# 限制与说明 #

本系列基础文章基本使用c/c++进行，都会使用最为基础的方式进行模拟，只关注与算法最为核心的部分，对于输入输出的各种工程级别的校验，一般不在考虑之列，因为不希望因此让核心代码变得更加冗长，但项目中实际使用的时候要特别留意这些方面。

--------------------

# 函数定义与理解 #

> void permutaion(int\* list, int k, int n)

*  list：待排列的数组
 *  n：全排列的总的元素数目
 *  k：在数组下标从0开始的前提下，k表示list中的前k个元素（下标为0～k-1）作为前缀不变化的情况下，对于此问题进行的分解，剩余的k～n进行全排列，所以当k为0的时候，表示为list中元素的全排列n!

--------------------

# 实现模拟 #

void swap(int* x, int* y) { 
        int tmp = *x; *x = *y; *y = tmp;
    }
    
    void permutation(int *list, int k, int n) { 
        if (k == n-1) { 
            for (int i=0; i<n; i++) printf("%d ",list[i]);
            printf("\n");
            return;
        }
        for (int i=k; i<n; i++) { 
            swap(&list[k],&list[i]);
            permutation(list,k+1,n);
            swap(&list[k],&list[i]);
        }
    }

可以看到实现的要点大概只有寥寥几行，主要说明如下：

*  深度遍历：递归调用的时候事前交换，事后恢复
 *  递归调用的时候，k递增，因为全排列初始值为0，自然会增至出口条件n
 *  整个长度为n的时候（此处下标为0所以代码为n-1），为递归的出口
 *  循环的初值为k而不是0，因为0～k-1的前缀已定

--------------------

# 调用示例 #

int main() { 
        int n = 0;
        while (scanf("%d",&n) != EOF) { 
            int list[n];
            for (int i=0; i<n; i++) { 
                scanf("%d",&list[i]);
            }
            permutation(list, 0, n);
        }
    }

注意：可以看到此处使用了list\[n\]，此种用法是上个实际的C规范C99中提出的，可以使用变量进行定义数组长度，但是需要注意编译器是否支持，而且使用起来可能会有很多问题，只是简单的模拟中又可能都会用到，慎。执行结果示例如下所示：

/Users/liumiao/CLionProjects/untitled/cmake-build-debug/untitled
    3
    1 2 3
    1 2 3 
    1 3 2 
    2 1 3 
    2 3 1 
    3 2 1 
    3 1 2 
    3
    3 2 1
    3 2 1 
    3 1 2 
    2 3 1 
    2 1 3 
    1 2 3 
    1 3 2