字符串的全排列

題目描述：

輸入一個字符串，打印出該字符串中字符的所有排列。

例如輸入字符串a(chǎn)bc，則輸出由字符a、b、c 所能排列出來的所有字符串：
abc、acb、bac、bca、cab 和 cba。

分析和解法：

這是典型的遞歸求解問題，遞歸算法有四個特性：

必須有可達(dá)到的終止條件，否則程序陷入死循環(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進(jìn)行交換，得到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
字符串的全排列和組合算法

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

字符串的全排列