作者 | Cooper Song
責編 | 伍杏玲
所謂全排列，就是把一堆字符按照一定的順序排列起來，所有可能的組合。
舉個簡單的例子，"123"的全排列為"123"、"132"、"213"、"231"、"312"、"321"。
1.使用庫函數進行全排列
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;
}
2.手撕全排列
可是如何用編程實現這一過程呢？本文就教大家使用深搜回溯算法實現全排列。代碼如下：
#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。
