ACM 10098 Generating Fast

排列組合之排列的標準題型。
我覺得還滿難的……
由於要按照字母排列順序輸出，且重複字母需列入考慮，
不是只是輸出所有情況而已……

使用backtracking的方法解題。
感覺是dfs的變形體，把每個字母當成一個節點看待。
每次都取其中一個節點，接著遞迴取第二個節點，直到每個節點皆取畢為止。

所以其實要做的很簡單……就是做從節點1到節點n，每個點都去做dfs。
光是紀錄是否已經走訪已經可以排出非重複字母的所有排列情況。
現在在把重複的情況納入考慮。
一個偷吃步的方法，就是對原本的string做sort，
sort後的string會依照大小順序排列。
如此，每當遇到一個重複的情況，就去對比原本存在output上的值是否相等，
若相等，表示重複，就跳過，不做dfs。
用講的感覺很抽象，直接舉實例：
若input為abcdc，先做sort後為：abccd。
假設5個節點為a b c1 c2 d，
按照順序，從a開始對每個節點遞迴做dfs。
a -> b -> c1 -> c2 -> d，這是第一次。
a -> b -> c1 -> c2 -> 沒點了，back，
a -> b -> c1 -> d -> c2，第二次，
a -> b -> c1 -> d -> 沒點了，back，
a -> b -> 這時候按照順序應該要取c2，但是c1跟c2兩個節點的內容都是c，
所以就不取，跳過c2，取d。

所以這就是為什麼要先做sort的原因，因為按照順序排列，
可以確定接下來要取的點是否與上一點重複。
如果沒有先sort，那是無法判別重複的（以此方法而言）。

或許還有其他更好的方法……歡迎提供。
筆者才疏學淺，一個方法都沒想到……
（沒錯，這個方法也是我在網路上看到的，世界真是充滿一堆神人 + 神碼）

/* ACM 10098 Generating Fast
 * mythnc
 * 2012/01/08 22:17:54
 * run time: 0.108
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXCHAR 11
#define TRUE    1
#define FALSE   0

void backtrack(int);
int cmp(const void *a, const void *b);

char input[MAXCHAR], output[MAXCHAR];
int visited[MAXCHAR];

int main(void)
{
    scanf("%*d");
    while (scanf("%s", &input) == 1) {
        qsort(input, strlen(input), sizeof(char), cmp);
        backtrack(0);
        putchar('\n');
    }

    return 0;
}

/* backtrack: do backtrack to producing answer */
void backtrack(int i)
{
    int j;

    /* output */
    if (input[i] == '\0') {
        output[i] = '\0';
        printf("%s\n", output);
        return;
    }
    /* clear the previous content in output[i] */
    output[i] = -1;
    for (j = 0; input[j] != '\0'; j++)
        if (!visited[j] && input[j] != output[i]) {
            visited[j] = TRUE;
            output[i] = input[j];
            backtrack(i + 1);
            visited[j] = FALSE;
        }
}

/* cmp: for qsort() */
int cmp(const void *a, const void *b)
{
    return *(char *)a - *(char *)b;
}