Генерація анаграм (Розбір)

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$?

Algorithm analysis

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".

Example

In the first test, for the string "$aAb$", the smallest permutation will be "$Aab$", and the largest will be "$baA$".

Algorithm implementation

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));
}