字符串的全排列
題目描述：
輸入一個字符串，打印出該字符串中字符的所有排列园蝠。
例如輸入字符串a(chǎn)bc渺蒿，則輸出由字符a、b彪薛、c 所能排列出來的所有字符串：
abc茂装、acb、bac善延、bca少态、cab 和 cba。
分析和解法：
這是典型的遞歸求解問題易遣，遞歸算法有四個特性：
- 必須有可達到的終止條件彼妻，否則程序陷入死循環(huán)
- 子問題在規(guī)模上比原問題小
- 子問題可通過再次遞歸調(diào)用求解
- 子問題的解應(yīng)能組合成整個問題的解
解法一：遞歸實現(xiàn)
對于字符串的排列問題：
如果能生成n-1個元素的全排列，就能生成n個元素的全排列豆茫。對于只有一個元素的集合澳骤，可以直接生成全排列。所以全排列的遞歸終止條件很明確澜薄，只有一個元素時为肮。我們可以分析一下全排列的過程：
- 首先，我們固定第一個字符a肤京，求后面兩個字符bc的排列
- 當(dāng)兩個字符bc排列求好之后颊艳，我們把第一個字符a和后面的b交換，得到bac忘分，接著我們固定第一個字符b棋枕，求后面兩個字符ac的排列
- 現(xiàn)在是把c放在第一個位置的時候了，但是記住前面我們已經(jīng)把原先的第一個字符a和后面的b做了交換妒峦，為了保證這次c仍是和原先處在第一個位置的a交換重斑，我們在拿c和第一個字符交換之前，先要把b和a交換回來肯骇。在交換b和a之后窥浪，再拿c和處于第一位置的a進行交換，得到cba笛丙。我們再次固定第一個字符c漾脂，求后面兩個字符b、a的排列
- 既然我們已經(jīng)知道怎么求三個字符的排列胚鸯，那么固定第一個字符之后求后面兩個字符的排列骨稿，就是典型的遞歸思路了
下面這張圖很清楚的給出了遞歸的過程：
源代碼如下：
#include <iostream>
#include <cstring>
using namespace std;
void AllPermutation(char* perm, int from, int to)
{
if(from > to)
return;
if(from == to) //打印當(dāng)前排列
{
static int count = 1; //局部靜態(tài)變量，用來統(tǒng)計全排列的個數(shù)
cout << count++ << ":" << perm;
cout << endl;
}
if(from < to) //用遞歸實現(xiàn)全排列
{
for(int j = from; j <= to; j++) //第j個字符分別與它后面的字符交換就能得到新的排列
{
swap(perm[j], perm[from]);
//cout<<0;
AllPermutation(perm, from + 1, to);
//cout<<1;
swap(perm[j], perm[from]);
//cout<<2;
}
}
}
int main()
{
char str[100];
cin >> str;
AllPermutation(str, 0, strlen(str) - 1);
return 0;
}
但是如果輸入里有重復(fù)字符又該如何去掉呢？
由于全排列就是從第一個數(shù)字起坦冠，每個數(shù)分別與它后面的數(shù)字交換形耗，我們先嘗試加個這樣的判斷——如果一個數(shù)與后面的數(shù)字相同那么這兩個數(shù)就不交換了。例如abb辙浑，第一個數(shù)與后面兩個數(shù)交換得bab激涤，bba。然后abb中第二個數(shù)和第三個數(shù)相同例衍，就不用交換了。但是對bab已卸，第二個數(shù)和第三個數(shù)不同佛玄，則需要交換，得到bba累澡。由于這里的bba和開始第一個數(shù)與第三個數(shù)交換的結(jié)果相同了梦抢，因此這個方法不行。
換種思維愧哟，對abb奥吩，第一個數(shù)a與第二個數(shù)b交換得到bab，然后考慮第一個數(shù)與第三個數(shù)交換蕊梧，此時由于第三個數(shù)等于第二個數(shù)霞赫，所以第一個數(shù)就不再用與第三個數(shù)交換了。再考慮bab肥矢，它的第二個數(shù)與第三個數(shù)交換可以解決bba端衰。此時全排列生成完畢！
這樣甘改，我們得到在全排列中去掉重復(fù)的規(guī)則：
去重的全排列就是從第一個數(shù)字起旅东，每個數(shù)分別與它后面非重復(fù)出現(xiàn)的數(shù)字交換。
源代碼如下：
#include <iostream>
#include <cstring>
using namespace std;
//在[from, to]區(qū)間中是否有字符與下標(biāo)為from的字符相等
bool IsSwap(char* from, char* to)
{
char* p;
for(p = from; p < to; p++)
{
if(*p == *to)
return false;
}
return true;
}
void AllPermutation(char* perm, int from, int to)
{
if(from > to)
return;
if(from == to) //打印當(dāng)前排列
{
static int count = 1; //局部靜態(tài)變量十艾，用來統(tǒng)計全排列的個數(shù)
cout << count++ << ":" << perm;
cout << endl;
}
if(from < to) //用遞歸實現(xiàn)全排列
{
for(int j = from; j <= to; j++) //第j個字符分別與它后面的字符交換就能得到新的排列
{
if(IsSwap((perm + j), (perm + to)))
{
swap(perm[j], perm[from]);
//cout<<0;
AllPermutation(perm, from + 1, to);
//cout<<1;
swap(perm[j], perm[from]);
//cout<<2;
}
}
}
}
int main()
{
char str[100];
cin >> str;
AllPermutation(str, 0, strlen(str) - 1);
return 0;
}
分析：時間復(fù)雜度為O（n!）抵代。這個解法不難想到，但是需要注意去除重復(fù)的那塊處理忘嫉，用最后一位與前面的每個字符比較荤牍，如果相等，就不交換庆冕，否則交換参淫。
解法二：字典序排列
首先，咱們得清楚什么是字典序愧杯。根據(jù)維基百科的定義：給定兩個偏序集A和B,(a,b)和(a′,b′)屬于笛卡爾集 A × B涎才，則字典序定義為
(a,b) ≤ (a′,b′) 當(dāng)且僅當(dāng) a < a′ 或 (a = a′ 且 b ≤ b′)。
所以給定兩個字符串，逐個字符比較耍铜，那么先出現(xiàn)較小字符的那個串字典順序小邑闺，如果字符一直相等，較短的串字典順序小棕兼。例如：abc < abcd < abde < afab陡舅。
那有沒有這樣的算法，使得
- 起點： 字典序最小的排列, 1-n , 例如12345
- 終點： 字典序最大的排列伴挚，n-1, 例如54321
- 過程： 從當(dāng)前排列生成字典序剛好比它大的下一個排列
答案是肯定的：有靶衍，即是STL中的next_permutation算法。
在了解next_permutation算法是怎么一個過程之前茎芋，咱們得先來分析下“下一個排列”的性質(zhì)颅眶。
- 假定現(xiàn)有字符串(A)x(B)，它的下一個排列是：(A)y(B’)田弥，其中A涛酗、B和B’是“字符串”(可能為空），x和y是“字符”偷厦，前綴相同商叹，都是A，且一定有y > x只泼。
- 那么剖笙，為使下一個排列字典順序盡可能小，必有：
- A盡可能長
- y盡可能小
- B’里的字符按由小到大遞增排列
現(xiàn)在的問題是：找到x和y请唱。怎么找到呢枯途？咱們來看一個例子。
比如說籍滴，現(xiàn)在我們要找21543的下一個排列酪夷，我們可以從左至右逐個掃描每個數(shù)，看哪個能增大（至于如何判定能增大孽惰，是根據(jù)如果一個數(shù)右面有比它大的數(shù)存在晚岭，那么這個數(shù)就能增大），我們可以看到最后一個能增大的數(shù)是：x = 1勋功。而1應(yīng)該增大到多少坦报？1能增大到它右面比它大的那一系列數(shù)中最小的那個數(shù)，即：y = 3狂鞋，故此時21543的下一個排列應(yīng)該變?yōu)?3xxx片择，顯然 xxx(對應(yīng)之前的B’）應(yīng)由小到大排，于是我們最終找到比“21543”大骚揍，但字典順序盡量小的23145字管，找到的23145剛好比21543大啰挪。
由這個例子可以得出next_permutation算法流程為：
next_permutation算法
- 定義
- 升序：相鄰兩個位置ai < ai+1，ai 稱作該升序的首位
- 步驟（二找嘲叔、一交換亡呵、一翻轉(zhuǎn)）
- 找到排列中最后（最右）一個升序的首位位置i，x = ai
- 找到排列中第i位右邊最后一個比ai 大的位置j硫戈，y = aj
- 交換x锰什，y
- 把第(i+ 1)位到最后的部分翻轉(zhuǎn)
還是拿上面的21543舉例，那么丁逝，應(yīng)用next_permutation算法的過程如下：
- x = 1汁胆；
- y = 3
- 1和3交換，得23541
- 翻轉(zhuǎn)541霜幼，得23145
23145即為所求的21543的下一個排列嫩码。
源代碼如下：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cassert>
using namespace std;
//反轉(zhuǎn)區(qū)間
void Reverse(char* begin, char* end)
{
while(begin < end)
swap(*begin++, *end--);
}
//下一個排列
bool NextPermutation(char* str)
{
assert(str); //檢查空指針
char *p, *q, *pFind;
char *pEnd = str + strlen(str) - 1;
if(str == pEnd)
return false;
p = pEnd;
while(p != str)
{
q = p;
p--;
if(*p < *q) //找升序的相鄰兩數(shù)，前一個數(shù)即替換數(shù)
{
//從后向前找比替換點大的第一個數(shù)
pFind = pEnd;
while(*pFind <= *p)
--pFind;
swap(*p, *pFind);
//替換點后的數(shù)全部反轉(zhuǎn)
Reverse(q, pEnd);
return true;
}
}
//如果沒有找到下一個排列辛掠，全部反轉(zhuǎn)后返回false
Reverse(str, pEnd);
return false;
}
int cmp(const void *a,const void *b)
{
return int(*(char *)a - *(char *)b);
}
int main()
{
char str[100];
cin >> str;
int count = 1;
qsort(str, strlen(str), sizeof(char), cmp);
do
{
cout << count++ << ":" << str << endl;
}while(NextPermutation(str));
return 0;
}
分析： 時間復(fù)雜度為O（n!）谢谦。這個版本是可以有重復(fù)字符的释牺。
特別注意：
- 一定要注意邊界條件和判斷條件萝衩，到底是 > 還是 >= ，會影響結(jié)果没咙。
參考資料：《編程之法》The Art of Programming By July
字符串的全排列和組合算法
