Last Updated: 28 Jan, 2021

K-th Permutation Sequence

Moderate

Asked in companies

Solve now

Problem statement

You have been given two integers ‘N’ and ‘K’. Your task is to find the K-th permutation sequence of numbers from 1 to ‘N’. The K-th permutation is the K-th permutation in the set of all sorted permutations of string 1 to ‘N’.

For example :

If ‘N’ = 3 and ‘K’ = 4. Then all permutations for ‘N’ = 3 are “123”, “132”, “213”, “231”, “312”, “321”. So the 4-th permutation is “231”.

Input Format:

The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains two single space-separated integers ‘N’ and ‘K’, respectively.

Output Format:

The only line of output contains a string of K-th permutation sequence of numbers from 1 to ‘N’.

Print the output of each test case in a separate line.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1 <= ‘T’ <= 100
1 <= ‘N’ <= 9
1 <= ‘K’ <= N!

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Naively we will generate all permutations of sequence 1 to ‘N’ and store them in an array. We will use recursion to generate all permutations.

Here is the algorithm:

We will call a void function permutate. The permutate function will work as follows (here ‘s’ and ‘ans’ denotes the string we passed to the function and the string we are generating, respectively):
- If s.length() == 0 (Base Case)
  - Push the string ‘ans’ into the array where all permutations will be stored.
- We run a for loop from i = 0 to s.length():
  - Do a recursive call by removing i-th character from ‘s’ and adding it to ‘ans’.
Finally, return the K-th element of the array.

Solve now

02 Approach

The key observation here is that the Kth permutation sequence can be formed by choosing the 1st digit and then the rest of the digits one by one.

For N=3, we have the permutations:

1 | 2,3

1 | 3,2

2 | 1,3

2 | 3,1

3 | 1,2

3 | 2,1

Please note, "|" bar is put to separate the first digit from the rest of the digits.

There are a total of N! = 3! = 6 permutations. Each 1st digit is "attached" to (n-1)! = 2! = 2 permutations formed by the rest of digits.

Thus, to choose the 1st digit, simply calculate (k -1) / (n - 1)! and use it to index into an array of digits 1,2,3.

Once the 1st digit is chosen, we choose 2nd and so on.

We remove the 1st digit from the array of digits, so the remaining are the "rest of digits".

For example for N = 3 and K = 4, the first digit would be present at index (4 - 1)/(3 - 1)! i.e. 1 in array [1, 2, 3]. So the first digit will be 2. Similarly, we can find all digits.

Solve now