C++ program to find Kth permutation Sequence
By Sakshi SinghConsider 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