Re: Generation of permutations

[dewar@gnat.com (Robert Dewar)]

"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.