Problem 146 ID Codes，識別碼

此題需要將輸入字串依照字串排序，印出它下一次會出現的字串排序。

舉個例子，對於abc字串的排序一共有六種，分別是：
abc
acb
bac
bca
cab
cba
當我輸入 cab 時，需要輸出 cba，也就是它下一次會出現的字串排序，可當我輸入 cba 時，因為它已是排序結尾，所以要輸出 No Successor。

對於這一題 C++ 可以使用 Algorithm 的 next_permutation() 方能輕易解出，可我們網站標榜「C的解題」，總不能掛羊頭賣狗肉吧！所以我又上網找了一些關於這題的演算法，因此寫出以下函式：

#define MAXLEN 60

char str[MAXLEN];

void swap(int i, int j)
{
     char tmp;
     tmp = str[i];
     str[i] = str[j];
     str[j] = tmp;
} 

int next_permutation()
{
    int i, j, k;
    int length;
    length = strlen(str);
    for(i = length - 1;i > 0 ; --i)
        if(str[i-1] < str[i]) break;
    j = i;
    if(j == 0) return 0;
    for(i = length - 1;i > 0; --i)
        if(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;
}

以上程式碼參考來源

以上函式可以方便找到下一次出現的字串排序，再接著只需判斷它是否有下一次的字串，將它印出即可。
By David.K

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