K-th Permutation Sequence Of First N Natural Numbers

1. 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].
2. Call the recursive function ‘kthPermutationHelper’ with parameters: integer i, an array v, integer N, and a 2 Dimensional array named ‘answer’.
3. Base case: if ‘i’ equal to N, then simply push ‘v’(a permutation of N) into ‘answer’ and return.
4. Now we make a boolean array named ‘visited’ of size N+1 to mark the occurrences. Initially, we’ll fill this array with 0.
5. Then mark all the numbers visited, which are present in the array ‘v’.
6. 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.

1. We start by making an array named ‘answer’, which will store the Kth permutation.
2. Then we’ll make an array named ‘numbersLeft’ and we’ll store all values from 1 till N inside this array.
3. 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.

1. 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).
2. 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)!
3. 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)!.
4. We keep doing the above steps till only one number is left.

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

1. Let’s take N = 4 {1,2,3,4} and K = 8
2. 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}
3. 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}
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}
5. Clearly, 4 will be the final digit in the 8th sequence since only 4 is left in the set.
6. Therefore our final answer(8th sequence) is 2 1 4 3.