Skip to content

UVA Problem (12335) : Lexicographic Order

December 19, 2011

Problem statement:

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.

Advertisements
One Comment leave one →
  1. June 21, 2013 3:41 pm

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: