Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.PCS 1/10/84; site hocsl.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxl!houxm!hogpc!pegasus!hocsl!dmt
From: dmt@hocsl.UUCP
Newsgroups: net.micro.pc
Subject: Re: Programing Puzzle
Message-ID: <145@hocsl.UUCP>
Date: Sat, 21-Jul-84 22:11:47 EDT
Article-I.D.: hocsl.145
Posted: Sat Jul 21 22:11:47 1984
Date-Received: Sun, 22-Jul-84 06:11:59 EDT
References: <994@inuxc.UUCP>
Organization: AT&T Information Systems Labs, Holmdel NJ
Lines: 32

REFERENCE:  <994@inuxc.UUCP>

Re: generating all permutations of a list.

I also suspect that Lisp will give the most elegant solution.
However, it's been so long since I've programmed in Lisp, that
I'd have to describe my algorithm in pseudo-code.

To Generate All Permutations Of A List:
If the list is a unit, you've got it [obviously].
Otherwise "slide" the first element through ALL PERMUTATIONS
	of the rest of the elements.  That is, for each permutation
	of the n-1 elements, generate the lists with the extra element
	first, second,....,last (for a total of n new lists).
You get the permutations of the n-1 elements by recursing the same
	procedure.
Example:
	list=123
	slide 1 thru all permutations of 23 [= 23, 32]
	123, 213, 231
	132, 312, 321

Three irreverent questions occur to me:
1-	Why am I doing this on Saturday night?
2-	Why am I doing this, when I'm sure Knuth has at least
	17 better solutions if I only had it handy?
3-	Since the problem specified for n<=20, how long would
	it take (and how much storage for an in-core Lisp) to
	generate all 10**17 permutations of a 20-element list?

'Night all!
Dave Tutelman  -  AT&TIS Holmdel