1060 - nth Permutation

1060 - nth Permutation

Given a string of characters, we can permute the individual characters to make new strings. At first we order the string into alphabetical order. Then we start permuting it.

For example the string 'abba' gives rise to the following 6 distinct permutations in alphabetical order.

aabb 1

abab 2

abba 3

baab 4

baba 5

bbaa 6

Given a string, you have to find the n^th permutation for that string. For the above case 'aabb' is the 1^st and 'baab' is the 4^th permutation.

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case contains a non empty string of lowercase letters with length no more than 20 and an integer n (0 < n < 2³¹).

Output

For each case, output the case number and the n^th permutation. If the n^th permutation doesn't exist print 'Impossible'.

Sample Input	Output for Sample Input
3 aabb 1 aabb 6 aabb 7	Case 1: aabb Case 2: bbaa Case 3: Impossible

---

-----------------------------------------------EDITORIAL ---------------------------------

 THIS PROBLEM CAN BE SOLVED RECURSIVELY ..

  FIRST  OF ALL WE CHECK MAXIMUM NUMBER OF PERMUTATIONS POSSIBLE FROM THE  GIVEN STRING ... IF IT IS < N THAN ANS IS IMPOSSIBLE , ELSE

NOW WE HAVE TO FIX  CHARACTER AT EACH POSITION STARTING FROM MSB POSITION ,

FOR FIXING THE CHARACTER AT ANY POSITION INITIALLY WE TRY TO FIX SMALLEST CHARACTER AT THAT POSITION IF BY PLACING THAT CHARACTER NUMBER OF PERMUTATION FORMED >=  REMAINING REQUIRED   PERMUTATION THAN FIX THIS CHARTER AT THAT POSITION , AND DECREASE THE FREQUENCY OF THIS CHARACTER SINCE THIS CHARACTER  IS USED AT THIS POSITION AND MOVE TO NEXT POSITION , ELSE IF NO OF PERMUTATION FORMED BY PLACING THIS CHARACTER IS LESS THAN THE REQUIRED REMAINING PERMUTATION THAN DECREASE REMAINING PERMUTATION   BY THE NUMBER OF PERMUTATION FORMED BY PLACING THIS CHARACTER AT THAT POSITION ( SINCE  THIS COUNT TIMES NUMBER OF PERMUTATIONS COMES IN BETWEEN CURRENT TO FINAL PERMUTATION ) AND TRY TO FIND NEXT CHARACTER FOR THIS POSITION,.....

SEE THE CODE FOR CLARITY 

----------------------------------------CODE-------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

string s,build;

int cnt[30];

lli  ncr[25][25];

int len;

// return number of  permutation possible from given n number of characters 

lli count(int n)

 {

    lli ret = 1;

    

    for (int i = 0; i < 26; i++) 

{

        ret *= ncr[n][cnt[i]];

        n -= cnt[i];

   

    }

    return ret;

}

int solve(int cur_pos,int rem_perm)

 {

  if(cur_pos>len)

    {

      printf("\n");

      return 0;

  }

  else

   {

    int i;

       for( i=0;i<=25;i++)

        {

          if(cnt[i])

           {

             cnt[i]--;

             lli use=count(len-cur_pos);

              if(use>=rem_perm) 

                                 {

                                //  if by fixing this character at current position permutation will >= remaining

                               //  k than  we can  use this character at this position

              break;

                                   }

                          

               cnt[i]++;//  since we are not using  i as the character at curent_pos so again                                          //increase its count

                rem_perm-=use;//  decrease number of remaining  perm 

  }

   }

    printf("%c",(char)(i+'a'));

    solve(cur_pos+1,rem_perm);

   }

 }

int main()

 {

 

  int t;

  int cas=1;

  for(int i=0;i<=20;i++)

   {

     ncr[i][0]=1;

     ncr[i][i]=1;

     for(int j=1;j<i;j++)

      {

       ncr[i][j]=ncr[i-1][j]+ncr[i-1][j-1];

}

  }

  

  scanf("%d",&t);

  while(t--)

   {

    int n;

     cin>>s>>n;

   

    memset(cnt,0,sizeof cnt);

     len=s.length();

     for(int i=0;i<len;i++)

        {

       cnt[s[i]-'a']++;

   }

    if(count(len)<n)

    {

     printf("Case %d: ",cas++);

     printf("Impossible\n");

}

        

        else

          {

           printf("Case %d: ",cas++);

          solve(1,n);

            

  }

  }

 

 }