12335

Problem Solving Head start:

Discussion is quoted from this link:

So before proceed recall,if a<b<c<d and string is- abcd, there are 24 permutation,where

1-6 permutation start with smallest, here a.
7-12 permutation start with second smallest, here b.
13-18 permutation start with third smallest, here c.
19-24 permutation start with fourth smallest, here d.

lets Define, order= current_lexographic_order;
= 11

So consider the input –

bdac 11

So start with first character b,

order= order % factorial(current examining string length)
= 11%fact(4)
= 11%24
=11;

So from it is clear that if (b)dac in lexographically 11’th smallest permutation,
then b is second smallest element,

bcoz it fall’s in range between 7-12,

Next remain, (d)ac, there are 6 permutation

1-2 permutation start with smallest.
3-4 permutation start with second smallest.
5-6 permutation start with third smallest.

(d)ac is 5’th smallest permutation, How we do we know this??? Since bdac in lexographically
11’th smallest permutation ,string starting with b starts from 7, so 7,8,9,10,(11), 5’th smallest permutation.

By calculation-

x=x % factorial(current examining string length)
= 11%factorial(3)
= 11%6
=5;

SO d goes to last position among d,a,c (empty position in array) .

Next remain, (a)c, there are 2 permutation

1 permutation start with smallest.
2 permutation start with second smallest.

(a)c which is 1’th smallest permutation. So a goes before c.How? same thing.

x=x % factorial(current examining string length)
= 5%factorial(2)
= 5%2
=1;

Solution:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <map>
#include <fstream>

#define ul unsigned long long

using namespace std;

//map<int,int>
char trace[21];
ul mp[21];
char np[21];

int main()
{
	int t,kase=1,n;
	string str,r;

	ul k,permute;

	mp[1]=1;
	mp[2]=2;
	mp[3]=6;
	mp[4]=24;
	mp[5]=120;
	mp[6]=720;
	mp[7]=5040;
	mp[8]=40320;
	mp[9]=362880;
	mp[10]=3628800;
	mp[11]=39916800;
	mp[12]=479001600;
	mp[13]=6227020800;
	mp[14]=87178291200;
	mp[15]=1307674368000;
	mp[16]=20922789888000;
	mp[17]=355687428096000;
	mp[18]=6402373705728000;
	mp[19]=121645100408832000;
	mp[20]=2432902008176640000;

	cin>>t;

	while(t--)
	{

		cin>>str;
		cin>>k;

		n=str.size();
		for(int i=0;i<n;i++)
		trace[i]='-';
		int m=n;
		//k= mp[n]-k-1;
		//cout<<k;
		int pos;
		ul numGroup;
		r="";
		/*
		Permutation or tha rank of a seuence.
		*/
		/*
		for(int i=n-1;i>=1;i--)
		{
			numGroup=mp[i];
			pos=k/numGroup;
			r.append(1u,str[pos]);
			str.erase(pos,1);
			k=k%numGroup;
		}

		r.append(1u,str[0]);
		cout<<r<<"\n";
		*/
		int x=0;
		k--;
		while(1)
		{
			k=k%mp[m];
			char ch = str[x];
			pos =k/(mp[m]/m);

			int cnt=0;

			for(int i=0;i<n;i++)
			{
				if(trace[i]=='-')
				cnt++;

				if(cnt==(pos+1))
				{
					//pos=i;
					trace[i]=ch;
					break;
				}

			}

			str.erase(0,1);
			m=str.size();
			if(m==0)
			break;
		}
		cout<<"Case "<<kase++<<": ";
		for(int j=0;j<n;j++)
		cout<<trace[j];
		cout<<"\n";
	}

	return 0;
}

 

So A[1]=b,