作者 | Cooper Song

責編 | 伍杏玲

所謂全排列，就是把一堆字符按照一定的順序排列起來，所有可能的組合。

舉個簡單的例子，"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>

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;

}

手撕全排列

可是如何用編程實現這一過程呢？本文就教大家使用深搜回溯算法實現全排列。代碼如下：

#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。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!