K-th Permutation Sequence of first N natural numbers
You’re given two integers N and K, your task is to find the Kth permutation of the sequence of first N natural numbers.

For Example :

If N = 3 and K = 3. The Possible Permutations for N = 3 are {(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)}. In this list, the 3rd Permutation sequence is 2 1 3.

Input Format :

The first line of the input contains an integer T denoting the number of test cases. The 'T' test cases follow. The first line of each test case contains two space-separated integers N and K, as specified in the problem statement.

Output Format :

For each test case, print an array denoting the Kth permutation of the sequence of first N natural numbers.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1

Question

K-th Permutation Sequence of first N natural numbers

You’re given two integers N and K, your task is to find the Kth permutation of the sequence of first N natural numbers.

For Example :

If N = 3 and K = 3.
The Possible Permutations for N = 3 are {(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)}. 
In this list, the 3rd Permutation sequence is 2 1 3.

Input Format :

The first line of the input contains an integer T denoting the number of test cases. The 'T' test cases follow.

The first line of each test case contains two space-separated integers N and K, as specified in the problem statement.

Output Format :

For each test case, print an array denoting the Kth permutation of the sequence of first N natural numbers.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <=  N <= 5 * 10^3
1 <= K <= min(N!, 5 * 10^3)

Time limit: 1 sec

Accepted Answer

The task is to find the Kth permutation of the sequence of first N natural numbers.

Generate all possible permutations of the sequence of first N natural numbers
Sort the permutations in lexicographical order
Return the Kth permutation from the sorted list

Accepted Answer

Insert all natural numbers upto n in a set.

Use iterator to traverse the set.

First position of the kth sequence will be occupied by the number present at index = k / (n-1)!

For each value in the set, find the first number index, then move the iterator to that index and add the value at that index to answer

Accepted Answer

Recursive Approach

We’ll make a function named ‘kthPermutation’ with two integer parameters n and k.
1. Inside this function, we’ll make a 2 Dimensional array named ‘answer’ and an array named ‘v’ and then call our helper function kPermutationHelper(0, v, n, answer).
2. Kth permutation will be answer[k-1].
Call the recursive function ‘kthPermutationHelper’ with parameters: integer i, an array v, integer N, and a 2 Dimensional array named ‘answer’.
Base case: if ‘i’ equal to N, then simply push ‘v’(a permutation of N) into ‘answer’ and return.
Now we make a boolean array named ‘visited’ of size N+1 to mark the occurrences. Initially, we’ll fill this array with 0.
Then mark all the numbers visited, which are present in the array ‘v’.
Then we check if a number already exists in array v or not, by running a loop(loop variable j) from 1 till N.
1. We first check if the current number ‘j’ already exists in our array ‘v’ or not. If it doesn’t exist in v, then we’ll place this number ‘j’ at this position.
2. We do this by pushing ‘j’ into 'v’ and calling kthPermutationHelper(i+1, v, n, answer). After this do the pop operation, i.e, backtrack.

Space Complexity: OtherExplanation:

O(N*N!), where N is the number whose Kth permutation sequence is to be found.

As we are using a 2 Dimensional array with N! Columns and each column will have N rows to store the N! Possible permutations. Thus, the space complexity will be O(N*N!).

Time Complexity: OtherExplanation:

O(N*N!), where N is the number whose Kth permutation sequence is to be found.

In total there are N! Permutations possible, and in each call, we iterate on the number, and there are N such numbers, which will cost us O(N) time. Hence, to generate all the permutations we’ll take O(N*N!) time.

Accepted Answer

Mathematics Based Approach

We start by making an array named ‘answer’, which will store the Kth permutation.
Then we’ll make an array named ‘numbersLeft’ and we’ll store all values from 1 till N inside this array.
Now we run a loop(loop variable i) from 0 till N - 1.
1. We then calculate the value at the current index(using the method discussed below).
2. Then we remove this value from the array ‘numbersLeft’ using the erase operation.

Let’s see how will we calculate the indices:

The starting position of any N length sequence is occupied by each of the numbers from 1 to n exactly n! / n that is (n-1)! times and that too in an Increasing order. So the first position of the kth sequence will be occupied by the number present at index = (k-1) / (n-1)!. We are using K-1 instead of K because we are using 0-Based Indexing. Similarly, we’ll do this for the other indices.

As we know calculating factorials can be very tedious work. Hence we use an observation here that, as soon as the product of the n*(n-1)*(n-1).... > K, we do not need to calculate the actual factorial value. The reason for this is that K/(nOriginal) and K/(nPartial) both will become equal to 0, when nPartial > K, where nOriginal is the original factorial value of N and nPartial is the partial factorial value of N. Hence we can save our time here by not calculating the factorial values.

We start by identifying the first index using the formula index = K/(N-1)!. Note that in this formulae we’ll plug in the value of k after decreasing it by 1 i.e K=K-1(We do this because we are using 0 based indexing).
Then we find the second index by using the same formula as we used in Step 1, but we’ll calculate our new K(let’s name it as K1), by using K1=K%(N-1)!. Then we’ll calculate the second index = K1/(N-2)!
Similarly, we find we’ll calculate our new K(let’s name it as K2), by using K2=K1%(N-2)!. Then we’ll calculate the third index = K2/(N-3)!.
We keep doing the above steps till only one number is left.

Let’s understand the above steps with the help of an example:

Let’s take N = 4 {1,2,3,4} and K = 8
First index = (8-1)/(4-1)! = 7/3! = 1, which means the first number of our Kth sequence is 2(which is at index 1 in the sequence {1,2,3,4}
For the second index K1 = K%(N-1)! = 7%6 = 1. Then second index = K1/(N-2)! = 1/2! = 0. Therefore the second digit of our 8th sequence is 1(which is at index 0 in the set {1,3,4}
Similarly for the third index K2 = K1%(N-2)! = 1%2! = 1. Therefore, the third index = K3/(N-3)! = 1/1! = 1. Therefore the third digit of our 8th sequence is 4(which is at index 1 in the set {3,4}
Clearly, 4 will be the final digit in the 8th sequence since only 4 is left in the set.
Therefore our final answer(8th sequence) is 2 1 4 3.

Space Complexity: O(n)Explanation:

O(N), where N is the number whose Kth permutation sequence is to be found.

As we are using an array of size N to store Kth permutation and another array of size N named ‘numbersLeft’ to store numbers left. Thus, the final space complexity will be O(N+N) = O(N).

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the number whose Kth permutation sequence is to be found.

As we’ll be traversing the original set of N Natural numbers once to get the value at those N indices and at the same time the erase operation will also take O(N) time. Thus, the final space complexity will be O(N*N) = O(N^2).

Java (SE 1.8)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(N),



    where N is the number whose Kth permutation sequence is to be found.

*/



import java.util.ArrayList;



public class Solution 

{

    public static ArrayList  kthPermutation(int n, int k) 

    {

        ArrayList answer = new ArrayList<>();

        ArrayList numbersLeft = new ArrayList<>(n);

        

        // Filling the vector with Numbers from 1 to N.

        for (int i = 0; i < n; i++)

        {

            numbersLeft.add(i+1);

        }



        // Decreasing k by 1 since we're using 0-Based Indexing.

        k--;

        

        for (int i = 0; i < n; i++)

        {

            int index, position;

            int currentN = n - i;

            int nPartial = 1;



            currentN--;

            

            // Calculating nPartial such that nPartial > K.

            while (k >= nPartial && currentN > 0)

            {

                nPartial *= currentN;

                currentN--;

            }



            index = k / nPartial;

            k %= nPartial;



            position = index;



            int number = numbersLeft.get(position);



            // Pushing this number into our answer vector.

            answer.add(number);



            // Erasing this number from numbersLeft vector.

            numbersLeft.remove(position);

            //numbersLeft.erase (numbersLeft.begin() + position );

        }



        return answer;

    }

}

Python (3.5)

'''
    Time Complexity: O(N^2)
    Space Complexity: O(N),

    where N is the number whose Kth permutation sequence is to be found.
'''


def kthPermutation(n, k):
    answer = []

    # Filling the list with Numbers from 1 to N.
    numbersLeft = [i+1 for i in range(n)]

    # Decreasing k by 1 since we're using 0-Based Indexing.
    k -= 1

    for i in range(n):
        currentN = n-i
        nPartial = 1

        currentN -= 1

        # Calculating nPartial such that nPartial > K.
        while (k >= nPartial and currentN > 0):
            nPartial *= currentN
            currentN -= 1

        index = k // nPartial
        k %= nPartial

        position = index

        number = numbersLeft[position]

        # Pushing this number into our answer vector.
        answer.append(number)

        # Erasing this number from numbersLeft vector.
        numbersLeft.pop(position)

    return answer

C++ (g++ 5.4)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(N),



    where N is the number whose Kth permutation sequence is to be found.

*/



vector kthPermutation(int n, int k)

{

    vector answer;

    vector numbersLeft(n);

    // Filling the vector with Numbers from 1 to N.

    for (int i = 0; i < n; i++)

    {

        numbersLeft[i] = i + 1;

    }

    // Decreasing k by 1 since we're using 0-Based Indexing.

    k--;

    for (int i = 0; i < n; i++)

    {

        int index, position;

        int currentN = n - i;

        int nPartial = 1;



        currentN--;

        // Calculating nPartial such that nPartial > K.

        while (k >= nPartial and currentN > 0)

        {

            nPartial *= currentN;

            currentN--;

        }



        index = k / nPartial;

        k %= nPartial;



        position = index;



        int number = numbersLeft[position];



        // Pushing this number into our answer vector.

        answer.push_back(number);



        // Erasing this number from numbersLeft vector.

        numbersLeft.erase (numbersLeft.begin() + position );

    }



    return answer;

}