# C++ program to find Kth permutation Sequence

Consider two given integers N and K, We have to find the Kth permutation sequence from integer 1 to N using C++.

For example,

Suppose N=3 and K=4,

Now, the order list of permutation sequence from integer 1 to 3 are:

123

132

213

231

312

321

We have to return the 4th (Kth) sequence from the above i.e., 231.

**EXAMPLE: **

Input: N=4 , K= 10 Output: Kth permutation sequence = 2341

Explanation: All the permutation sequnece from integer 1 to N are: 1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321 10th sequence is 2341.

The total number of sequences containing 1 to N integers have total n! unique sequence. So, The value of K should be less than or equal to (N!).

## Kth Permutation Sequence Algorithm:

The **naive approach** to solve this problem is finding all the permutation sequences and returning Kth one out.

The **efficient way** to solve this problem is by the algorithm mentioned below. We will be using the factorial and backtracking concepts.

- The first position of sequences is occupied by each integer from 1 to n exactly (n-1)! number of times in ascending order.

Considering the above example for the detailed explanation of this step,

HereĀ n=4

Therefore, (n-1)! = 3! = 6

i.e, there will be 6 sequences starting from 1, 2, 3 and 4 in ascending order. The above sequence gives the validation of the statement.

Therefore, The first index of the Kth sequence will be k/(n-1)! - After finding the first position, the number used at the first position will be removed. Now the problem is reduced to finding the k%(n-1)! sequence from remaining n-1 integers.

Repeat the same concept for the next position and so on.

**Note: **While calculating factorial, product value can get very large compared to k, so stop calculating product value i.e., n * n-1 * …. as it becomes greater than k, to avoid the useless large computation.

The implementation of the above algorithm in C++

#include <bits/stdc++.h> using namespace std; //Function to find the factorial int fact(int A, int B){ int product=1; for(int i=1; i<=A; i++){ product*=i; //Stop computation if product > k if(product > B) return B+1; } return product; } //Function to find kth permutation string findPermutation(int n, int k) { string ans=""; int temp,c,fac; k--; set<int> hash; for(int i=1; i<=n; i++){ hash.insert(i); } while(k > 0){ fac = fact(--n, k); temp = k/fac; auto it = hash.begin(); advance(it, temp); c = *(it); ans+= to_string(c); hash.erase(c); k = k%fac; } for(auto it= hash.begin(); it!=hash.end(); it++){ ans += to_string(*it); } return ans; } int main() { int n = 4, k = 10; cout << "Kth permutation sequence = " << findPermutation(n, k); return 0; }

Output: Kth permutation sequence = 2341

**Also, refer**

## Leave a Reply