lexicographic order

[Scorvus]

can anyone tell how the lexicographic order work? I'm trying to solve this problem but got stumped by lexicographic order
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=121&page=show_problem&problem=882

[Ispil]

Alphabetical. It used the permutation of ABC as an example; which, as you can see, is in alphabetical order (abc, acb, bac, bca, cab, cba).

[Scorvus]

hmm how does acb become bac? shouldn't it become bca?

[andywestken]

"lexicographic order" is another name for "dictionary order" and "alphabetical order", if that helps.

(The wikipedia.org entry does mention this just before disappearing into set theory...)

So for the simple example they use in the problem you've provided the link to, abc; it's permutions are, in alphabetic order:

  0 - abc
  1 - acb
  2 - bac
  3 - bca
  4 - cab
  5 - cba

This is, they are ordered as if you had sorted the whole lot on the first letter according to a < b < c < ... (assuming we want ascending order)

  0 - abc  (a < b < c)
  1 - acb
  2 - bac
  3 - bca
  4 - cab
  5 - cba

Then for each group beginning with the same letter, you sorted the group by the second letter

  0 - abc  (b < c)
  1 - acb

  2 - bac  (a < c)
  3 - bca

  4 - cab  (a < b)
  5 - cba

Then for each group beginning with the same first two letters, you sort them by the third (but we've run out of letters here.)

And so on, until you run out of letter (counting no letter as less than 'a')

Andy

Lexicographical order
http://en.wikipedia.org/wiki/Lexicographical_order

[Scorvus]

I'm sorry,but I still don't understand how acb become bac and how bca become cab. May be you explain me what you mean with this?

Then for each group beginning with the first two letters, you sort them by the third

[andywestken]

Sorry, that should have read "the same first two letters.

Andy

[Scorvus]

What do you mean by sort them by the third? Is the same first two letter is from right to left?