×

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
PDFBibTeX XMLCite