# UVA Problem (12335) : Lexicographic Order

This problem is a adhoc problem. In this problem you need generate the lexicographic smallest

permutation given a permutation and it’s lexicographic order.

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, x= current_lexographic_order;

= 11

So consider the input –

bdac 11

So start with first character b,

x= x % factorial(current examining string length)

= 11%factorial(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,

So A[1]=b,

So,

_______***_______________

| () | b | () | () |

|_____|_____|_____|______|

A[0] A[1] A[2] A[3]

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) .

___________________***__

| () | b | () | d |

|_____|_____|_____|______|

A[0] A[1] A[2] A[3]

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;

So now-

_________________________

| a | b | () | d |

|_____|_____|_____|______|

A[0] A[1] A[2] A[3]

And then lasr the remaining element (c), place it in the empty position, here it is A[2].

So overall array looks like-

___________***______

a b c d

____________________

A[0] A[1] A[2] A[3]

Hope it’s understandable.

Please leave a comment so that i can add more solution, because inspiration lies behind everything.

For any query email me salimsazzad222@gmail.com.

Really a nice tricks! I found your blog while searching for UVA 10891 and found this blog with some good articles !! Carry on !