sorting by a partial order

sorting by a partial order

[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).  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?
TIA


paul


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: sorting by a partial order

[Thien-Thi Nguyen]

   From: prj@po.cwru.edu (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


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: sorting by a partial order

[Keith Wright]

> From: Thien-Thi Nguyen <ttn@giblet.glug.org>
> 
>    From: prj@po.cwru.edu (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  <kwright@free-comp-shop.com>

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


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: sorting by a partial order

[Thien-Thi Nguyen]

   From: Keith Wright <kwright@gis.net>
   Date: Wed, 30 Oct 2002 01:34:45 -0500

   I can't define "defines" to somebody
   confused about definitions.

that would be a feat, indeed.  i took "predicate" to refer to only the
relation, w/o the set.  if OP had used the term "poset" directly, and
not used "predicate" in the context of the less-function argument to
`sort', i would not have been (as) confused.

   Knuth calls this a topological sort.
   I'm not sure if anybody else does.

check out the tsort (GNU textutils) info page.

thi


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: sorting by a partial order

[Thien-Thi Nguyen]

   From: Thien-Thi Nguyen <ttn@giblet.glug.org>
   Date: Tue, 29 Oct 2002 23:27:49 -0800

   i would not have been (as) confused.

another area of confusion for me was "partial ordering" (poset) vs
"partial order" (relation).  i assumed these were the same.  so i guess
another answer to the OP would be: check out slib's tsort.scm.  (this is
what i should've done for THUD instead of kludging some merge-sort; live
and learn.)

thi


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: sorting by a partial order

[Paul Jarc]

Keith Wright <kwright@gis.net> wrote:
> I don't know what you have been reading, but Paul's use of "poset"

Too bad I didn't actually use that word. :)  Sorry for the confusion.
Maybe it would have been clearer if I explained that my relation means
"B depends on A", so in the result A must precede B.  This is for a
program similar to make.

> Knuth, Art of Computer Programming Vol 1, Fundamental Algorithms, 2.2.3
> calls this a topological sort.

Thanks, I'll have a look at that.

> The algoriths are short, the problem is the form in which the data
> is presented and how you need the answer.

I can put the data in any form that's convenient while gathering it.
For the answer, I need to be able to iterate through all the items in
a valid order.  Or iterate through them in an arbitrary order, and
inserting the result of processing each item at a proper spot into a
sorted list, but I guess that amounts to the same thing.

> Knuth's algorithm does the topological sort on any set of pairs
> which generates the partial order as its transitive closure.

Ok, that's almost how I have it right now.  Although it's not quite a
set of pairs - I have a hash table storing the dependencies, whose
keys are items and whose values are smaller hash tables.  The keys in
a smaller hash table are items which are the dependencies of
thecorresponding key in the large hash table.  But I can change that
if it turns out not to be convenient.

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

Not if it gives a right answer. :)


paul


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: sorting by a partial order

[rm]

On Wed, Oct 30, 2002 at 12:12:45PM -0500, Paul Jarc wrote:
> Keith Wright <kwright@gis.net> wrote:
> > I don't know what you have been reading, but Paul's use of "poset"
> 
> Too bad I didn't actually use that word. :)  Sorry for the confusion.
> Maybe it would have been clearer if I explained that my relation means
> "B depends on A", so in the result A must precede B.  This is for a
> program similar to make.

Hmm, wouldn't that be a nice place to use Schelog (Prolog in Scheme)?
If i remember correctly, i had it running under Guile without problems--
i could try and dig it up from my harddisk if you want me to.

 Ralf Mattes


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: sorting by a partial order

[Paul Jarc]

rm@fabula.de wrote:
> Hmm, wouldn't that be a nice place to use Schelog (Prolog in Scheme)?

That sounds useful.  Found it on Google:
<URL:http://www.ccs.neu.edu/home/dorai/schelog/schelog.html>


paul


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: sorting by a partial order

[Mikael Djurfeldt]

prj@po.cwru.edu (Paul Jarc) writes:

> Keith Wright <kwright@gis.net> wrote:
> > I don't know what you have been reading, but Paul's use of "poset"
> 
> Too bad I didn't actually use that word. :)  Sorry for the confusion.
> Maybe it would have been clearer if I explained that my relation means
> "B depends on A", so in the result A must precede B.  This is for a
> program similar to make.

Have a look at the "tsort" module in slib:

(use-modules (ice-9 slib))
(require 'tsort)


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user