Get the Kth Permutation

Problem: Given an array of N numbers {1,2...N},  get the Kth permutation. For example, when N = 3, the first permutation is "123", the second is "132", the sixth is "321".

Solution: With STL, we can use next_permutation(). Just call it K-1 times. However, next_permutation()'s complexity is not constant. A better way is to use recursion:

String Find(string a, int k)
{
   if(len(a)==1 or k==0) return a;

   int N = len(a);
   
   int i = k/factorial(N-1);
   int j = k%factorial(N-1);

   return a[i] + find(a.substring(0,i) + a.substring(i+1), j);
}