[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

sorting by a partial order

From: Paul Jarc
Subject: sorting by a partial order
Date: Tue, 29 Oct 2002 15:33:59 -0500
User-agent: Gnus/5.090008 (Oort Gnus v0.08) Emacs/21.2 (i686-pc-linux-gnu)

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).  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.
* Can sort, stable-sort, sort-list, etc., deal with a partial order
  for the less procedure, or must it be a full ordering?
* 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.)
* 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?


reply via email to

[Prev in Thread] Current Thread [Next in Thread]