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.

  1. 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)!
  2. 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

Your email address will not be published. Required fields are marked *