K-th Permutation Sequence

Posted: 28 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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 
Approach 1

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.
Try Problem