【POJ 1256】Anagram 题解（全排列）

描述 你要编写一个程序，从一组给定的字母中生成所有可能的单词。 示例：给定单词“abc”，您的程序应该-通过探索这三个字母的所有不同组合-输出单词“abc”、“acb”、“bac”、“bca”、“cab”和“cba”。 在输入文件中的单词中，某些字母可能出现多次。对于给定的单词，您的程序不应多次生成相同的单词，并且单词应按字母顺序升序输出。

输入 输入由几个单词组成。第一行包含一个数字，给出要跟随的单词数。以下每行包含一个单词。单词由A到Z的大写或小写字母组成。大写字母和小写字母应视为不同。每个单词的长度小于13。 输出 对于输入中的每个单词，输出应该包含可以用给定单词的字母生成的所有不同单词。从同一输入单词生成的单词应按字母顺序升序输出。大写字母在相应的小写字母之前。

Sample Input

3 aAb abc acba

Sample Output

Aab Aba aAb abA bAa baA abc acb bac bca cab cba aabc aacb abac abca acab acba baac baca bcaa caab caba cbaa Hint

大写字母在相应的小写字母之前。 所以正确的字母顺序是“A”<“A”<“B”<“B”<…<”Z'<'Z'。 来源 1995年西南欧洲地区比赛

思路

'A'<'a'<'B'<'b'<…<'Z'<'z' 如果是同一字母的不同大小写，直接比较。如果是不同字母，则先转换为小写再比较。

AC代码

#include <iostream>
#include <algorithm>
#include <cstring>
#define AUTHOR "HEX9CF"
using namespace std;

//'A'<'a'<'B'<'b'<…<'Z'<'z'
bool cmp(char x, char y)
{
    if (tolower(x) == tolower(y))
    {
        return x < y;
    }
    else
    {
        return tolower(x) < tolower(y);
    }
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        char s[15];
        int len = 0;
        cin >> s;
        len = strlen(s);
        sort(s, s + len, cmp);
        do
        {
            cout << s << endl;
        } while (next_permutation(s, s + len, cmp));
    }
    return 0;
}