一文看懂全排列算法

作者 | Cooper Song

责编 | 伍杏玲

所谓全排列，就是把一堆字符按照一定的顺序排列起来，所有可能的组合。

举个简单的例子，"123"的全排列为"123"、"132"、"213"、"231"、"312"、"321"。

使用库函数进行全排列

C++的<algorithm>头文件中实现了全排列，即next_permutation函数，它是基于字典序实现的，执行一次next_permutation函数就相当于进行了一次“变异”，变异之后字典序会比原来的字符串大，但其位次也仅仅排在变异之前的字符串之后。什么意思呢？比如"123"调用next_permutation函数经过一次变异之后会变成"132"，而不是"213"、"321"等字典序更大的字符串。

next_permutation是有返回值的，返回值为true或false，意思是如果变异之后仍然产生了新的排列就会返回true，不能再产生新的排列了就会返回false。还是上面那个例子，如果当前字符串已经是"321"了，不存在字典序比"321"更大的排列了，此时就会返回false。因此，如果要进行全排列的字符串是"132"，就应当先对其排序变成"123"，否则在全排列时就会漏掉"123"。

next_permutation的用法如下：

#include <iostream>
#include <algorithm>
using namespace std;
string str;
int main
{
getline(cin,str);
//先进行排序使之字典序最小
sort(str.begin,str.end);
cout<<"其全排列为:"<<endl;
do
{
cout<<str<<endl;
}while(next_permutation(str.begin,str.end));
return 0;
}

手撕全排列

可是如何用编程实现这一过程呢？本文就教大家使用深搜回溯算法实现全排列。代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
string str;
string temp;
vector<bool> vis;
void dfs(int cnt,int n)
{
if(cnt==n)
{
cout<<temp<<endl;
return;
}
for(int i=0;i<n;i++)
{
if(vis[i]==false)
{
temp.push_back(str[i]);
vis[i]=true;
dfs(cnt+1,n);
vis[i]=false;
temp.pop_back;
}
}
}
int main
{
getline(cin,str);
sort(str.begin,str.end);
int n=str.size;
vis.resize(n);
dfs(0,n);
return 0;
}

我们把产生的排练暂存在字符串temp中，当temp中的字符个数与初始字符串的字符个数相等时就将temp输出了。

数组vis存放的是字符串的某个下标索引到的字符有没有加入temp，如果加入了temp就将其vis置为true，没加入的其vis就为false。

dfs传入的参数cnt是指已经填入temp的字符个数，n是初始字符串的字符个数。

有了上面那些铺垫，我们在主函数中调用dfs(0,n)，意思是初始状态temp中没有字符。

为了建立字符与下标之间的联系，方便大家观察，我们使用"012"这个例子描述算法，最初temp={}，vis都为false，进了递归函数dfs，就开始遍历初始字符串，依次往temp填入字符。

在阅读下面的过程之前，我邀请大家关注两个要素，递归层数和当前递归层数下i的值，这两个要素直接决定了下一个要尝试填入的字符。

起初递归层数为0。从i=0开始遍历。i=0时，vis[0]=false，将0填入temp，然后将vis[0]置为true，传入cnt+1=1表示temp中已有字符的个数为1，进行下一层递归，此时

temp={0}

此时递归层数为1。从i=0开始遍历。i=0时，vis[0]=true，0已经被填入temp了不满足条件；i=1时，vis[1]=false，将1填入temp，然后将vis[1]置为true，传入cnt+1=2表示temp中已有字符的个数为2，进行下一层递归，此时

temp={0,1}

此时递归层数为2。从i=0开始遍历。i=0时，vis[0]=true，0已经被填入temp了不满足条件；i=1时，vis[1]=true，1已经被填入temp了不满足条件；i=2时，vis[2]=false，将2填入temp，然后将vis[2]置为true，传入cnt+1=3表示temp中已有字符的个数为3，进行下一层递归，此时

temp={0,1,2}

此时递归层数为3。经判断temp中已经填入了3个字符，达到了“出厂要求”，将其输出后返回上一层递归。

此时递归层数为2。上次在2层递归里遍历到i=2了，从dfs返回后取出temp末尾的字符2，于是将vis[2]又置为了false，继续遍历，i=3超出了下标范围，遍历结束，返回上一层递归。此时

temp={0,1}

此时递归层数为1。上次在1层递归里遍历到i=1了，从dfs返回后取出temp末尾的字符1，于是将vis[1]又置为了false；此时

temp={0}

继续遍历，此时i=2，vis[2]=false，将2填入temp，然后将vis[2]置为true，传入cnt+1=2表示temp中已有字符的个数为2，进行下一层递归，此时

temp={0,2}

此时递归层数为2。i=0时，vis[0]=true，0已经被填入temp了不满足条件；i=1时，vis[1]=false，将1填入temp，然后将vis[1]置为true，传入cnt+1=3表示temp中已有字符的个数为3，进行下一层递归，此时

temp={0,2,1}

此时递归层数为3。经判断temp中已经填入了3个字符，达到了“出厂要求”，将其输出后返回上一层递归。

此时递归层数为2。上次在2层递归里遍历到i=1了，从dfs返回后取出temp末尾的字符1，于是将vis[1]又置为了false。此时

temp={0,2}

继续遍历，此时i=2，vis[2]=true，2已经被填入temp了不满足条件；继续遍历，i=3超出了下标范围，遍历结束，返回上一层递归。

此时递归层数为1。上次在1层递归里遍历到i=2了，从dfs返回后取出temp末尾的字符2，于是将vis[2]又置为了false。此时

temp={0}

继续遍历，i=3超出了下标范围，遍历结束，返回上一层递归。

此时递归层数为0。上次在0层递归里遍历到i=0了，从dfs返回后取出temp末尾的字符0，于是将vis[0]又置为了false。此时

temp={}

继续遍历，此时i=1，vis[1]=false，将1填入temp，并将vis[1]置为true，传入cnt+1=1表示temp中已有字符的个数为1，进行下一层递归，此时

temp={1}

此时递归层数为1。从i=0开始遍历。i=0时，vis[0]=false，将0填入temp，然后将vis[0]置为true，传入cnt+1=2表示temp中已有字符的个数为2，进行下一层递归，此时

temp={1,0}

此时递归层数为2。从i=0开始遍历。i=0时，vis[0]=true，0已经被填入temp了不满足条件；i=1时，vis[1]=true，1已经被填入temp了不满足条件；i=2时，vis[2]=false，将2填入temp，然后将vis[2]置为true，传入cnt+1=3表示temp中已有字符的个数为3，进行下一层递归，此时

temp={1,0,2}

此时递归层数为3。经判断temp中已经填入了3个字符，达到了“出厂要求”，将其输出后返回上一层递归。

此时递归层数为2。上次在2层递归里遍历到i=2了，从dfs返回后取出temp末尾的字符2，于是将vis[2]又置为了false；继续遍历，i=3超出了下标范围，遍历结束，返回上一层递归。此时

temp={1,0}

此时递归层数为1。上次在1层递归里遍历到i=0了，从dfs返回后取出temp末尾的字符0，于是将vis[0]又置为了false；此时

temp={1}

继续遍历，此时i=1，vis[1]=true，1已经被填入temp了不满足条件；继续遍历，此时i=2，vis[2]=false，将2填入temp，然后将vis[2]置为true，传入cnt+1=2表示temp中已有字符的个数为2，进行下一层递归，此时

temp={1,2}

此时递归层数为2。从i=0开始遍历。i=0时，vis[0]=false，将0填入temp，然后将vis[0]置为true，传入cnt+1=3表示temp中已有字符的个数为3，进行下一层递归，此时

temp={1,2,0}

此时递归层数为3。经判断temp中已经填入了3个字符，达到了“出厂要求”，将其输出后返回上一层递归。

此时递归层数为2。上次在2层递归里遍历到i=0了，从dfs返回后取出temp末尾的字符，其实就是0，于是将vis[0]又置为了false；继续遍历，vis[1]和vis[2]都为true，也就是1和2都在temp里，都不满足条件，遍历结束返回上一层递归。此时

temp={1,2}

此时递归层数为1。上次在1层递归里遍历到i=2了，从dfs返回后取出temp末尾的字符2，于是将vis[2]又置为了false；此时

temp={1}

继续遍历，i=3超出了下标范围，遍历结束，返回上一层递归。此时

此时递归层数为0。上次在0层递归里遍历到i=1了，从dfs返回后取出temp末尾的字符1，于是将vis[1]又置为了false；此时

temp={}

继续遍历，此时i=2，vis[2]=false，将2填入temp，然后将vis[2]置为true，传入cnt+1=1表示temp中已有字符的个数为1，进行下一层递归，此时

temp={2}

此时递归层数为1。从i=0开始遍历。i=0时，vis[0]=false，将0填入temp，然后将vis[0]置为true，传入cnt+1=2表示temp中已有字符的个数为2，进行下一层递归，此时

temp={2,0}

此时递归层数为2。从i=0开始遍历。i=0时，vis[0]=true，0已经被填入temp了不满足条件；i=1时，vis[1]=false，将1填入temp，然后将vis[1]置为true，传入cnt+1=3表示temp中已有字符的个数为3，进行下一层递归，此时

temp={2,0,1}

此时递归层数为3。经判断temp中已经填入了3个字符，达到了“出厂要求”，将其输出后返回上一层递归。

此时递归层数为2。上次在2层递归里遍历到i=1了，从dfs返回后取出temp末尾的字符1，于是将vis[1]又置为了false；此时

temp={2,0}

继续遍历，此时i=2，vis[2]=true，2已经被填入temp了不满足条件；继续遍历，i=3超出了下标范围，遍历结束，返回上一层递归。

此时递归层数为1。上次在1层递归里遍历到i=0了，从dfs返回后取出temp末尾的字符0，于是将vis[0]又置为了false；此时

temp={2}

继续遍历，此时i=1，vis[1]=false，将1填入temp，然后将vis[1]置为true，传入cnt+1=2表示temp中已有字符的个数为2，进行下一层递归，此时

temp={2,1}

此时递归层数为2。从i=0开始遍历。i=0时，vis[0]=false，将0填入temp，然后将vis[0]置为true，传入cnt+1=3表示temp中已有字符的个数为3，进行下一层递归，此时

temp={2,1,0}

此时递归层数为3。经判断temp中已经填入了3个字符，达到了“出厂要求”，将其输出后返回上一层递归。

此时递归层数为2。上次在2层递归里遍历到i=0了，从dfs返回后取出temp末尾的字符0，于是将vis[0]又置为了false；此时

temp={2,1}

继续遍历，vis[1]和vis[2]都为true，意味着1和2都在temp里，都不满足条件，遍历结束，返回上一层递归。

此时递归层数为1。上次在1层递归里遍历到i=1了，从dfs返回后取出temp末尾的字符1，于是将vis[1]又置为了false；此时

temp={2}

继续遍历，此时i=2，vis[2]=true，2已经被填入temp了不满足条件；继续遍历，i=3超出了下标范围，遍历结束，返回上一层递归。

此时递归层数为0。上次在0层递归里遍历到i=2了，从dfs返回后取出temp末尾的字符2，于是将vis[2]又置为了false。此时

temp={}

继续遍历，i=3超出了下标范围，遍历结束。

全排列到此结束，temp和vis都恢复了最初的状态。

又到了金三银四面试季，衷心祝愿大家都能拿到想要的Offer。