195. Анаграмма

По заданному набору букв сгенерировать все возможные слова в алфавитном порядке. Например, из слова “abc” можно получить слова abc, acb, bac, bca, cab, cba. Буквы в слове могут повторяться.

Вход. Первая строка содержит количество тестов. Каждая следующая строка содержит слово из букв латинского алфавита (от A до Z). Буквы верхнего и нижнего регистра считать различными.

Выход. Для каждого входного теста вывести все возможные слова, которые можно получить из заданных букв, в возрастающем алфавитном порядке. Каждое слово выводить в отдельной строке. В алфавитном порядке буква верхнего регистра меньше соответствующей буквы нижнего регистра.

Пример входа

3
aAb
abc
acba

Пример выхода

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

РЕШЕНИЕ

комбинаторика, генерация перестановок

Подсказка

1. Чем отличается лексикографическая сортировка слов от алфавитной?

2. Рассмотрим строку zAZaaZ. Укажите порядок букв при их алфавитной и лексикографической сортировке.

3. При помощи какой функции STL можно реализовать генерацию перестановок всех букв в слове?

4. Функция sort по умолчанию сортирует буквы в слове в лексикографическои порядке. Как реализовать с ее помощью алфавитную сортировку?

5. Реализуйте функцию алфавитной сортировки int lt(char a, char b), которая передается в качестве третьего аргумента функции sort.

6. Как по строке s найти алфавитно наименьшую перестановку букв?

Анализ алгоритма

Сортируем символы входной строки по возрастанию. Далее используем встроенную функцию next_permutation для генерации всех перестановок. При этом следует написать собственную функцию сравнения символов. При стандартном (лексикографическом) сравнении любая буква верхнего регистра будет меньше любой буквы нижнего регистра. То есть при сортировке букв a, A, z, Z, r, R получим слово ARZarz. В задаче следует сортировать (и генерировать перестановки) в соответствии с порядком AaBbCc…Zz, необходимо из букв a, A, z, Z, r, R получить AaRrZz.

Пример

Для строки aAb (1 тест) наименьшей перестановкой будет Aab, а наибольшей baA.

Реализация алгоритма

Функция lt будет использоваться при сортировке и генерации перестановок. Она сравнивает два символа в соответствии с порядком AaBbCc…Zz.

int lt(char a, char b)

{

if (toupper(a) != toupper(b)) return (toupper(a) < toupper(b));

return (a < b);

}

Читаем входную строку, вычисляем ее длину и сортируем символы в алфавитном порядке.

scanf("%s", &s);len = strlen(s);

sort(s,s+len,lt);

Выводим текущую анаграмму (перестановку символов) и генерируем следующую до тех пор пока это возможно.

do {

printf("%s\n",s);

} while(next_permutation(s,s+len,lt));