### lexicographic order

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
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).
hmm how does acb become bac? shouldn't it become bca?
"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
Last edited on
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
Last edited on
Sorry, that should have read "the same first two letters.

Andy
Last edited on
What do you mean by sort them by the third? Is the same first two letter is from right to left?
Topic archived. No new replies allowed.