Last Updated on March 25, 2022 by Ria Pathak

### CONCEPTS USED:

Recursion

### DIFFICULTY LEVEL:

Hard

### PROBLEM STATEMENT`(`

SIMPLIFIED`)`

:

Given a sorted array

`A`

containing`N`

distinct elements, your task is to find the M^{th}permutation of the given array.

#### For Example :

```
Input :
N = 3, M = 5
A = [3 4 5]
Output : 5 3 4
Explanation :
All 3! = 6 permutations of the given array are
1st : 3 4 5
2nd : 3 5 4
3rd : 4 3 5
4th : 4 5 3
5th : 5 3 4
6th : 5 4 3
```

*Can we use Recursion here ?*

Yes,`Recursion`

is a good option whenever we need to find different permutations or combinations.

### OBSERVATION :

Total number of

`unique`

permutations of`A`

will be`N!`

So finding all such permutations and then printing M

^{th}permutation can give`TLE`

for large values of`N`

.

### SOLVING APPROACH:

The idea is to recursively keep finding the element in the array that should appear in the M

^{th}permutation element by element, printing it and deleting it from the original array till all the elements are not printed.

is, value ofInteresting point`k-1`

say`K`

, divided by the`factorial of (sizeOfArray - 1)`

gives us the position of the element in the array that should be currently placed in the`M^{th}`

permutation of the array. We can find the position, print the element and delete it from the original array and Similarly positions of all such elements can be calculated one after the other, value of`K`

is reduced to`K % fact`

on each iteration.

Let us understand it more clearly by the illustration given below.

**See original problem statement here**

### ILLUSTRATION :

```
A = [3 4 5], N = 3
k = 5
fact = factorial(N - 1) = factorial(3 - 1) = factorial(2) = 2
K = k - 1 = 5 - 1 = 4
position = K / fact = 4 / 2 = 2
This gives us the index of our first element of the 5th permutation of the given array.
Print A[position] = A[2] = 5, also delete it from current array.
Also update value of K as K = K % fact = 4 % 2 = 0 => K = 0
A = [3 4], N = 2
fact = factorial(N - 1) = factorial(2 - 1) = factorial(1) = 1
K = 0
position = K / fact = 0 / 1 = 0
This gives us the index of our next element of the 5th permutation of the given array.
Print A[position] = A[0] = 3, also delete it from current array.
A = [3], N = 1
fact = factorial(N - 1) = factorial(1 - 1) = factorial(0) = 1
K = 0
position = K / fact = 0 / 1 = 0
This gives us the index of our next element of the 5th permutation of the given array.
Print A[position] = A[0] = 4, also delete it from current array.
Therefore, 5th permutation of the array [3 4 5] is printed as => 5 3 4
```

### SOLUTIONS:

include <bits/stdc++.h> using namespace std; /* function for finding factorial of a number */ int fact(int n) { if(n==0) return 1; return n*fact(n-1); } string answer(vector<int> &v, int k) { int A=v.size(); if(A==0) return ""; /* finding factorial of size - 1 */ int f = fact(A-1); /* finding the position index of the element to be placed first */ int pos = k/f; k = k % f; /* converting element to be placed first into string */ string str = to_string(v[pos]); /* deleting the found element from the array */ v.erase(v.begin() + pos); /* print the element that should be placed first and recursively find all such elements */ return str + " " + answer(v, k); } int main() { int n,k; cin>>n>>k; vector<int>v(n,0); for(int i=0;i<n;i++) cin>>v[i]; cout << answer(v, k-1); return 0; }

import java.util.*; import java.io.*; public class Main { /* function for finding factorial of a number */ static int fact(int n) { if(n==0) return 1; return n*fact(n-1); } static String answer(ArrayList<Integer> v, int k) { int A=v.size(); if(A==0) return ""; /* finding factorial of size - 1 */ int f = fact(A-1); /* finding the position index of the element to be placed first */ int pos = k/f; k = k % f; /* converting element to be placed first into string */ String str = Integer.toString(v.get(pos)); /* deleting the found element from the array */ v.remove(pos); /* print the element that should be placed first and recursively find all such elements */ return str + " " + answer(v, k); } public static void main(String args[]) throws IOException { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); ArrayList<Integer> v = new ArrayList<Integer>(n); for(int i=0;i<n;i++){ int temp = sc.nextInt(); v.add(temp); } System.out.println(answer(v, k-1)); } }

[forminator_quiz id="775"]

This article tried to discuss Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion you can check out MYCODE | Competitive Programming.