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

　　全排列算法（一文看懂全排列算法）
　　所谓全排列，就是把一堆字符按照一定的顺序排列起来，所有可能的组合。
　　举个简单的例子，123的全排列为123、132、213、231、312、321。
　　使用库函数进行全排列
　　C的lt；algorithmgt；头文件中实现了全排列，即nextpermutation函数，它是基于字典序实现的，执行一次nextpermutation函数就相当于进行了一次变异，变异之后字典序会比原来的字符串大，但其位次也仅仅排在变异之前的字符串之后。什么意思呢？比如123调用nextpermutation函数经过一次变异之后会变成132，而不是213、321等字典序更大的字符串。
　　nextpermutation是有返回值的，返回值为true或false，意思是如果变异之后仍然产生了新的排列就会返回true，不能再产生新的排列了就会返回false。还是上面那个例子，如果当前字符串已经是321了，不存在字典序比321更大的排列了，此时就会返回false。因此，如果要进行全排列的字符串是132，就应当先对其排序变成123，否则在全排列时就会漏掉123。
　　nextpermutation的用法如下：includelt；iostreamgt；includelt；algorithmgt；usingnamespacestd；stringstr；intmain｛getline（cin，str）；先进行排序使之字典序最小sort（str。begin，str。end）；coutlt；lt；其全排列为：lt；lt；endl；do｛coutlt；lt；strlt；lt；endl；｝while（nextpermutation（str。begin，str。end））；return0；｝
　　手撕全排列
　　可是如何用编程实现这一过程呢？本文就教大家使用深搜回溯算法实现全排列。代码如下：includelt；iostreamgt；includelt；vectorgt；includelt；algorithmgt；usingnamespacestd；stringstr；stringtemp；vectorlt；boolgt；vis；voiddfs（intcnt，intn）｛if（cntn）｛coutlt；lt；templt；lt；endl；return；｝for（inti0；ilt；n；i）｛if（vis〔i〕false）｛temp。pushback（str〔i〕）；vis〔i〕true；dfs（cnt1，n）；vis〔i〕false；temp。popback；｝｝｝intmain｛getline（cin，str）；sort（str。begin，str。end）；intnstr。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。从i0开始遍历。i0时，vis〔0〕false，将0填入temp，然后将vis〔0〕置为true，传入cnt11表示temp中已有字符的个数为1，进行下一层递归，此时
　　temp｛0｝
　　此时递归层数为1。从i0开始遍历。i0时，vis〔0〕true，0已经被填入temp了不满足条件；i1时，vis〔1〕false，将1填入temp，然后将vis〔1〕置为true，传入cnt12表示temp中已有字符的个数为2，进行下一层递归，此时
　　temp｛0，1｝
　　此时递归层数为2。从i0开始遍历。i0时，vis〔0〕true，0已经被填入temp了不满足条件；i1时，vis〔1〕true，1已经被填入temp了不满足条件；i2时，vis〔2〕false，将2填入temp，然后将vis〔2〕置为true，传入cnt13表示temp中已有字符的个数为3，进行下一层递归，此时
　　temp｛0，1，2｝
　　此时递归层数为3。经判断temp中已经填入了3个字符，达到了出厂要求，将其输出后返回上一层递归。
　　此时递归层数为2。上次在2层递归里遍历到i2了，从dfs返回后取出temp末尾的字符2，于是将vis〔2〕又置为了false，继续遍历，i3超出了下标范围，遍历结束，返回上一层递归。此时
　　temp｛0，1｝
　　此时递归层数为1。上次在1层递归里遍历到i1了，从dfs返回后取出temp末尾的字符1，于是将vis〔1〕又置为了false；此时
　　temp｛0｝
　　继续遍历，此时i2，vis〔2〕false，将2填入temp，然后将vis〔2〕置为true，传入cnt12表示temp中已有字符的个数为2，进行下一层递归，此时
　　temp｛0，2｝
　　此时递归层数为2。i0时，vis〔0〕true，0已经被填入temp了不满足条件；i1时，vis〔1〕false，将1填入temp，然后将vis〔1〕置为true，传入cnt13表示temp中已有字符的个数为3，进行下一层递归，此时
　　temp｛0，2，1｝
　　此时递归层数为3。经判断temp中已经填入了3个字符，达到了出厂要求，将其输出后返回上一层递归。
　　此时递归层数为2。上次在2层递归里遍历到i1了，从dfs返回后取出temp末尾的字符1，于是将vis〔1〕又置为了false。此时
　　temp｛0，2｝
　　继续遍历，此时i2，vis〔2〕true，2已经被填入temp了不满足条件；继续遍历，i3超出了下标范围，遍历结束，返回上一层递归。
　　此时递归层数为1。上次在1层递归里遍历到i2了，从dfs返回后取出temp末尾的字符2，于是将vis〔2〕又置为了false。此时
　　temp｛0｝
　　继续遍历，i3超出了下标范围，遍历结束，返回上一层递归。
　　此时递归层数为0。上次在0层递归里遍历到i0了，从dfs返回后取出temp末尾的字符0，于是将vis〔0〕又置为了false。此时
　　temp｛｝
　　继续遍历，此时i1，vis〔1〕false，将1填入temp，并将vis〔1〕置为true，传入cnt11表示temp中已有字符的个数为1，进行下一层递归，此时
　　temp｛1｝
　　此时递归层数为1。从i0开始遍历。i0时，vis〔0〕false，将0填入temp，然后将vis〔0〕置为true，传入cnt12表示temp中已有字符的个数为2，进行下一层递归，此时
　　temp｛1，0｝
　　此时递归层数为2。从i0开始遍历。i0时，vis〔0〕true，0已经被填入temp了不满足条件；i1时，vis〔1〕true，1已经被填入temp了不满足条件；i2时，vis〔2〕false，将2填入temp，然后将vis〔2〕置为true，传入cnt13表示temp中已有字符的个数为3，进行下一层递归，此时
　　temp｛1，0，2｝
　　此时递归层数为3。经判断temp中已经填入了3个字符，达到了出厂要求，将其输出后返回上一层递归。
　　此时递归层数为2。上次在2层递归里遍历到i2了，从dfs返回后取出temp末尾的字符2，于是将vis〔2〕又置为了false；继续遍历，i3超出了下标范围，遍历结束，返回上一层递归。此时
　　temp｛1，0｝
　　此时递归层数为1。上次在1层递归里遍历到i0了，从dfs返回后取出temp末尾的字符0，于是将vis〔0〕又置为了false；此时
　　temp｛1｝
　　继续遍历，此时i1，vis〔1〕true，1已经被填入temp了不满足条件；继续遍历，此时i2，vis〔2〕false，将2填入temp，然后将vis〔2〕置为true，传入cnt12表示temp中已有字符的个数为2，进行下一层递归，此时
　　temp｛1，2｝
　　此时递归层数为2。从i0开始遍历。i0时，vis〔0〕false，将0填入temp，然后将vis〔0〕置为true，传入cnt13表示temp中已有字符的个数为3，进行下一层递归，此时
　　temp｛1，2，0｝
　　此时递归层数为3。经判断temp中已经填入了3个字符，达到了出厂要求，将其输出后返回上一层递归。
　　此时递归层数为2。上次在2层递归里遍历到i0了，从dfs返回后取出temp末尾的字符，其实就是0，于是将vis〔0〕又置为了false；继续遍历，vis〔1〕和vis〔2〕都为true，也就是1和2都在temp里，都不满足条件，遍历结束返回上一层递归。此时
　　temp｛1，2｝
　　此时递归层数为1。上次在1层递归里遍历到i2了，从dfs返回后取出temp末尾的字符2，于是将vis〔2〕又置为了false；此时
　　temp｛1｝
　　继续遍历，i3超出了下标范围，遍历结束，返回上一层递归。此时
　　此时递归层数为0。上次在0层递归里遍历到i1了，从dfs返回后取出temp末尾的字符1，于是将vis〔1〕又置为了false；此时
　　temp｛｝
　　继续遍历，此时i2，vis〔2〕false，将2填入temp，然后将vis〔2〕置为true，传入cnt11表示temp中已有字符的个数为1，进行下一层递归，此时
　　temp｛2｝
　　此时递归层数为1。从i0开始遍历。i0时，vis〔0〕false，将0填入temp，然后将vis〔0〕置为true，传入cnt12表示temp中已有字符的个数为2，进行下一层递归，此时
　　temp｛2，0｝
　　此时递归层数为2。从i0开始遍历。i0时，vis〔0〕true，0已经被填入temp了不满足条件；i1时，vis〔1〕false，将1填入temp，然后将vis〔1〕置为true，传入cnt13表示temp中已有字符的个数为3，进行下一层递归，此时
　　temp｛2，0，1｝
　　此时递归层数为3。经判断temp中已经填入了3个字符，达到了出厂要求，将其输出后返回上一层递归。
　　此时递归层数为2。上次在2层递归里遍历到i1了，从dfs返回后取出temp末尾的字符1，于是将vis〔1〕又置为了false；此时
　　temp｛2，0｝
　　继续遍历，此时i2，vis〔2〕true，2已经被填入temp了不满足条件；继续遍历，i3超出了下标范围，遍历结束，返回上一层递归。
　　此时递归层数为1。上次在1层递归里遍历到i0了，从dfs返回后取出temp末尾的字符0，于是将vis〔0〕又置为了false；此时
　　temp｛2｝
　　继续遍历，此时i1，vis〔1〕false，将1填入temp，然后将vis〔1〕置为true，传入cnt12表示temp中已有字符的个数为2，进行下一层递归，此时
　　temp｛2，1｝
　　此时递归层数为2。从i0开始遍历。i0时，vis〔0〕false，将0填入temp，然后将vis〔0〕置为true，传入cnt13表示temp中已有字符的个数为3，进行下一层递归，此时
　　temp｛2，1，0｝
　　此时递归层数为3。经判断temp中已经填入了3个字符，达到了出厂要求，将其输出后返回上一层递归。
　　此时递归层数为2。上次在2层递归里遍历到i0了，从dfs返回后取出temp末尾的字符0，于是将vis〔0〕又置为了false；此时
　　temp｛2，1｝
　　继续遍历，vis〔1〕和vis〔2〕都为true，意味着1和2都在temp里，都不满足条件，遍历结束，返回上一层递归。
　　此时递归层数为1。上次在1层递归里遍历到i1了，从dfs返回后取出temp末尾的字符1，于是将vis〔1〕又置为了false；此时
　　temp｛2｝
　　继续遍历，此时i2，vis〔2〕true，2已经被填入temp了不满足条件；继续遍历，i3超出了下标范围，遍历结束，返回上一层递归。
　　此时递归层数为0。上次在0层递归里遍历到i2了，从dfs返回后取出temp末尾的字符2，于是将vis〔2〕又置为了false。此时
　　temp｛｝
　　继续遍历，i3超出了下标范围，遍历结束。
　　全排列到此结束，temp和vis都恢复了最初的状态。
　　又到了金三银四面试季，衷心祝愿大家都能拿到想要的Offer。