Find n | Java program to print n - th permutation ; Utility for calculating factorial ; 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 ; append string termination character and print result ; Driver program to test above method
public class PermuteString { final static int MAX_CHAR = 26 ; final static int MAX_FACT = 20 ; static long fact [ ] = new long [ MAX_FACT ] ; static void precomputeFactorirals ( ) { fact [ 0 ] = 1 ; for ( int i = 1 ; i < MAX_FACT ; i ++ ) fact [ i ] = fact [ i - 1 ] * i ; } static void nPermute ( String str , int n ) { precomputeFactorirals ( ) ; int len = str . length ( ) ; int freq [ ] = new int [ MAX_CHAR ] ; for ( int i = 0 ; i < len ; i ++ ) freq [ str . charAt ( i ) - ' a ' ] ++ ; String out = " " ; int sum = 10 ; int k = 0 ; while ( sum >= n ) { for ( int i = 0 ; i < MAX_CHAR ; i ++ ) { if ( freq [ i ] == 0 ) continue ; freq [ i ] -- ; sum = 0 ; int xsum = ( int ) fact [ len - 1 - k ] ; for ( int j = 0 ; j < MAX_CHAR ; j ++ ) xsum /= fact [ freq [ j ] ] ; sum += xsum ; if ( sum >= n ) { out += ( char ) ( i + ' a ' ) ; k ++ ; n -= ( sum - xsum ) ; break ; } if ( sum < n ) freq [ i ] ++ ; } } for ( int i = MAX_CHAR - 1 ; k < len && i >= 0 ; i -- ) if ( freq [ i ] != 0 ) { out += ( char ) ( i + ' a ' ) ; freq [ i ++ ] -- ; } System . out . println ( out ) ; } public static void main ( String [ ] args ) { int n = 2 ; String str = " geeksquiz " ; nPermute ( str , n ) ; } }