text: Lexicographic rank of a string | A O ( n ) solution for finding rank of string ; all elements of count [ ] are initialized with 0 ; A utility function to find factorial of n ; Construct a count array where value at every index contains count of smaller characters in whole string ; Removes a character ch from count [ ] array constructed by populateAndIncreaseCount ( ) ; A function to find rank of a string in all permutations of characters ; Populate the count array such that count [ i ] contains count of characters which are present in str and are smaller than i ; count number of chars smaller than str [ i ] fron str [ i + 1 ] to str [ len - 1 ] ; Reduce count of characters greater than str [ i ] ; Driver program to test above function
code: #include <stdio.h> NEW_LINE #include <string.h> NEW_LINE #define MAX_CHAR  256 NEW_LINE int count [ MAX_CHAR ] = { 0 } ; int fact ( int n ) { return ( n <= 1 ) ? 1 : n * fact ( n - 1 ) ; } void populateAndIncreaseCount ( int * count , char * str ) { int i ; for ( i = 0 ; str [ i ] ; ++ i ) ++ count [ str [ i ] ] ; for ( i = 1 ; i < MAX_CHAR ; ++ i ) count [ i ] += count [ i - 1 ] ; } void updatecount ( int * count , char ch ) { int i ; for ( i = ch ; i < MAX_CHAR ; ++ i ) -- count [ i ] ; } int findRank ( char * str ) { int len = strlen ( str ) ; int mul = fact ( len ) ; int rank = 1 , i ; populateAndIncreaseCount ( count , str ) ; for ( i = 0 ; i < len ; ++ i ) { mul /= len - i ; rank += count [ str [ i ] - 1 ] * mul ; updatecount ( count , str [ i ] ) ; } return rank ; } int main ( ) { char str [ ] = " string " ; printf ( " % d " , findRank ( str ) ) ; return 0 ; }