HackerRank Bigger is Greater(Algorithms>Implementation)

這應該是本部落格第一篇HackerRank Medium難度的文章XD

題目:
給定一個字(word) w, 重新排列成另一個字s,
使得s在辭典順序排列上大於w. (s lexicographically greater w)
排列方式有多個可能解，
請找出當中最小的一個。

輸入:
第一行輸入t (代表測項的數目)，
接下來的t行每行包含了一個w(也就是每行一個字)。
限制條件為
1 <= t <= 10的5次方
1 <=|w|<=100
w只會包含小寫的英文字母，且它的長度不會超過100。

輸出:
對每個測項，輸出新的排列後辭典順序比原來大的w。
如果有多種可能，則輸出辭典順序最小的解，
而如果不存在解，則印出"no answer"。


解題:
這題的目的是尋找next permutation(下一個排列)。
思路上，首先我們要先看看目前的排列是否是字典順序上最大的排列，
舉例來說，如果有一個數列如下:

0 1 2 5 3 3 0

那我們當然直覺可以講出其最大辭典排法為:

5 3 3 2 1 0 0

也就是由左至右為遞減的排列。
那麼今天我們要找下一個排列的話，
首先就要確認其是否已經是最大排列，
是的話直接表示no answer，
不是的話則可以由右至左看這樣的排序會持續到什麼地方。

0 1 2 5 3 3 0

紅字標起來的地方是完整的遞減排序，
意味著在這塊區域內任意的調換，
辭典排法的順序只有可能變小，不可能變大。

那怎麼辦呢? 想要讓字典順序變大，
那麼就拿左邊黑色區域的2來跟右邊紅色區域的換好了!
因為拿更右邊的換，位數越低，
不管怎樣換，拿越靠右邊來換辭典順序理應能更小。

那麼，跟誰換?
跟最少比2大的換，因為比2小的話，
換過來辭典順序反而會變小。

0 1 2 5 3 3 0

0 1 3 5 3 2 0

換完以後就是所有可能中的辭典順序最小的解嗎?
並非如此，因為5 3 2 0剛好是由大到小排序。
注意這邊換過以後，由於前面2和3換的方式和條件，
(從右至左，找比2大的值做交換)
換完後(2的左邊的數) >= 3 > 2 >= (2的右邊的數)
自然令換完以後的右半邊的排列還是由大到小排序。
那麼，只要令這部分的值兩兩做交換，
我們就可以得到由小到大排序的辭典順序最小的狀況了。

統整一下流程結論: (設陣列為a_0~a_n-1)
1. 若陣列長 = 0或1 => no answer
2. 令i from n-1 -> 0, 找出首個i的值使得a[i-1] < a[i]
3. 如果i為0的話，表示此排序為辭典最大 => no answer
4. 令j from a_n-1->a_i, 找出第一個j，令a[j] > a[i-1];
5. a[j] 和 a[i-1]交換
6. 將i~j之間的的所有數兩兩交換，如此升序變降序。
7. 印出新的排序，此即所有解當中的最小的辭典排序的解。

Code：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

void swap(char *x, char *y){
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
        
}

int next_permutation(char *a, size_t length){
    size_t i, j;
    if (length == 0) return 0;
    
    i = length - 1;
    while (i > 0 && a[i-1] >= a[i])
        i--;
    if (i == 0)
        return 0;
    
    // 現在保證存在一個i使得 a[i-1] < a[i], 
    // 在此之前其他的數字由左到右都是越來越小
    // 也就是本來就是排序較大的permutation,這部分換了字串不會比較大
    // 所以如果全部都是降序排列，就直接回傳0
    // 接下來再找一個j，滿足a[j]比a[i-1]大，swap過來，可以保證現在的陣列比較大
    // 且由右往回找，可以確保換的值是最小的。
    // 剩下的部分就是把原本降序排列改成升序，這樣才是比較小的排列方式。
    j = length - 1;
    while (a[j] <= a[i-1])
        j--;
    swap(&a[i-1], &a[j]);
    
    j = length - 1;
    while(i < j){
        swap(&a[i], &a[j]);
        i++;
        j--;
    }    
    return 1;
}

int main() {
    int n;    
    scanf("%d\n", &n);
    for(int i=0; i<n; i++){
        char word[100];
        scanf("%s", word);
        if (next_permutation(word, strlen(word))){
            printf("%s\n", word);
        } else {
            printf("no answer\n");
        }
    }   
    return 0;
}