Given a string, the task is to generate all different strings that can be created using it’s characters.
For example, given string = “abc”
All possible distinct strings that can be generated using the three characters in this string are:
Notice that there were three characters in the string, so that possible number of ways in which these three characters could be rearranged is 3! = 6.
We fix one character and then insert the remaining two characters to form one combination, and for the next combination we reverse the insertion of the last two characters. We then fix a different character and repeat the process.
This was simple enough.
But, what if the given string is this : “abcdefgh”
This string has eight characters, that means the number of permutations is
8! = 40320. No one in their right minds would want to form 40320 combinations on their own.
Now comes to our rescue, a very elegant, unbuilt function in c++ .
* drum rolls *
The next_permutation () Function.
The next_permutation() function rearranged the elements in the range [first, last) into the next lexicographically greater permutation.
Woa, that was too much Arabic!
Let us first understand what’s meant by ‘[first, last)’.
When a range is written in this manner with a square opening bracket and closing parenthesis, it means that the all the elements from the first to the second last element of the range are included but the last element is not.
Example: All the integers before ‘5’ = 1,2,3,4
This can be written as: [1,5)
Now, what is ‘lexicographical’ ?
A ‘lexicographical order’ is the order that a language dictionary uses.
In a dictionary you would find all the words starting with the letter ‘a’ at the beginning and all those starting with ‘z’ at the end.
And within the ‘a’ lettered words, the words will be arranged in a manner like this:
So, what the next_permutation() function does is, it takes a range of the elements and rearranges them into the next greater lexicographical permutation. If it was able to rearrange the elements, it return true.
If it is not able to rearrange the elements (because they are already in there greatest lexicographical combination), it returns false.
To solve the given question, we sort the string to bring it into its smallest lexicographical order. We then run the next_permutation() function on this string until no greater combination can be formed and the next_permutation() function returns false.
Note that the given string might contain repeating characters, for example:
Because there are repeating characters, there will several redundant combinations. (The two ‘a’s are identical, but the next_permutation() function will treat them as distinct and will generate several combinations which are unique ‘in theory’ but are identical.)
To avoid this problem, we store our generated combinations in a set.