Message-ID: <994@inuxc.UUCP>
Date: Fri, 20-Jul-84 17:21:51 EDT
Article-I.D.: inuxc.994
Posted: Fri Jul 20 17:21:51 1984
Date-Received: Sat, 21-Jul-84 04:38:51 EDT
Organization: AT&T Consumer Products Div., Indianapolis
Lines: 24


	Here is a interesting problem that has annoyed me all
afternoon. I thought I might post it to the net
and see what solutions some of you midnight hackers come up with.

	" Given an array of n unique elements, print every possible
	  permutation of the array."
	(eg the array (1,2,3) would cause the following to be printed
		123
		132
		312
		321
		231
		213)
		
For the sake of discussion lets say that n can range from 1 to 20, 
and lets talk about solutions using basic, pascal, forth, or lisp.

	My bet is that lisp will generate the most elegant solution
to this problem, if I can figure out how to program the stupid thing.

				
				Fred Mendenhall
				AT&T CP

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

Message-ID: <2998@rabbit.UUCP>
Date: Sun, 22-Jul-84 10:48:48 EDT
Article-I.D.: rabbit.2998
Posted: Sun Jul 22 10:48:48 1984
Date-Received: Mon, 23-Jul-84 02:14:42 EDT
References: <145@hocsl.UUCP>
Organization: AT&T Bell Laboratories, Murray Hill
Lines: 10

A beatiful solution appears in Dijkstra's "A Discipline of Programming."
It is expressed as a program fragement to transform a given permutation
into its successor.  Thus, if applied repeatedly, the program will
generate all permutations.  The program is non-recursive, so it can
easily be implemented in any language, and saves no state information
aside from the actual permutation.

Unfortunately, I don't have a copy of the book handy right now, and
it's been a few years since I've seen this particular algorithm,
so I don't remember it exactly.  If I reconstruct it, I'll post it.