[Leetcode] 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.

Analysis:

From the example, we observed that the permutations can be divided into n groups, each beginning with degit 1 <=i <=n and the first digit must be i = k/(n-1)!

Similarly, the position of k in the group is k % (n-1)! and the remaining numbers are divided into n-1 groups and the first digit must be i = (k % (n-1)!)/(n-2)!.

Loop until all the numbers are set.

    string getPermutation(int n, int k) {
     vector<int> nums;
     //set an array with all numbers
     for (int i = 0; i<n; i++)
      nums.push_back(i + 1);
        
        //get (n-1)!
     int nn = 1;
     for (int i = 1; i < n; i++)
      nn = nn * i;
    
     string str;
     int kk = k - 1;
     while (n > 1)
     {
         //the kth permutation is at (k-1)/(n-1)! group
      int pos = kk / nn;
      str.push_back(nums[pos] + '0');
      //the number has been used, removed it from the array
      nums.erase(nums.begin() + pos);
      //the position in the group is at (k-1) % (n-1)!
      kk = kk % nn;
      //the number of permutations in the group is (n-2)!
      n = n - 1;
      nn = nn / n;
     }
     str.push_back(nums[0] + '0');
     return str;
    }