Description
Given a string of characters, an anagram of the string is obtained by permuting
the letters in the string arbitrarily. For example, the anagrams of the string
“abab” are “aabb”, “abab”, “abba”, “baab”, “baba” and “bbaa”. The possible
anagrams of a string can be ordered by the lexicographic ordering. A string
s1 is less than s2 if at the smallest position in which the two strings differ,
s1 has a smaller character than s2. This is the usual dictionary ordering of
words. The anagrams of “abab” are listed above in increasing order.
The rank of a string is the number of anagrams of the string that are less
than it. This is its position in the ordered list of all its anagrams, starting
with 0. The rank of “abab” is 1, while that of “baab” is 3.
Given a string s, you have to write a function to compute its rank. Also, given
a position x, you have to find the anagram of s that has rank x.
Input Format
The input contains a string s followed by a number x, separated by a space.
The length of the string is at most 18, and it can be assumed it contains
only small letters ‘a’,…,’z’. Also, x is less than the number of possible
anagrams of s.
Output
Output the rank of s and the anagram of s that occurs at position x.
Example
Input Output
abab 4 1 baba
smile 80 117 miles
Hint:
The total number of anagrams of a string of length n is the multinomial
coefficient n!/(n_1!*n_2!*…*n_k!), where n_i is the number of occurrences
of the ith character. Note that 18! is within the range of a long long number
but not an int. To find the rank, find the number of strings that have a
smaller character than the given string in the first position, then find the
number that have the same first character but a smaller second character
and so on. Reverse this process to get the string from the rank.
There is a library function next_permutation that can be used to generate
the anagram of the string that comes next in lexicographic order. This
is defined in the header file <algorithm>, and can be used as
next_permutation(s.begin(),s.end())
where s is a string (or vector/array). This modifies the string itself to the
next anagram in lex order and returns true, unless the string is the largest
in lex order, in which case it does nothing and returns false. You can use
this for testing for small x, but in general this will be too inefficient. You
can also check that the functions you define are inverses of each other.
Submission
Submit a single .cpp file on moodle named RollNo_2.cpp
