Anonymous user
Talk:Order two numerical lists: Difference between revisions
→Lexicographic order
(boundary conditions) |
|||
Line 60:
: No. "Lexicographic" only refers to the list as whole, not when comparing its individual elements. The elements are compared by whatever is natural, which probably means numerical comparison function (100 > 11, 11 > 2). --[[User:Ledrug|Ledrug]] 04:33, 30 November 2011 (UTC)
:: Well that wasn't clear. So doesn't that imply no padding? --[[User:Dgamey|Dgamey]] 04:47, 30 November 2011 (UTC)
::: Hmm?
::: Lexicographic comparison of two lists meaning comparing corresponding elements from either list, ''probably'' from left to right, and the ordering of the first unequal pair decides the ordering of the two lists. The elements need to be comparable and have good ordering. Say the lists are strings "ax" and "ay", the most natural ordering is "ax" < "ay". When comparing "ax" and "aY", depends on what comparison function you use for letters, it could be "ax" < "aY" if using case insensitive cmp, or "ax" > "aY" if comparing ASCII code case sensitively. Comparison function of strings is lexicographic, that of the letters is not: it can be whatever that has a good ordering. Replace "letters" with "numbers", "comparing letters" with "comparing numbers", and you lexicographically compare list of numerical values.
::: When two lists are of different lengths, "comparing corresponding elements" needs clarification when one list runs out. One way is, conceptually, you can pad the shorter list with some default value so they are equal length again. For strings, this default value may be considered as code point 0, so comparing "ab" to "abcde" can be considered as the same between "ab\0\0\0" and "abcde". It's convenient and practical most of the time, but if you were to pad strings with odd stuff like "W", you could still have well ordered comparisons, it's just not going to be terribly intuitive (imagine a diction where "abT" < "ab" = "abW" < "abX"). --[[User:Ledrug|Ledrug]] 05:48, 30 November 2011 (UTC)
| |||