  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# PERMUSEQ

Last Updated on March 25, 2022 by Ria Pathak Recursion

Hard

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given a sorted array `A` containing `N` distinct elements, your task is to find the Mth 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 :

1. Total number of `unique` permutations of `A` will be `N!`

2. So finding all such permutations and then printing Mth permutation can give `TLE` for large values of `N`.

### SOLVING APPROACH:

1. The idea is to recursively keep finding the element in the array that should appear in the Mth permutation element by element, printing it and deleting it from the original array till all the elements are not printed.

2. Interesting point is, value of `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 = 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 = 3, also delete it from current array.

A = , 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 = 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);
}
{
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];

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();