Re: sorting by a partial order

[Keith Wright]

> From: Thien-Thi Nguyen <address@hidden>
> 
>    From: address@hidden (Paul Jarc)
> 
>    I have a two-place predicate that defines a partial order (i.e., it is
>    possible that neither is A less than B nor is B less than A).
> 
> this use of "partial order" is different from what i've read
> about in the sorting literature.  a "poset" (partial order set)
> is not defined by a predicate if the number of "places" in that
> predicate is less than the number of items in the set, even
> though the set may indeed be in partial order.  i guess i'm
> confused about the word "defines" here.

I don't know what you have been reading, but Paul's use of "poset"
is in exact agreement with the standard mathematical definition
for most of a century, to wit: a poset is a set 'S' together
with a binary relation '<=' which is reflexive (x<=x),
antisymetric (if x<=y & y<=x then x=y), and transitive
(if x<=y & y<=z then x<=y).  I can't define "defines" to somebody
confused about definitions.

>    I want to sort a sequence of items according to that predicate, so
>    that if A occurs before B in the result, then B is not less than A
>    according to the predicate.

Knuth, Art of Computer Programming Vol 1, Fundamental Algorithms, 2.2.3
calls this a topological sort.  I'm not sure if anybody else does.

>    * Can sort, stable-sort, sort-list, etc., deal with a partial order
>      for the less procedure, or must it be a full ordering?
> 
> here i am again confused about using "partial order" to describe the
> predicate.

I'm not confused, but I don't know the answer.  A glance at the
source---the comments say it uses quick sort, which works by
recursively choosing an item and partitioning the array into those
less than and those greater (or not less than) the chosen item.
My guess is that would not work unless given a total order.
At best it would take very careful programming to make it work,
so if the author, who writes beautiful comments, does not brag
about doing it, it's probably because he never thought of doing it.

>    * My predicate is actually not quite a partial order because it is
>      not transitive.  Is there any existing code for constructing the
>      transitive closure of a relation?

I think that's harder than sorting (in terms of running time, not
programming difficulty).  The algoriths are short, the problem
is the form in which the data is presented and how you need the
answer.  Knuth's algorithm does the topological sort on any set
of pairs which generates the partial order as its transitive
closure.  It is surely more efficent to do this, starting with
as few pairs as possible, than to try to pump it up to the transitive
closure before beginning.  You do need to be able to store a
table of size proportional to the number of pairs of item related
by <= and to loop through all items, is that a problem?

-- 
     -- Keith Wright  <address@hidden>

Programmer in Chief, Free Computer Shop <http://www.free-comp-shop.com>
         ---  Food, Shelter, Source code.  ---