From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Keith Wright Newsgroups: gmane.lisp.guile.user Subject: Re: sorting by a partial order Date: Wed, 30 Oct 2002 01:34:45 -0500 Sender: guile-user-admin@gnu.org Message-ID: <200210300634.g9U6Yj401336@fcs9.free-comp-shop.com> References: NNTP-Posting-Host: main.gmane.org X-Trace: main.gmane.org 1035960321 25073 80.91.224.249 (30 Oct 2002 06:45:21 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Wed, 30 Oct 2002 06:45:21 +0000 (UTC) Return-path: Original-Received: from monty-python.gnu.org ([199.232.76.173]) by main.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 186mbO-0006W7-00 for ; Wed, 30 Oct 2002 07:45:18 +0100 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.10) id 186mWa-0005Jr-00; Wed, 30 Oct 2002 01:40:20 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.10) id 186mWF-00057R-00 for guile-user@gnu.org; Wed, 30 Oct 2002 01:39:59 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.10) id 186mWA-000566-00 for guile-user@gnu.org; Wed, 30 Oct 2002 01:39:58 -0500 Original-Received: from mx03.gis.net ([208.218.130.11] helo=gis.net) by monty-python.gnu.org with esmtp (Exim 4.10) id 186mW9-00054h-00 for guile-user@gnu.org; Wed, 30 Oct 2002 01:39:54 -0500 Original-Received: from fcs9.free-comp-shop.com ([67.30.180.166]) by mx03.gis.net; Wed, 30 Oct 2002 01:39:45 -0500 Original-Received: (from kwright@localhost) by fcs9.free-comp-shop.com (8.11.2/8.11.2) id g9U6Yj401336; Wed, 30 Oct 2002 01:34:45 -0500 X-Authentication-Warning: fcs9.free-comp-shop.com: kwright set sender to kwright@gis.net using -f Original-To: guile-user@gnu.org In-reply-to: (message from Thien-Thi Nguyen on Tue, 29 Oct 2002 19:23:03 -0800) X-Rcpt-To: Errors-To: guile-user-admin@gnu.org X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.0.11 Precedence: bulk List-Help: List-Post: List-Subscribe: , List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: Xref: main.gmane.org gmane.lisp.guile.user:1303 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.user:1303 > From: Thien-Thi Nguyen > > 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 Programmer in Chief, Free Computer Shop --- Food, Shelter, Source code. --- _______________________________________________ Guile-user mailing list Guile-user@gnu.org http://mail.gnu.org/mailman/listinfo/guile-user