Given a string, find its rank among all its permutations sorted lexicographically. For example, rank of “abc” is 1, rank of “acb” is 2, and rank of “cba” is 6.
For simplicity, let us assume that the string does not contain any duplicated characters.
Read full article from Lexicographic rank of a string | GeeksforGeeks
For simplicity, let us assume that the string does not contain any duplicated characters.
Let the given string be “STRING”. In the input string, ‘S’ is the first character. There are total 6 characters and 4 of them are smaller than ‘S’. So there can be 4 * 5! smaller strings where first character is smaller than ‘S’.
Rank = 4*5! + 4*4! + 3*3! + 1*2! + 1*1! + 0*0! = 597
Time Complexity O(n^2).
int
findSmallerInRight(
char
* str,
int
low,
int
high)
{
int
countRight = 0, i;
for
(i = low+1; i <= high; ++i)
if
(str[i] < str[low])
++countRight;
return
countRight;
}
// A function to find rank of a string in all permutations
// of characters
int
findRank (
char
* str)
{
int
len =
strlen
(str);
int
mul = fact(len);
int
rank = 1;
int
countRight;
int
i;
for
(i = 0; i < len; ++i)
{
mul /= len - i;
// count number of chars smaller than str[i]
// fron str[i+1] to str[len-1]
countRight = findSmallerInRight(str, i, len-1);
rank += countRight * mul ;
}
return
rank;
}
int
fact(
int
n)
{
return
(n <= 1)? 1 :n * fact(n-1);
}
We can reduce the time complexity to O(n) by creating an auxiliary array of size 256.
// Construct a count array where value at every index
// contains count of smaller characters in whole string
void
populateAndIncreaseCount (
int
* count,
char
* str)
{
int
i;
for
( i = 0; str[i]; ++i )
++count[ str[i] ];
for
( i = 1; i < 256; ++i )
count[i] += count[i-1];
}
// Removes a character ch from count[] array
// constructed by populateAndIncreaseCount()
void
updatecount (
int
* count,
char
ch)
{
int
i;
for
( i = ch; i < MAX_CHAR; ++i )
--count[i];
}
// A function to find rank of a string in all permutations
// of characters
int
findRank (
char
* str)
{
int
len =
strlen
(str);
int
mul = fact(len);
int
rank = 1, i;
int
count[MAX_CHAR] = {0};
// all elements of count[] are initialized with 0
// Populate the count array such that count[i] contains count of
// characters which are present in str and are smaller than i
populateAndIncreaseCount( count, str );
for
(i = 0; i < len; ++i)
{
mul /= len - i;
// count number of chars smaller than str[i]
// fron str[i+1] to str[len-1]
rank += count[ str[i] - 1] * mul;
// Reduce count of characters greater than str[i]
updatecount (count, str[i]);
}
return
rank;
}
The above programs don’t work for duplicate characters. To make them work for duplicate characters, find all the characters that are smaller (include equal this time also), do the same as above but, this time divide the rank so formed by p! where p is the count of occurrences of the repeating character.