Write a program
that generates all possible words from a given set of letters.
For example,
from the word
“abc”, all possible
permutations of the letters are: “abc”, “acb”, “bac”, “bca”, “cab”, and “cba”.
The input words
may contain duplicate letters. The program must avoid printing the same word
more than once. All words should be printed in ascending alphabetical order.
Input. The first line
contains the number of test cases. Each of the following lines contains one
word consisting of Latin letters (from A to Z).
Uppercase and lowercase letters are treated as distinct.
Output. For each test
case, print all unique words that can be formed from the given letters in
ascending order. Each word should be printed on a separate line. In
alphabetical order, uppercase letters are considered smaller than their
lowercase counterparts.
|
Sample
input |
Sample
output |
3aAbabc
acba |
AabAbaaAbabAbAabaAabcacbbacbcacabcbaaabcaacbabacabcaacabacbabaacbacabcaacaabcaba
cbaa |
combinatorics - permutations
Exercise
1. What is the difference between lexicographical
sorting and alphabetical sorting of words?
2. Consider the string “zAZaaZ”.
Specify the order of the letters in alphabetical and lexicographical sorting.
3. Which STL function can be used to
generate all permutations of the letters in a word?
4. The sort function by default
sorts the letters of a word in lexicographical order. How can it be used to
perform alphabetical sorting?
5. Implement a function for alphabetical
sorting, int lt(char a, char b), which will be
passed as the third argument to the sort function.
6. How can you find the alphabetically
smallest permutation of the letters in a string s?
Sort the
characters of the input string in ascending order according to alphabetical
order. Then, use the built-in next_permutation function to
generate all permutations.
Since the
default (lexicographical)
sorting assumes that any uppercase letter is smaller than any lowercase letter,
it is necessary to define a custom comparison function for the characters. For
example, under default sorting, the letters a, A, z, Z, r, R would result in the
string “ARZarz”. However, the
task requires sorting and generating permutations in alphabetical order
AaBbCc…Zz. Therefore, the letters a, A, z, Z, r, R should produce the string “AaRrZz”.
In the first test, for the
string “aAb”, the smallest permutation will be “Aab”, and the
largest will be “baA” .
The lt function is used for sorting characters and
generating permutations. It compares two characters according to the
alphabetical order AaBbCc…Zz.
int lt(char
a, char b)
{
if
(toupper(a) != toupper(b)) return (toupper(a)
< toupper(b));
return (a
< b);
}
The main part of the
program. Read the number of test cases n.
cin >> n;
Process n test cases sequentially.
for (i = 0; i < n; i++)
{
Read the input string s and sort its characters in alphabetical
order.
cin >> s;
sort(s.begin(), s.end(), lt);
Print the current anagram
(permutation of characters) and use the next_permutation function
to generate the next one, as long as possible.
do {
cout << s << endl;
} while
(next_permutation(s.begin(), s.end(), lt));
}