[Leetcode 06/2020] Permutation Sequence
Published: 2020-06-20 13:10:42

Problem: 
//============================================
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 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.
Given k will be between 1 and n! inclusive.
Example 1:

Input: n = 3, k = 3
Output: "213"

//============================================
This problem is really easy using C++ with STL library. Using next_permutation(string.begin(), string.end()) function, we can use a while loop as the solution below.
```
class Solution {
public:
    string getPermutation(int n, int k) {
        string s ="";
        for(int i =1;i <=n; i++)
        {
            s+= to_string(i);
        }
        cout<<s<<endl;
        while(k>1) //First time count from 1
        {
            k--;
            next_permutation(s.begin(), s.end());
            
        }
        return s;
    }
};
```

Other efficient method: (https://www.geeksforgeeks.org/find-the-k-th-permutation-sequence-of-first-n-natural-numbers/)
Explanation with simple example {1,2,3,4} and k =8
Step 1: First we find the first index using the formula 
index = k / (n-1)! (with k = k-1)
so first index = 7/(4-1)! = 1 => first index = 1, we have {2,.,.}
Step 2: Then we find the second index with k now will be calculated to k1 = k%(n-1)! = 7%6 =  1 so next index = 1/(3-1)!=1/2! = 0 in the set {1,3,4} so 1 will be the next number. We have {2,1,.,.}
Step 3: Similarly, we calculate k2 = 1%(2!) = 1. next index = k2/(n-3)! = 1/1! = 1 in the set {3,4}. So 4 will be the next number. We have {2,1,4,.}
Finally we have last number remaining. So we just fill in and the final result is {2,1,4,3}

```
class Solution {
public:
    int factorial(int n) 
    { 
        return (n==1 || n==0) ? 1: n * factorial(n - 1);  
    } 
    int findFirstNumIndex(int& k, int n) 
    { 
  
        if (n == 1) //last number remaining in set, so return the index 0
            return 0; 
        n--; 

        int first_num_index; 
        int n_partial_fact = factorial(n);

        // First position of the kth sequence will be at index = k / (n-1)!  
        first_num_index = k / n_partial_fact; 

        k = k % n_partial_fact; 

        return first_num_index; 
    } 
    string getPermutation(int n, int k) {
        string ans = ""; 
  
    set<int> s; 
  
    // Insert all natural number in set {1,2,3,4}
    for (int i = 1; i <= n; i++) 
        s.insert(i); 
  
    set<int>::iterator itr; 
  
    // Mark the first position 
    itr = s.begin(); 
  
    // K starts couting from 1 
    k = k - 1; 
  
    for (int i = 0; i < n; i++) { 
  
        int index 
            = findFirstNumIndex(k, n - i); 
  
        advance(itr, index); //get the value of number in the index. 
  
        ans += (to_string(*itr)); 
  
        // remove current number from the set 
        s.erase(itr); 
  
        itr = s.begin(); 
    } 
    return ans; 

```
Please leave comment if I made any mistakes. Thanks a lot.