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

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

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



So A[1]=b,



Leave a Reply

Your email address will not be published. Required fields are marked *