scientific article; zbMATH DE number 3557795

From MaRDI portal
Publication:4133641





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.




Cited in
(78)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4133641)