[Tutor] Sequence Comparison [prefixes come first!]

[Danny Yoo]

On Wed, 14 Jan 2004, Isr Gish wrote:

> Magnus Lycka wrote:
>
>    >> >>> (1, 2)                 < (1, 2, -1)
>    >> True
>    >> # i totally didnot understand it
>    >
>    >Anything is more than nothing... Why is that difficult
>    >to understand.
>
>   I would rather think that -1 which is less then 0 whould be less then
> nothing.

Hi Isr,


Unfortunately, this reason doesn't generalize well if that third component
is positive.  It's also true that (1, 2) < (1, 2, 42).


Lexicographic ordering should be a very familiar concept.  English
dictionaries follow the same method of ordering words.

If you're on a Unix system, here's a brute-force way to see some examples:

###
words = [w.strip() for w in open('/usr/share/dict/words')]
words.sort()
i = 0
while i < len(words):
    for j in range(i+1, len(words)):
        if words[j].startswith(words[i]):
            print words[i], words[j]
        else:
            break
    i = i + 1
###

I know there must be a smarter way to do this, but I'm lazy, and it's
late... *grin*


Here's a selection of what the program picks out:

    aft    afterburner
    thin thingumbob
    woo    wooden
    wrist  wristband
    yore   yoretime

In all these cases, the left word is a 'prefix' of the right word.  In
summary: prefixes come first.  *grin*


Because of our experience looking up words in a dictionary, we know that
'aft' comes before 'afterburner'.  It's not something arbitrary, but a
systematic way that we use to sort our words.

If this makes sense, then it's just a matter of crossing our eyes a little
to see that

     (1, 2) < (1, 2, -1)

is the same thing, just in a different domain.  Instead of comparing
"letter-by-letter", we're comparing element by element.


Hope this helps!