From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Thien-Thi Nguyen Newsgroups: gmane.lisp.guile.user Subject: Re: sorting by a partial order Date: Tue, 29 Oct 2002 19:23:03 -0800 Sender: guile-user-admin@gnu.org Message-ID: References: Reply-To: ttn@glug.org NNTP-Posting-Host: main.gmane.org X-Trace: main.gmane.org 1035949018 3810 80.91.224.249 (30 Oct 2002 03:36:58 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Wed, 30 Oct 2002 03:36:58 +0000 (UTC) Cc: guile-user@gnu.org 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 186jf4-0000z3-00 for ; Wed, 30 Oct 2002 04:36:54 +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 186jen-0007Js-00; Tue, 29 Oct 2002 22:36:37 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.10) id 186je9-0005gv-00 for guile-user@gnu.org; Tue, 29 Oct 2002 22:35:57 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.10) id 186je2-0005FR-00 for guile-user@gnu.org; Tue, 29 Oct 2002 22:35:54 -0500 Original-Received: from ca-crlsca-cuda3-c6a-b-211.crlsca.adelphia.net ([68.71.15.211] helo=giblet) by monty-python.gnu.org with esmtp (Exim 4.10) id 186je0-0005AI-00 for guile-user@gnu.org; Tue, 29 Oct 2002 22:35:48 -0500 Original-Received: from ttn by giblet with local (Exim 3.35 #1 (Debian)) id 186jRf-0003pY-00; Tue, 29 Oct 2002 19:23:03 -0800 Original-To: prj@po.cwru.edu In-reply-to: (prj@po.cwru.edu) 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:1302 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.user:1302 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