From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,c42dbf68f5320193
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2002-05-02 05:32:12 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!postnews1.google.com!not-for-mail
From: dewar@gnat.com (Robert Dewar)
Newsgroups: comp.lang.ada
Subject: Re: Generation of permutations
Date: 2 May 2002 05:32:11 -0700
Organization: http://groups.google.com/
Message-ID: <5ee5b646.0205020432.30c71bee@posting.google.com>
References: <aajce7$7jb$1@snipp.uninett.no>
 <4519e058.0204300552.15317df9@posting.google.com>
 <aam989$99c$1@nh.pace.co.uk>
NNTP-Posting-Host: 205.232.38.244
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1020342732 9959 127.0.0.1 (2 May 2002 12:32:12
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: 2 May 2002 12:32:12 GMT
Xref: archiver1.google.com comp.lang.ada:23404
Date: 2002-05-02T12:32:12+00:00
List-Id: <comp.lang.ada>

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in message news:<aam989$99c$1@nh.pace.co.uk>...

> I once did it for an article in "Ada Letters" called "Junk Facts And The
> Slowsort". (My resume says that was Ada Letters, Vol 10, Num 1, if that's
> any help.) It was a *really* slow sorting algorithm. Unfortunately that was
> so long ago I don't have the code around anymore.

The sorting algorithm that looks like

  pick x in permutations (s) | sorted (s)

is of course fundamentally well known. See Jack Schwartz "On Programming"
(Courant Institute, early 1970's) for a discussion of how this algorithm
can be automatically transformed into more efficient algorithms. For a more
formal discussion of such transformations, see Susan Merrit's Phd Thesis
(Courant Institute, sometime in the early 90's, NYU, I was the advisor).
Also see Robert Paige's work on formal differentiation systems for an
actual implementation of this and similar transformations.

In a certain sense, the above "program" is not just an implementation of
sorting, it is a fundamental definition of what sorting means.