POJ 1256 Anagram：自定義字典序全排列

題目描述

給定字符串（大小寫字母），按規則 'A'<'a'<'B'<'b'...<'Z'<'z' 輸出所有不重複全排列。

解法：next_permutation + 自定義比較器

1. 定義比較函數 cmp(a,b) 實現題目規則順序。
2. 將字符串轉為字符數組，按 cmp 排序。
3. 輸出當前排列，循環調用 next_permutation(begin, end, cmp) 直到返回 false。

C++ 代碼實現

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

bool cmp(char a, char b) {
    // 同大小寫按字母序
    if (islower(a) && islower(b)) return a < b;
    if (isupper(a) && isupper(b)) return a < b;
    // 大寫在對應小寫之前
    if (isupper(a)) a += 32; // 轉小寫比較
    if (isupper(b)) b += 32;
    return a < b;
}

int main() {
    int T; scanf("%d", &T);
    char s[20];
    while (T--) {
        scanf("%s", s);
        int len = strlen(s);
        sort(s, s + len, cmp);
        do {
            printf("%s\n", s);
        } while (next_permutation(s, s + len, cmp));
    }
    return 0;
}

關鍵點

• next_permutation 接受自定義比較器（C++ 標準庫支持），直接生成按自定義序的下一排列。
• 比較器需實現嚴格弱序，本題規則滿足。
• 去重：輸入可能含重複字符，next_permutation 自動處理重複元素不生成重複排列。