fred@inuxc.UUCP (Fred Mendenhall) (07/21/84)
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
schang@uiucdcs.UUCP (07/21/84)
#R:inuxc:-99400:uiucdcs:24700048:000:990 uiucdcs!schang Jul 21 15:57:00 1984 [] Prolog is probably the best language to solve this problem, it took me less than 15 minutes to write and test the following : > % 'permut' returns one permutation of 'List'. It consists of taking one > % element from 'List' and then taking one permutation of the remaining > % list. > > permut(List, [Elt | Tail]) :- > pickup_one(Elt,List,Remaining), > permut( Remaining, Tail). > permut( [], []). > > pickup_one( X, [X | T], T). > pickup_one( X, [Y | T], [Y | Z]) :- > pickup_one( X, T, Z). Here is the result of the program : > > UNSW - PROLOG (IBM PC) > : permut([1,2,3], X)? > > X = [1, 2, 3] > > X = [1, 3, 2] > > X = [2, 1, 3] > > X = [2, 3, 1] > > X = [3, 1, 2] > > X = [3, 2, 1] > : ^D Thierry Schang ...!{ihnp4, pur-ee, parsec}!uiucdcs!schang Department of Computer Science University of Illinois 1304, W. Springfield Urbana, Il 61801
dmt@hocsl.UUCP (07/22/84)
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
ark@rabbit.UUCP (Andrew Koenig) (07/22/84)
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.