只要排到跟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'; }
沒有留言:
張貼留言