🚀 go-pugleaf

boehm@parc.xerox.com (Hans Boehm) writes:

>gudeman@cs.arizona.edu (David Gudeman) writes:

>>In article  <1991Apr22.153149.8082@newcastle.ac.uk> Chris Holt writes:
[about sorting using a partial order relation as a parameter]

>>I know that is the standard solution, but I wonder if a better
>>solution wouldn't be a function $ord : D -> Int$ that maps domain
>>objects into arbitrary integers with the property that if $d1 < d2$
>>by the partial order, then $ord(d1) < ord(d2)$.  ($d1 < d2$ means that
>>$d1 <= d2$ and $d1 =/= d2$.)

>There is no such function mapping character strings to integers.  Note
>that "a" < "aa" < "aaa" < ...infinitely many strings... < "b".  No subset
>of the integers has this property.  See any set theory book for a
>discussion of transfinite ordinals.

There can be a such a function for the finite strings; you use
the lengths of the strings, so
  a < b < ... < z < aa < ab < ... az < ba < bb < (rest of 2-sequences)
    < (3-sequences) < (4-sequences) etc.
Agreed the ordering given by Hans Boehm requires a dense codomain,
but again the rationals are dense, and so can handle finite and
repeating strings, and they can be mapped to the integers (though
without the obvious ordering being preserved).

A partial order can always be strengthened to a total order, of
course; but one thing I wondered as I decided to make my example
partial is, must every algorithm for partial order sorting be
at least o(n**2)?
-----------------------------------------------------------------------------
 Chris.Holt@newcastle.ac.uk      Computing Lab, U of Newcastle upon Tyne, UK
-----------------------------------------------------------------------------
 "And when they die by thousands why, he laughs like anything." G Chesterton