What exactly is "lexicographical order"?

[zacharyleung]

There are quite a few questions where we are required to print the lexicographically smallest answer. Is there a good way in general to get this smallest answer? Problems that are like this include 116, 10026...

[shamim]

Well one thing i can tell you is there is no general way because some problem redefine the meaning of lexicographically. For example, in problem 195, the lexicographical order is AaBbCc....WwYyZz, eventhough if we did ASCII comparison it would be ABC...WYZabc...wyz.

[miras]

heh...

[sohel]

a string A is lexicographically smaller than a string B
if( strcmp(A, B) < 0 );

eg. AB is smaller than Aa....

For alphabetically sorted string is :
AaBbCcDd.........

and so Aa is alphabetically smaller than AB.

[CDiMa]

From what I know :

a string A is lexicographically smaller than a string B
if( strcmp(A, B) < 0 );

EG: AB is smaller than Aa....

For alphabetically: sorted string is :
AaBbCcDd.........

and so Aa is alphabetically smaller than AB.

What you are explaining is a particular case of lexicographic order.

Lexicographic means that you sort different objects considering first an attribute ranked the most important.
If you have a tie for the most important attribute you further sort checking the second ranked attribute and so on until you find an attribute that distinguishes the two objects.

To sort lexicographically you need to specify an ordered list of attributes and a sort order for the elements of each attribute.

The most usual implementation of a lexicographic order is the classic dictionary order.
The list of attrbutes is (first letter, second letter, third letter, etc.) and the sort order for each attribute is the alphabetical order.

And for numbers : maintain an ascending order..
111 is larger than 22 ( I think ).

111 is smaller that 22 in the classical lexicographic order since its first cypher (1) is smaller than the first cypher of 22.

About the original question, the best way to find the smallest lexicographical solution is to generate the solutions in lexicographical order

Ciao!!!

Claudio