酷应用

一文看懂全排列算法！

百家作者：CSDN 2020-02-09 11:30:22

作者?|?Cooper Song

责编 |?伍杏玲

出品 | CSDN（ID：CSDNnews）

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

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

使用库函数进行全排列

C++的头文件中实现了全排列，即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?
#include?
using?namespace?std;
string?str;
int?main()
{
????getline(cin,str);
????//先进行排序使之字典序最小
????sort(str.begin(),str.end());
????cout<<"其全排列为:"<<endl;
????do
????{
????????cout<endl;
????}while(next_permutation(str.begin(),str.end()));
????return?0;
}

手撕全排列

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

#include?
#include?
#include?
using?namespace?std;
string?str;
string?temp;
vector<bool>?vis;
void?dfs(int?cnt,int?n)
{
????if(cnt==n)
????{
????????cout<endl;
????????return;
????}
????for(int?i=0;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}

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。

【End】

推荐阅读?

?面对疫情等群体性危机，程序员如何在家高效办公？

?特殊时期，字节跳动高效有序的远程协作办公经验，值得各企业学习！

?你离成为优秀的架构师，就差这份超全路线图了

?AAAI 2020论文解读：商汤科技提出新弱监督目标检测框架

?GitHub 标星 14000+，阿里开源的 SEATA 如何应用到极致？

?区块链创业的尴与尬

你点的每一个在看，我认真当成了喜欢

关注公众号：拾黑（shiheibook）了解更多

[广告]赞助链接：

*文章为作者独立观点，不代表爱尖刀立场

本文由 CSDN发表，转载此文章须经作者同意，并请附上出处( 爱尖刀 )及本页链接。

原文链接 https://www.ijiandao.com/2b/baijia/350547.html

图库

CSDN

关注网络尖刀微信公众号
随时掌握互联网精彩

赞助链接

百度热搜榜

排名热点搜索指数