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 code
< ? php $ MAX_CHAR = 256 ; $ count = array_fill ( 0 , $ MAX_CHAR + 1 , 0 ) ; function fact ( $ n ) { return ( $ n <= 1 ) ? 1 : $ n * fact ( $ n - 1 ) ; } function populateAndIncreaseCount ( & $ count , $ str ) { global $ MAX_CHAR ; for ( $ i = 0 ; $ i < strlen ( $ str ) ; ++ $ i ) ++ $ count [ ord ( $ str [ $ i ] ) ] ; for ( $ i = 1 ; $ i < $ MAX_CHAR ; ++ $ i ) $ count [ $ i ] += $ count [ $ i - 1 ] ; } function updatecount ( & $ count , $ ch ) { global $ MAX_CHAR ; for ( $ i = ord ( $ ch ) ; $ i < $ MAX_CHAR ; ++ $ i ) -- $ count [ $ i ] ; } function findRank ( $ str ) { global $ MAX_CHAR ; $ len = strlen ( $ str ) ; $ mul = fact ( $ len ) ; $ rank = 1 ; populateAndIncreaseCount ( $ count , $ str ) ; for ( $ i = 0 ; $ i < $ len ; ++ $ i ) { $ mul = ( int ) ( $ mul / ( $ len - $ i ) ) ; $ rank += $ count [ ord ( $ str [ $ i ] ) - 1 ] * $ mul ; updatecount ( $ count , $ str [ $ i ] ) ; } return $ rank ; } $ str = " string " ; echo findRank ( $ str ) ; ? >