全排列算法（一文看懂全排列算法）

　　全排列算法（一文看懂全排列算法）
　　所谓全排列，就是把一堆字符按照一定的顺序排列起来，所有可能的组合。
　　举个简单的例子，＂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>usingnamespacestd;stringstr;intmain{getline(cin,str);//先进行排序使之字典序最小sort(str.begin,str.end);cout<<＂其全排列为:＂<<endl;do{cout<<str<<endl;}while(next_permutation(str.begin,str.end));return0;}
　　手撕全排列
　　可是如何用编程实现这一过程呢？本文就教大家使用深搜回溯算法实现全排列。代码如下：#include<iostream>  #include<vector>#include<algorithm>usingnamespacestd;stringstr;stringtemp;vector<bool>vis;voiddfs(intcnt,intn){if(cnt==n){cout<<temp<<endl;return;}for(inti=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;}}}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中没有字符。
　　为了建立字符与下标之间的联系，方便大家观察，我们使用＂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。