Permutation Index

Problem:
While i was developing a parallel application i faced a problem, this problem says "given set of letters, can you tell me the permutation number X if all permutation are sorted in lexicographical order ?"
example:
letters {a, b, c}
Permutations: abc, acb, bac, bca, cab,cba
what i want given number N generate the permutation which index is N (eg. 3-> bca)

The normal solution for this problem is using the function next_permutation N times till finding the solution - and this is not an efficient solution because as you know the number of permutations is Factorial the length of the letters set ..

At this point: we have to search for a method that we can use to generate the permutation directly without passing on all other permutations

Solution :
As we mentioned in the problem you know that Number of Permutations with length X
is factorial X
okay lets use the given example:
letters {a, b, c}
perumtations are 3! = 6 Why ??
because the first letter can have 3 choices the second can have 2 (we removed the letter we choose in the first) and the third have only 1 choice so 3*2*1 = 6
from that we can say that there is 6 permutations it can start with 3 letters each letter can be followed by (2*1) permutations
abc, acb (2 permutations starting with a)
bac, bca (2 permutations starting with b)
cab, cba (2 permutations starting with c)

For any string of length N there exist N! permutation - also there exist (N-1)! Permutations starts with each letter(why ?)

Because when we use the first letter we can use it again so we have N-1 letter we want to make different permutations for it so we have (N-1)! permutations for them

from that we can think of a very simple method
i'll illustrate this method by example:
In {a,b,c},what is the permutation with index 3 ?

We know that (0,1 start with a) - (2,3 start with b) - (4,5 start with c)
so the string till now is "b"
Then we remove b from the choices and so we have only 2 remaining letters (a,c)
now the remaining index is 1

Again get index 1 in permutations (a,c)
using the same method i get that this permutation starts with c ( as there is 2! permutations 1 starting with a and 1 starting with c)
now the string till now is "bc"

Again lets get the reminder which is 0
having letter (a) i want to get the permutation number 0 : it's a
so the string is "bca"

From that we know that i can get the first character by dividing by (N-1)!
then remove this character from the set and adding it to the string
then getting the new index (reminder) by getting the mod with (N-1)!
and then do that again till generating the whole string

Code:

string getNthPermutation(long long index,string st)
{
 // st is sorted string contain the letters
 if(st=="")return"";
 int len = st.size();
 long long fact = factorial(len-1);
 long long frst = index/fact;
 char frstChar = st[frst];
 long long newIndex = index%fact;
 st.erase(st.begin()+frst);
 return frstChar + getNthPermutation(newIndex,st);
}