趣味編程｜字符串中字符的所有排列的遞歸算法

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

輸入字符串abc，則打印出由字符串a、b、c能排列出的所有字符串abc、acb、bac、bca、cab、cba。

求整個字符串的排列，可以看成兩步。

• 第一步求所有可能出現在第一個位置的字符，即把第一個字符和後面的所有字符交換。如下圖（a）就是分別把第一個字符a和後面的b、c等字符交換的情形。
• 第二步固定第一個字符，求後面所有字符的排列。

這時我們仍然把後面的所有字符分成兩部分：後面的字符的第一個字符，以及這個字符之後的所有字符。然後把第一個字符逐一和它後面的字符交換如下圖（b）

下圖很好的解釋了上述過程：

代碼實現：

<code>void Permutation(char *pStr, char *pBegin);

void Permutation(char *pStr) {
    if (pStr == NULL)
        return;
    Permutation(pStr, pStr);
}

void Permutation(char *pStr, char *pBegin) 
{
    if (*pBegin == '\0')      // 字符串結束打印字符串
        printf("%s\n", pStr);
    else 
    {
        for (char *pCh = pBegin; *pCh != '\0'; ++pCh) // 遍歷整個字符串
        {
            char temp = *pCh; // 交換當前字符與首字符
            *pCh = *pBegin;
            *pBegin = temp;

            Permutation(pStr, pBegin + 1);

            temp = *pCh;      // 交換當前字符與首字符
            *pCh = *pBegin;
            *pBegin = temp;
        }
    }
}/<code>

pStr指向整個字符串，pBegin指向當前排列字符串的第一個字符。在每一次遞歸的時候，從pBegin向後掃描每一個字符（指針pCh指向的字符）。在交換pBegin和pCh指向的字符之後，再對pBegin後面的字符串遞歸地進行排列操作，直至pBegin指向字符串末尾

測試部分

<code>void Test(char* pStr) 
{
    if(pStr == NULL)
        printf("Test for nullptr：\n");
    else if(*pStr == '\0')
        printf("Test for nullString：\n");
    else
        printf("Test for %s:\n", pStr);

    Permutation(pStr);
    printf("\n");
}

int main(int argc, const char * argv[]) 
{
    Test(NULL);

    char string1[] = "";
    Test(string1);

    char string2[] = "a";
    Test(string2);

    char string3[] = "ab";
    Test(string3);

    char string4[] = "abc";
    Test(string4);
    getchar();
    return 0;
}/<code>

運行輸出

<code>Test for nullptr：

Test for nullString：


Test for a:
a

Test for ab:
ab
ba

Test for abc:
abc
acb
bac
bca
cba
cab/<code>

但是如果字符串中存在相同的字符，那麼應該如何處理去重呢？

去重的全排列就是從第一個數字起，每個數分別與它後面非重複出現的數字進行交換：

<code>//在[from, to]區間中是否有字符與下標為from的字符相等
bool IsSwap(char *from, char *to) {
    char* p;
    for(p = from; p < to; p++) {
        if(*p == *to)
            return false;
    }
    return true;
}

void Permutation(char *pStr, char *pBegin) {
    if (*pBegin == '\0') { // 字符串結束打印字符串
        printf("%s\n", pStr);
    } else {
        // 遍歷整個字符串
        for (char *pCh = pBegin; *pCh != '\0'; ++pCh) {
            if (IsSwap(pBegin, pCh)) {

                swap(*pCh, *pBegin);

                Permutation(pStr, pBegin + 1);

                swap(*pCh, *pBegin);
            }
        }
    }
}
/<code>

參考 《劍指offer》