ACM 146 ID Codes

本來想用排列組合的方式去解，
只要排到跟input相等的組合，
下一次的排列組合就是答案。
不過沒想到竟然TL了 =.=。

所以得想一個更快的方法才行：
直接排！就是最快的方式！

至於如何直接排呢？
可以參考algorithmist的方法。
主要是從右邊開始往左找，找到第一組string[y] < string[x]的情況時，
就把string[x]與string[y]對調，x~y之間的substring與x~strlen(n)間的substring
做reverse後，兩者互換即可。

證明
... y ...(1)... x ...(2)...
由s[y] < s[x]可推導出，
substring(2) <= s[y] < s[x]，
substring(1) >= s[x] > s[y]。
若要按照字母順序排列，
那下一筆資料就需比s[y]大且要在s[y]之後，
兩者之間不可有其他元素。
s[x]是唯一選擇，
所以x與y互換。
... x ...(1)... y ...(2)...
這時候(1)、y與(2)三者要排列要為最小順序，
讓x~y之間的substring <= y <= y之後的substring。
由推導出的公式可知，
substring(2) <= s[y]，
substring(1) >= s[y]，
所以substring(2)要排在y前面，
substring(1)排在y後面。
但是substring(1)與substring(2)兩者排列也要為最小順序，
所以需把(1)與(2)做reverse。

簡單講呢，就是reverse中做reverse啦。
x與y互換之後(1)y(2)變成，(2)y(1)，
(2)跟(1)再做reverse，可得
... x ...~(2)... y ...~(1)...

/* ACM 146 ID Codes
 * mythnc
 * 2012/01/08 19:16:00   
 * run time: 0.000
 */
#include <stdio.h>
#include <string.h>

#define MAXCHAR 51
#define TRUE    1
#define FALSE   0

void next(char *, int);
void reverse(char *, int, int, char *);

int main(void)
{
    char input[MAXCHAR];

    while (scanf("%s", input) && input[0] != '#')
        next(input, strlen(input));

    return 0;
}

/* next: find next permutation of s */
void next(char *s, int n)
{
    int i, j, last;
    char x, y;
    char wl[MAXCHAR], wr[MAXCHAR];

    for (i = n - 1, last = TRUE; i > 0; i--) {
        for (j = i - 1; j > -1; j--)
            if (s[j] < s[i]) {
                last = FALSE;
                break;
            }
        if (!last)
            break;
    }

    /* s is the last */
    if (last) {
        printf("No Successor\n");
        return;
    }

    wl[0] = wr[0] = '\0';
    if (i - j > 1)
        reverse(s, j, i, wl);
    if (n - i > 1)
        reverse(s, i, n, wr);

    /* output */
    x = s[i];
    y = s[j];
    s[j] = '\0';
    printf("%s%c%s%c%s\n", s, x, wr, y, wl);
}

/* reverse: reverse s from start to end.
 * save result in t */
void reverse(char *s, int start, int end, char *t)
{
    int i, j;

    for (i = end - 1, j = 0; i > start; i--, j++)
        t[j] = s[i];

    t[j] = '\0';
}