{"id":766,"date":"2020-06-10T08:02:44","date_gmt":"2020-06-10T08:02:44","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=766"},"modified":"2022-03-25T11:00:26","modified_gmt":"2022-03-25T11:00:26","slug":"permuseq","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/permuseq\/","title":{"rendered":"PERMUSEQ"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Recursion<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given a sorted array A<\/code> containing N<\/code> distinct elements, your task is to find the Mth<\/sup> permutation of the given array.<\/p>\n<\/blockquote>\n

For Example :<\/h4>\n
Input : \n\nN = 3, M = 5\nA = [3 4 5] \n\nOutput : 5 3 4\n\nExplanation : \n\nAll 3! = 6 permutations of the given array are\n\n1st : 3 4 5\n\n2nd : 3 5 4\n\n3rd : 4 3 5\n\n4th : 4 5 3\n\n5th : 5 3 4\n\n6th : 5 4 3<\/code><\/pre>\n
Can we use Recursion<\/code> here ?<\/em><\/strong>  <\/p>\n
\n
Yes<\/strong>, Recursion<\/code> is a good option whenever we need to find different permutations or combinations. <\/p>\n<\/blockquote>\n
OBSERVATION :<\/h3>\n
\n
    \n
  1. \n
    Total number of unique<\/code> permutations of A<\/code> will be N!<\/code>     <\/p>\n<\/li>\n
  2. \n
    So finding all such permutations and then printing Mth<\/sup> permutation can give TLE<\/code> for large values of N<\/code>.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    SOLVING APPROACH:<\/h3>\n
    \n
      \n
    1. \n
      The idea is to recursively keep finding the element in the array that should appear in the Mth<\/sup> permutation element by element, printing it and deleting it from the original array till all the elements are not printed.  <\/p>\n<\/li>\n
    2. \n
      Interesting point<\/em><\/strong> is, value of k-1<\/code> say K<\/code>, divided by the factorial of (sizeOfArray - 1)<\/code> gives us the position of the element in the array that should be currently placed in the M^{th}<\/code> 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<\/code> is reduced to K % fact<\/code> on each iteration.
      \nLet us understand it more clearly by the illustration given below.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
      <\/strong><\/u><\/a><\/p>\n
      ILLUSTRATION :<\/h3>\n
      A = [3 4 5], N = 3\nk = 5\n\nfact = factorial(N - 1) = factorial(3 - 1) = factorial(2) = 2\nK = k - 1 = 5 - 1 = 4\n\nposition = K \/ fact = 4 \/ 2 = 2\nThis gives us the index of our first element of the 5th permutation of the given array.\nPrint A[position] = A[2] = 5, also delete it from current array.\nAlso update value of K as K = K % fact = 4 % 2 = 0 => K = 0\n\nA = [3 4], N = 2\n\nfact = factorial(N - 1) = factorial(2 - 1) = factorial(1) = 1\nK = 0\n\nposition = K \/ fact = 0 \/ 1 = 0\nThis gives us the index of our next element of the 5th permutation of the given array.\nPrint A[position] = A[0] = 3, also delete it from current array.\n\nA = [3], N = 1\n\nfact = factorial(N - 1) = factorial(1 - 1) = factorial(0) = 1\nK = 0\n\nposition = K \/ fact = 0 \/ 1 = 0\nThis gives us the index of our next element of the 5th permutation of the given array.\nPrint A[position] = A[0] = 4, also delete it from current array.\n\nTherefore, 5th permutation of the array [3 4 5] is printed as => 5 3 4 <\/code><\/pre>\n
      SOLUTIONS:<\/h3>\n
      \t\t\t\t\t\t