```
class Solution {
public:
string getPermutation(int n, int k) {
int i, j, base=1;
string s(n, '0');
for(int i=1; i<=n; i++){
base*=i;
s[i-1]+=i; /*** change string s to "12345..." ***/
}
/***
* n=4 k=10 n!=24
* i=0 base=6 k=10 s=[2,1,3,4]
* i=1 base=2 k=4 s=[2,3,1,4]
* i=2 base=1 k=0 s=[2,3,4,1]
***/
for(i=0, k--; i<n; i++){
base/=(n-i); /*** f/(n-i) is the i-th base ***/
j=i+k/base; /*** f/base is the i-th value-index ***/
char c=s[j];
/*** move the remained number tegother **/
while(j>i) { s[j]=s[j-1]; j--;}
k%=base;
s[i]=c;
}
return s;
}
};
```