Problem 195 Anagram，排列組合

此題只須將字串所有可能的排序，由小到大排列出來。

首先，宣告一個陣列，並建構一函式比較字元大小：

#define MAXLEN 35

char str[MAXLEN];
char compStr[] = {'A','a','B','b','C','c','D','d','E','e','F','f','G','g','H','h','I','i','J','j'
,'K','k','L','l','M','m','N','n','O','o','P','p','Q','q','R','r','S','s','T','t'
                 ,'U','u','V','v','W','w','X','x','Y','y','Z','z'};

int comp(char ch1, char ch2)
{
    int i, ch1i, ch2i;
    for (i = 0; i < strlen(compStr); i ++)
        if (ch1 == compStr[i]) ch1i = i;
    for (i = 0; i < strlen(compStr); i ++)
        if (ch2 == compStr[i]) ch2i = i;
    if (ch1i < ch2i) return 1;
    else return 0;    
}

再使用Problem 146上函式判斷是否有下一次的字串排序，一直判斷到底即可。但重點是你須將輸入字串做排序：

void sort()
{
    int i, j;
    char ch;
    for (i = strlen(str) - 1; i >= 0; i--)
        for (j = 0; j < strlen(str); j++)
            if (comp(str[strlen(str) - j - 1], str[i]) )
               ch = str[strlen(str) - j - 1], 
               str[strlen(str) - j - 1] = str[i], str[i] = ch; 
}

再將排序函式稍做修改：

int next_permutation()
{
    int i, j, k;
    int length;
    length = strlen(str);
    for(i = length - 1;i > 0 ; --i)
        if(comp(str[i-1], str[i])) break;
    j = i;
    if(j == 0) return 0;
    for(i = length - 1;i > 0; --i)
        if(comp(str[j-1], str[i])) break;
    k = i;
    swap(j-1, k);
    for(i = j, j = length - 1;i < j; ++i, --j)
        swap(i, j);
    return 1;
}

而主程式只須用一無窮迴圈印出即可：

int n, i;
scanf("%d", &n);
getchar();
for (i = 0; i < n; i ++)
{
    gets(str);
    sort();
    printf("%s\n", str);
    while (next_permutation())
        printf("%s\n", str);
             
}

By David.K

p195題目連結
回ACM題庫目錄
回首頁