PERMUSEQ

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 :

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

2. So finding all such permutations and then printing M^th 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 M^th 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[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));
  }
}

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.