Find n | C ++ 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 ; append string termination character and print result ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE const int MAX_CHAR = 26 ; const int MAX_FACT = 20 ; ll fact [ MAX_FACT ] ; void precomputeFactorials ( ) { fact [ 0 ] = 1 ; for ( int i = 1 ; i < MAX_FACT ; i ++ ) fact [ i ] = fact [ i - 1 ] * i ; } void nPermute ( char str [ ] , int n ) { precomputeFactorials ( ) ; int len = strlen ( str ) ; int freq [ MAX_CHAR ] = { 0 } ; for ( int i = 0 ; i < len ; i ++ ) freq [ str [ i ] - ' a ' ] ++ ; char out [ MAX_CHAR ] ; int sum = 0 ; int k = 0 ; while ( sum != n ) { sum = 0 ; for ( int i = 0 ; i < MAX_CHAR ; i ++ ) { if ( freq [ i ] == 0 ) continue ; freq [ i ] -- ; int xsum = fact [ len - 1 - k ] ; for ( int j = 0 ; j < MAX_CHAR ; j ++ ) xsum /= fact [ freq [ j ] ] ; sum += xsum ; if ( sum >= n ) { out [ k ++ ] = i + ' a ' ; n -= ( sum - xsum ) ; break ; } if ( sum < n ) freq [ i ] ++ ; } } for ( int i = MAX_CHAR - 1 ; k < len && i >= 0 ; i -- ) if ( freq [ i ] ) { out [ k ++ ] = i + ' a ' ; freq [ i ++ ] -- ; } out [ k ] = ' \0' ; cout << out ; } int main ( ) { int n = 2 ; char str [ ] = " geeksquiz " ; nPermute ( str , n ) ; return 0 ; }