LeetCode OJ--Permutation Sequence *

class Solution{
public:
    string getPermutation(int n, int k)
    {
        //get fractial
        vector<int> fractial;
        fractial.push_back(1);
        for(int i = 1;i<n;i++)
        {
            fractial.push_back(fractial[i-1]*(i+1));
        }
        //to mark if this digit selected ,true means can be selected, false means already selected.
        vector<bool> allnum;
        for(int i = 0; i <=n; i++)
            allnum.push_back(true);

        int ChuShu = k - 1, YuShu = 0;
        string ans;
        int weishu = 0;

        while(weishu<n)
        {
            int _num_i;
            int place;
            if(weishu == n-1) // the last digit
                _num_i = select(allnum,1);
            else
            {
                YuShu = ChuShu % fractial[n-2-weishu];
                place = ChuShu / fractial[n-2-weishu];
                 
                _num_i = select(allnum,place + 1 );
            }
            ChuShu = YuShu;
            weishu ++;
            char ch = ‘3‘ - 3 + _num_i;
            ans += ch;
        }
        return ans;
    }
    int select(vector<bool> &allnum,int place)
    {
        int i = 1;
        
        while(place)
        {
            if(allnum[i] == true)
            {
                place--;
                if(place == 0)
                    break;
            }
            i++;
        }
        allnum[i] = false;
        return i;
    }
};

int main()
{
    class Solution myS;
    cout<<myS.getPermutation(5,16);
    return 0;
}