趣味编程|字符串中字符的所有排列的递归算法

要求输入一个字符串，打印出该字符串中字符的所有排列。

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

求整个字符串的排列，可以看成两步。

• 第一步求所有可能出现在第一个位置的字符，即把第一个字符和后面的所有字符交换。如下图（a）就是分别把第一个字符a和后面的b、c等字符交换的情形。
• 第二步固定第一个字符，求后面所有字符的排列。

这时我们仍然把后面的所有字符分成两部分：后面的字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换如下图（b）

下图很好的解释了上述过程：

代码实现：

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;
        }
    }
}

pStr指向整个字符串，pBegin指向当前排列字符串的第一个字符。在每一次递归的时候，从pBegin向后扫描每一个字符（指针pCh指向的字符）。在交换pBegin和pCh指向的字符之后，再对pBegin后面的字符串递归地进行排列操作，直至pBegin指向字符串末尾

测试部分

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;
}

运行输出

Test for nullptr：

Test for nullString：


Test for a:
a

Test for ab:
ab
ba

Test for abc:
abc
acb
bac
bca
cba
cab

但是如果字符串中存在相同的字符，那么应该如何处理去重呢？

去重的全排列就是从第一个数字起，每个数分别与它后面非重复出现的数字进行交换：

//在[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);
            }
        }
    }
}

参考 《剑指offer》