Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!batcomputer!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.c
Subject: Re: permutation generation ?
Message-ID: <6370@goanna.cs.rmit.oz.au>
Date: 17 Jun 91 12:27:18 GMT
References: <3367@ria.ccs.uwo.ca>
Distribution: comp.lang.c
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 32

In article <3367@ria.ccs.uwo.ca>, creider@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.