[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: sorting by a partial order
From: |
Thien-Thi Nguyen |
Subject: |
Re: sorting by a partial order |
Date: |
Tue, 29 Oct 2002 19:23:03 -0800 |
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