Permutation generation methods. (English) Zbl 0358.05003
This paper surveys the numerous methods that have been proposed for permutation enumeration by computer. The various algorithms which have been developed over the years are described in detail, and implemented in a modern ALGOL-like
language. All of the algorithms are derived from one simple control structure. The problems involved with implementing the best of the algorithms on real computers are treated in detail. Assembly-language programs are derived and analyzed fully. The paper is intended not only as a survey of permutation generation methods, but also as a tutorial on how to compare a number of different
algorithms for the same task. Among the methods discussed are those due to Heap, Wells, Boothroyd, Johnson, Trother, Ehrlich, Dershewitz, Ives, Tompkins, Paige, Peck and Schrack, Pike, Pleszczynzki, Langdon, Ord-Smith, Fischer and Krause, Schreck and Shimrat, Shen, Phillips, Dijkstra, Lehmer, and Durstenfeld. Included are algorithms for generating random permutations and for generating permutations according to a
hexicographic ordering. The paper begins with simple algorithms that generate permutations by successively exchanging elements; these algorithms all have a common control structure. Then a few older algorithms are considered in the framework of the same control structure including some based on elementary operations other than exchanges. Finally, the implementation, analysis, and “optimization” of the best of the algorithms are considered in detail.
Reviewer: Robert Sedgewick
MSC:
05A05 | Permutations, words, matrices |
05A10 | Factorials, binomial coefficients, combinatorial functions |
05A15 | Exact enumeration problems, generating functions |
68W99 | Algorithms in computer science |
94B99 | Theory of error-correcting codes and error-detecting codes |