Page 1 of 1
What exactly is "lexicographical order"?
Posted: Sat Mar 20, 2004 10:10 am
by 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...
Posted: Sat Mar 20, 2004 11:50 am
by 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.
Posted: Mon Mar 22, 2004 2:16 pm
by miras
heh...
huh
Posted: Tue Mar 23, 2004 8:06 am
by 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.
Re: huh
Posted: Tue Mar 23, 2004 10:41 am
by CDiMa
sohel wrote: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.
sohel wrote: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