Find n | Python3 program to print n - th permutation ; Utility for calculating factorials ; Function for nth permutation ; length of given string ; Count frequencies of all characters ; out string for output string ; iterate till sum equals n ; We update both n and sum in this loop . ; check for characters present in freq [ ] ; Remove character ; calculate sum after fixing a particular char ; if sum > n fix that char as present char and update sum and required nth after fixing char at that position ; if sum < n , add character back ; if sum == n means this char will provide its greatest permutation as nth permutation ; print result ; Driver Code
MAX_CHAR = 26 NEW_LINE MAX_FACT = 20 NEW_LINE fact = [ None ] * ( MAX_FACT ) NEW_LINE def precomputeFactorials ( ) : NEW_LINE INDENT fact [ 0 ] = 1 NEW_LINE for i in range ( 1 , MAX_FACT ) : NEW_LINE INDENT fact [ i ] = fact [ i - 1 ] * i NEW_LINE DEDENT DEDENT def nPermute ( string , n ) : NEW_LINE INDENT precomputeFactorials ( ) NEW_LINE length = len ( string ) NEW_LINE freq = [ 0 ] * ( MAX_CHAR ) NEW_LINE for i in range ( 0 , length ) : NEW_LINE INDENT freq [ ord ( string [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT out = [ None ] * ( MAX_CHAR ) NEW_LINE Sum , k = 0 , 0 NEW_LINE while Sum != n : NEW_LINE INDENT Sum = 0 NEW_LINE for i in range ( 0 , MAX_CHAR ) : NEW_LINE INDENT if freq [ i ] == 0 : NEW_LINE INDENT continue NEW_LINE DEDENT freq [ i ] -= 1 NEW_LINE xsum = fact [ length - 1 - k ] NEW_LINE for j in range ( 0 , MAX_CHAR ) : NEW_LINE INDENT xsum = xsum // fact [ freq [ j ] ] NEW_LINE DEDENT Sum += xsum NEW_LINE if Sum >= n : NEW_LINE INDENT out [ k ] = chr ( i + ord ( ' a ' ) ) NEW_LINE n -= Sum - xsum NEW_LINE k += 1 NEW_LINE break NEW_LINE DEDENT if Sum < n : NEW_LINE INDENT freq [ i ] += 1 NEW_LINE DEDENT DEDENT DEDENT i = MAX_CHAR - 1 NEW_LINE while k < length and i >= 0 : NEW_LINE INDENT if freq [ i ] : NEW_LINE INDENT out [ k ] = chr ( i + ord ( ' a ' ) ) NEW_LINE freq [ i ] -= 1 NEW_LINE i += 1 NEW_LINE k += 1 NEW_LINE DEDENT i -= 1 NEW_LINE DEDENT print ( ' ' . join ( out [ : k ] ) ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 2 NEW_LINE string = " geeksquiz " NEW_LINE nPermute ( string , n ) NEW_LINE DEDENT