Lexicographic Rank of a String

Permutation :

• Let the given string be “CODING”. In the input string, ‘C’ is the first character. There are a total of 6 characters and 0 of them are smaller than ‘C’. So there can be 0 * 5! smaller strings where the first character is smaller than ‘C’.
• Now let us Fix ‘C’ and find the smaller strings starting with ‘C’.
• Repeat the same process for ‘O’, rank is 0*5! + 4*4! +…
• Now fix ‘O’ and repeat the same process for ‘D’, rank is 0*5! + 4*4! + 0*3! +…
• Now fix ‘D’ and repeat the same process for ‘I’, rank is 0*5! + 4*4! + 0*3! + 1*2! +…
• Now fix ‘I’ and repeat the same process for ‘N’, rank is 0*5! + 4*4! + 0*3! + 1*2! + 1*1! +…
• Now fix ‘N’ and repeat the same process for ‘G’, rank is 0*5! + 4*4! + 0*3! + 1*2! + 1*1! + 0*0!
• Rank = 0*5! + 4*4! + 0*3! + 1*2! + 1*1! + 0*0! = 99
   

The above computations find the count of smaller strings. Therefore the rank of a given string “CODING” is the count of smaller strings plus 1. The final rank = 1 + 99 = 100.

Approach :

• First make a function, say ‘fact()’ taking integer ‘n’ as a parameter which will return the factorial of the integer ‘n’.
• Now make a function, say ‘smallRight()’ taking string ‘S’, integer variable ‘low’ representing lower index and integer variable ‘high’ representing higher index as parameters to calculate count of smaller characters in right.
  • Declare a variable, say ‘count’ to store the count of smaller characters in right.
  • Iterate from ‘low’ + 1 to ‘high’ with the help of iterator pointer ‘i’.
    • If a character, S[i] is less than S[low] then increment ‘count’.
  • Return ‘count’ to the function.
• Inside the given function:
  • First calculate the factorial of the length of the string by calling function ‘fact()’ passing length of the string as its argument and store the value returned in a variable, say ‘factorial’.
  • Now declare a variable, say ‘rank’ to store the final answer and initialize it with value 1.
  • Now iterate over the whole string with iterator pointer ‘i’.
    • Make ‘factorial’ as factorial = factorial / len - i. Where ‘len’ denotes the length of the string ‘S’.
    • Now call the function ‘smallRight()’ passing string ‘S’, ‘i’ and ‘len’ - 1 as its arguments in place of ‘S’, ‘low’ and ‘high’ respectively and store the result returned in a variable, say ‘count’.
    • The above step is done to count the characters smaller than S[i] from S[i+1] to S[len - 1].
    • Now make ‘rank’ as ‘rank’ = ‘rank’ + ‘count’ * ‘factorial’.
• Return ‘rank’ to the function as the final answer.

The idea is to store the count of smaller elements in the right of each character in an auxiliary array in which the value at every index contains the count of smaller characters in the whole string.

Approach:

• First call the function ‘fact()’ passing ‘len’ as an argument, where ‘len’ is the length of the given string ‘S’ to calculate the factorial and store the value returned in a variable, say ‘factorial’.
• Initialize integer variable ‘rank’ to store the final answer and initialize it with value 1.
• Declare an auxiliary array, say ‘count’ of size 256 as there are 256 characters and initialize it with 0.
• Now fill the ‘count’ array such that count[i] contains the count of characters which are present in ‘S’ and smaller than ‘i’ where ‘i’ is the iterator pointer.
• Now iterate over the whole string with iterator pointer ‘i’.
  • Make ‘factorial’ as factorial = factorial / len - i. Where ‘len’ denotes the length of the string ‘S’.
  • Now count the number of characters smaller than S[i] from S[i+1] to S[len - 1].
  • Update ‘rank’ as rank = rank + count[S[i] - 1] * ‘factorial’.
  • Now reduce the count of characters greater than S[i].
• Return ‘rank’ to the function.