Lexicographic rank of a string | A utility function to find factorial of n ; A utility function to count smaller characters on right of arr [ low ] ; A function to find rank of a string in all permutations of characters ; count number of chars smaller than str [ i ] fron str [ i + 1 ] to str [ len - 1 ] ; Driver program to test above function
def fact ( n ) : NEW_LINE INDENT f = 1 NEW_LINE while n >= 1 : NEW_LINE INDENT f = f * n NEW_LINE n = n - 1 NEW_LINE DEDENT return f NEW_LINE DEDENT def findSmallerInRight ( st , low , high ) : NEW_LINE INDENT countRight = 0 NEW_LINE i = low + 1 NEW_LINE while i <= high : NEW_LINE INDENT if st [ i ] < st [ low ] : NEW_LINE INDENT countRight = countRight + 1 NEW_LINE DEDENT i = i + 1 NEW_LINE DEDENT return countRight NEW_LINE DEDENT def findRank ( st ) : NEW_LINE INDENT ln = len ( st ) NEW_LINE mul = fact ( ln ) NEW_LINE rank = 1 NEW_LINE i = 0 NEW_LINE while i < ln : NEW_LINE INDENT mul = mul / ( ln - i ) NEW_LINE countRight = findSmallerInRight ( st , i , ln - 1 ) NEW_LINE rank = rank + countRight * mul NEW_LINE i = i + 1 NEW_LINE DEDENT return rank NEW_LINE DEDENT st = " string " NEW_LINE print ( findRank ( st ) ) NEW_LINE