creider@cogsci.uwo.ca (Chet Creider) (06/13/91)
Has anyone written programs which generate permutations, ideally of strings, not just integers, or know of a reference with algorithms? An earlier request to sci.math.stats elicited no replies, but maybe those readers are not programmers. Please note that the problem is not to compute the number of permutations, but to list them. There is a initial treatment, for integers only and for P(n,n) only, in Kruse, Leung and Tondo, *Data Structures and Program Design in C*. Many thanks, Chet Creider <creider@cogsci.uwo.ca> or <creider@csd.uwo.ca>
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (06/17/91)
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.