## DEV Community 👩‍💻👨‍💻 is a community of 966,155 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Nhy

Posted on

# [Leetcode 06/2020] Permutation Sequence

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;

``````