permutation generation ?

[Richard A. O'Keefe]

In article <3367 at ria.ccs.uwo.ca>, creider at cogsci.uwo.ca (Chet Creider) writes:
> Has anyone written programs which generate permutations, ideally of
> strings, not just integers, or know of a reference with algorithms?

Read chapter 13 of Dijkstra's book "A Discipline of Programming".
In fact, why not read the whole book?

If you have a permutation generator for integers, you have everything
you need.  Hint: use i and perm(i) as subscripts when copying from one
array to another.

> Please note that the problem is
> not to compute the number of permutations, but to list them.

You really don't want to do that.  There are a LOT of permutations.
Suppose your computer can generate one permutation every microsecond,
and that you're not interested in a program that runs longer than a
day.  So that's 86.4 milliard permutations.  What's the largest value
of n such that you can generate all n! permutations of n items in that
time?
	13.		(you can _almost_ fit 14 in.)

Not a lot, is it?  In consequence, there aren't a lot of applications
for listing all permutations of (1..n).

To generate all permutations of 1..n:
    Generate all the permutations of 1..(n-1), and for each of them
	try inserting n at the beginning, between adjacent pairs, at the end.
Trivial.
-- 
Q:  What should I know about quicksort?   A:  That it is *slow*.
Q:  When should I use it?  A:  When you have only 256 words of main storage.