60 Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> number;
        int factorial = 1;
        for (int i=1;i<=n;i++)
        {
            number.push_back(i);
            factorial *= i;
        }
        k--;
        for (int i=0;i<n;i++)
        {
            factorial = factorial/(n-i);
            int k_bit = k/factorial;
            forward(number,i+k_bit,i);
            k=k%factorial;
        }
        
        string res;
        for (int i=0;i<number.size();i++)
            res.push_back(number[i]+'0');
        return res;
    }
    void forward(vector<int> &number, int new_pos,int old_pos)
    {
        for (int j=new_pos;j>old_pos;j--)
        {
            swap(number[j],number[j-1]);
        }
    }
};