使用C語言解決字符串全排列問題

2020-01-26 14:58:49

字體：大中小

來源：轉載

供稿：網友

問題
輸入一個字符串，打印出該字符串中字符的所有排列。例如輸入字符串abc，則輸出由字符a，b，c所能排列出來的所有字符串abc，acb，bac，bca，cab和cba

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

必須有可達到的終止條件，否則程序陷入死循環
子問題在規模上比原問題小
子問題可通過再次遞歸調用求解
子問題的解應能組合成整個問題的解

對于字符串的排列問題：
如果能生成n-1個元素的全排列，就能生成n個元素的全排列。對于只有一個元素的集合，可以直接生成全排列。所以全排列的遞歸終止條件很明確，只有一個元素時。我們可以分析一下全排列的過程：

首先，我們固定第一個字符a，求后面兩個字符bc的排列
當兩個字符bc排列求好之后，我們把第一個字符a和后面的b交換，得到bac，接著我們固定第一個字符b，求后面兩個字符ac的排列
現在是把c放在第一個位置的時候了，但是記住前面我們已經把原先的第一個字符a和后面的b做了交換，為了保證這次c仍是和原先處在第一個位置的a交換，我們在拿c和第一個字符交換之前，先要把b和a交換回來。在交換b和a之后，再拿c和處于第一位置的a進行交換，得到cba。我們再次固定第一個字符c，求后面兩個字符b、a的排列
既然我們已經知道怎么求三個字符的排列，那么固定第一個字符之后求后面兩個字符的排列，就是典型的遞歸思路了

下面這張圖很清楚的給出了遞歸的過程：

2015815112832632.png (805×385)

基本解決方法
方法1：依次從字符串中取出一個字符作為最終排列的第一個字符，對剩余字符組成的字符串生成全排列，最終結果為取出的字符和剩余子串全排列的組合。

#include <iostream>#include <string>using namespace std; void permute1(string prefix, string str){  if(str.length() == 0)    cout << prefix << endl;  else  {    for(int i = 0; i < str.length(); i++)      permute1(prefix+str[i], str.substr(0,i)+str.substr(i+1,str.length()));  }} void permute1(string s){  permute1("",s);} int main(){  //method1, unable to remove duplicate permutations.  cout << "method1" << endl;  permute1("ABA");}

優點：該方法易于理解，但無法移除重復的排列，如：s="ABA"，會生成兩個“AAB”。

方法2：利用交換的思想，具體見實例，但該方法不如方法1容易理解。

2015815112903993.gif (400×320)

#include <iostream>#include <string>#include <cstdio>using namespace std; void swap(char* x, char* y){  char tmp;  tmp = *x;  *x = *y;  *y = tmp;} /* Function to print permutations of string  This function takes three parameters:  1. String  2. Starting index of the string  3. Ending index of the string. */void permute(char *a, int i, int n){  int j;  if (i == n)   printf("%s/n", a);  else  {    for (j = i; j <= n; j++)    {     if(a[i] == a[j] && j != i) //為避免生成重復排列，當不同位置的字符相同時不再交換  　　   continue;     swap((a+i), (a+j));     permute(a, i+1, n);     swap((a+i), (a+j)); //backtrack    }  }}  int main(){  //method2  cout << "method2" << endl;  char a[] = "ABA";  permute(a,0,2);  return 0;}

兩種方法的生成結果：

method1ABAAABBAABAAAABABAmethod2ABAAABBAA

下面來看ACM題目實例

示例題目
題目描述

    題目描述：
    給定一個由不同的小寫字母組成的字符串，輸出這個字符串的所有全排列。
    我們假設對于小寫字母有'a' < 'b' < ... < 'y' < 'z'，而且給定的字符串中的字母已經按照從小到大的順序排列。
    輸入：
    輸入只有一行，是一個由不同的小寫字母組成的字符串，已知字符串的長度在1到6之間。
    輸出：
    輸出這個字符串的所有排列方式，每行一個排列。要求字母序比較小的排列在前面。字母序如下定義：
    已知S = s1s2...sk , T = t1t2...tk，則S < T 等價于，存在p (1 <= p <= k)，使得
    s1 = t1, s2 = t2, ..., sp - 1 = tp - 1, sp < tp成立。
    樣例輸入：
    abc
    樣例輸出：
    abc
    acb
    bac
    bca
    cab
    cba
    提示：
    每組樣例輸出結束后要再輸出一個回車。

ac代碼

 #include <stdio.h>   #include <stdlib.h>   #include <string.h>       struct seq   {     char str[7];   };       struct seq seqs[721];   int count;       void swap(char *str, int a, int b)   {     char temp;     temp = str[a];     str[a] = str[b];     str[b] = temp;   }       void permutation_process(char *name, int begin, int end) {     int k;         if (begin == end - 1) {       strcpy(seqs[count].str, name);       count ++;     }else {       for (k = begin; k < end; k ++) {         swap(name, k, begin);         permutation_process(name, begin + 1, end);         swap(name, k, begin);       }     }   }       int compare(const void *p, const void *q)   {     const char *a = p;     const char *b = q;     return strcmp(a, b);   }       int main()   {     char name[7];     int i, len;         while (scanf("%s", name) != EOF) {       count = 0;       len = strlen(name);       permutation_process(name, 0, len);       qsort(seqs, count, sizeof(seqs[0]), compare);           for (i = 0; i < count; i ++) {         printf("%s/n", seqs[i].str);       }       printf("/n");     }         return 0;   }

    /**************************************************************
        Problem: 1120
        User: wangzhengyi
        Language: C
        Result: Accepted
        Time:710 ms
        Memory:920 kb
    ****************************************************************/

去掉重復的全排列
上述代碼有個缺陷，就是會造成重復數據的輸出，例如abb這種字符串，上述程序跑完結果如圖：

2015815112950326.png (564×150)

由于全排列就是從第一個數字起，每個數分別與它后面的數字交換，我們先嘗試加個這樣的判斷――如果一個數與后面的數字相同那么這兩個數就不交換了。例如abb，第一個數與后面兩個數交換得bab，bba。然后abb中第二個數和第三個數相同，就不用交換了。但是對bab，第二個數和第三個數不同，則需要交換，得到bba。由于這里的bba和開始第一個數與第三個數交換的結果相同了，因此這個方法不行。

換種思維，對abb，第一個數a與第二個數b交換得到bab，然后考慮第一個數與第三個數交換，此時由于第三個數等于第二個數，所以第一個數就不再用與第三個數交換了。再考慮bab，它的第二個數與第三個數交換可以解決bba。此時全排列生成完畢！

這樣，我們得到在全排列中去掉重復的規則：
去重的全排列就是從第一個數字起，每個數分別與它后面非重復出現的數字交換。

貼出上面ac代碼的去重版本：

 #include <stdio.h>   #include <stdlib.h>   #include <string.h>      struct seq   {     char str[7];   };      struct seq seqs[721];   int count;      int is_swap(char *str, int begin, int k)   {     int i, flag;        for (i = begin, flag = 1; i < k; i ++) {       if (str[i] == str[k]) {         flag = 0;         break;       }     }        return flag;   }      void swap(char *str, int a, int b)   {     char temp;     temp = str[a];     str[a] = str[b];     str[b] = temp;   }      void permutation_process(char *name, int begin, int end) {     int k;        if (begin == end - 1) {       strcpy(seqs[count].str, name);       count ++;     }else {       for (k = begin; k < end; k ++) {         if (is_swap(name, begin, k)) {           swap(name, k, begin);           permutation_process(name, begin + 1, end);           swap(name, k, begin);         }       }     }   }      int compare(const void *p, const void *q)   {     const char *a = p;     const char *b = q;     return strcmp(a, b);   }      int main()   {     char name[7];     int i, len;        while (scanf("%s", name) != EOF) {       count = 0;       len = strlen(name);       permutation_process(name, 0, len);       qsort(seqs, count, sizeof(seqs[0]), compare);          for (i = 0; i < count; i ++) {         printf("%s/n", seqs[i].str);       }       printf("/n");     }        return 0;   }

上一篇：詳解約瑟夫環問題及其相關的C語言算法實現

下一篇：淺談2路插入排序算法及其簡單實現