Re: sorting by a partial order

[Thien-Thi Nguyen]

   From: address@hidden (Paul Jarc)
   Date: Tue, 29 Oct 2002 15:33:59 -0500

   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 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.

ok.

   * 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.

   * How do these procedures behave if, by mistake, the ordering
     predicate (consistently) returns contradictory results?  (A is less
     than B, and B is less than A.)

there are some shuffling algorithms that use this technique.
"consistently contradictory" sounds like a self-referential oxymoron.
(kudos to the witty prof! :-)

   * 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?

(perhaps not) coincidentally, i'm looking at such code now, in lr0.scm.
it has the following citation:

 ;; This is the digraph algorithm from "Efficient Construction of
 ;; LALR(1) Lookahead Sets" by F. DeRemer and T. Pennello, in ACM
 ;; TOPLS Vol 4 No 4, October 1982.  They credit J. Eve and R. Kurki
 ;; Suonio, "On Computing the transitive closure of a relation."
 ;; Acta Inf. 8 1977.

there are more recent research efforts, too.  efficient parsing seems to
still be a hot research topic (insert gratuitous xml slam here).

thi