作者
CooperSong
责编
伍杏玲
所谓全排列，就是把一堆字符按照一定的顺序排列起来，所有可能的组合。
举个简单的例子，的全排列为、、、、、。
使用库函数进行全排列
C++的algorithm头文件中实现了全排列，即next_permutation函数，它是基于字典序实现的，执行一次next_permutation函数就相当于进行了一次“变异”，变异之后字典序会比原来的字符串大，但其位次也仅仅排在变异之前的字符串之后。什么意思呢？比如调用next_permutation函数经过一次变异之后会变成，而不是、等字典序更大的字符串。
next_permutation是有返回值的，返回值为true或false，意思是如果变异之后仍然产生了新的排列就会返回true，不能再产生新的排列了就会返回false。还是上面那个例子，如果当前字符串已经是了，不存在字典序比更大的排列了，此时就会返回false。因此，如果要进行全排列的字符串是，就应当先对其排序变成，否则在全排列时就会漏掉。
next_permutation的用法如下：
#includeiostream#includealgorithmusingnamespacestd;stringstr;intmain(){getline(cin,str);//先进行排序使之字典序最小sort(str.begin(),str.end());cout其全排列为:endl;do{coutstrendl;}while(next_permutation(str.begin(),str.end()));return0;}
手撕全排列
可是如何用编程实现这一过程呢？本文就教大家使用深搜回溯算法实现全排列。代码如下：
#includeiostream#includevector#includealgorithmusingnamespacestd;stringstr;stringtemp;vectorboolvis;voiddfs(intcnt,intn){if(cnt==n){couttempendl;return;}for(inti=0;in;i++){if(vis==false){temp.push_back(str);vis=true;dfs(cnt+1,n);vis=false;temp.pop_back();}}}intmain(){getline(cin,str);sort(str.begin(),str.end());intn=str.size();vis.resize(n);dfs(0,n);return0;}
我们把产生的排练暂存在字符串temp中，当temp中的字符个数与初始字符串的字符个数相等时就将temp输出了。
数组vis存放的是字符串的某个下标索引到的字符有没有加入temp，如果加入了temp就将其vis置为true，没加入的其vis就为false。
dfs传入的参数cnt是指已经填入temp的字符个数，n是初始字符串的字符个数。
有了上面那些铺垫，我们在主函数中调用dfs(0,n)，意思是初始状态temp中没有字符。
为了建立字符与下标之间的联系，方便大家观察，我们使用这个例子描述算法，最初temp={}，vis都为false，进了递归函数dfs，就开始遍历初始字符串，依次往temp填入字符。
在阅读下面的过程之前，我邀请大家