Princeton ELE 572 - Permutation Generation Methods

Unformatted text preview:

Permutation Generation Methods* ROBERT SEDGEWlCK Program ~n Computer Science and Dwlsmn of Applled Mathematics Brown Unwersity, Prowdence, Rhode Island 02912 This paper surveys the numerous methods that have been proposed for permutatmn enumeration by computer. The various algorithms which have been developed over the years are described in detail, and zmplemented in a modern ALc, oL-hke language. All of the algorithms are derived from one rumple control structure. The problems involved with implementing the best of the algorithms on real com- puters are treated m 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 tutomal on how to compare a number of different algorithms for the same task Key Words and Phrases: permutations, combmatomal algorithms, code optimlzatmn, analysis of algorithms, lexicographlc ordering, random permutatmns, recursion, cyclic rotatzon. CR Categories: 3.15, 4.6, 5 25, 5.30. INTRODUCTION Over thirty algorithms have been pub- lished during the past twenty years for generating by computer all N! permuta- tions of N elements. This problem is a nontrivial example of the use of computers in combinatorial mathematics, and it is interesting to study because a number of different approaches can be compared. Surveys of the field have been published previously in 1960 by D. H. Lehmer [26] and in 1970-71 by R. J. Ord-Smith [29, 30]. A new look at the problem is appropriate at this time because several new algo- rithms have been proposed in the inter- vening years. Permutation generation has a long and distinguished history. It was actually one of the first nontrivial nonnumeric prob- lems to be attacked by computer. In 1956, C. Tompkins wrote a paper [44] describing a number of practical areas 'where permu- * Thin work was supported by the Natmnal Science Foundatmn Grant No. MCS75-23738 tation generation was being used to solve problems. Most of the problems that he described are now handled with more so- phisticated techniques, but the paper stim- ulated interest in permutation generation by computer per se. The problem is simply stated, but not easily solved, and is often used as an example in programming and correctness. (See, for example, [6]). The study of the various methods that have been proposed for permutation gener- ation is still very instructive today because together they illustrate nicely the rela- tionship between counting, recursion, and iteration. These are fundamental concepts in computer science, and it is useful to have a rather simple example which illus- trates so well the relationships between them. We shall see that algorithms which seem to differ markedly have essentially the same structure when expressed in a modern language and subjected to simple program transformations. Many readers may find it surprising to discover that ~'top-down" (recursive) and '~bettom-up" Copyright © 1977, Associahon for Computing Machinery, Inc. General permismon to repubhsh, but not for profit, all or part of this materml is granted provided that ACM's copymght notice is given and that reference is made to the publication, to its date of issue, and to the fact that repnntmg privileges were granted by permission of the Association for Computing Machinery Computing Surveys, Vol 9, No 2, June 1977138 • R. Sedgewick CONTENTS INTRODUCTION 1 METHODS BASED ON EXCHANGES Recur~lve methods Adjacent exchanges Factorial counting "Loopless" algorithms Another lterahve method 2 OTHER TYPES OF ALGORITHMS Nested cycling Lexlcograpluc algorlthras Random permutataons 3 IMPLEMENTATION AND ANALYSIS A recurslve method (Heap) An lteratlve method (Ives) A cychc method (Langdon) CONCLUSION ACKNOWLEDGMENTS REFERENCES v (iterative) design approaches can lead to the same program. Permutation generation methods not only illustrate programming issues in high-level (procedural) languages; they also illustrate implementation issues in low-level (assembly) languages. In this pa- per, we shall try to find the fastest possible way to generate permutations by com- puter. To do so, we will need to consider some program "optimization" methods (to get good implementations) and some mathematical analyses (to determine which implementation is best). It turns out that on most computers we can generate each permutation at only slightly more than the cost of two store instructions. In dealing with such a problem, we must be aware of the inherent limitations. Without computers, few individuals had the patience to record all 5040 permuta- tions of 7 elements, let alone all 40320 permutations of 8 elements, or all 362880 permutations of 9 elements. Computers help, but not as much as one might think. Table 1 shows the values of N! for N -< 17 along with the time that would be taken by a permutation generation program that produces a new permutation each micro- second. For N > 25, the time required is far greater than the age of the earth! For many practical applications, the sheer magnitude of N! has led to the devel- opment of "combinatorial search" proce- dures which are far more efficient than permutation enumeration. Techniques such as mathematical programming and backtracking are used regularly to solve optimization problems in industrial situa- tions, and have led to the resolution of several hard problems in combinatorial mathematics (notably the four-color prob- lem). Full treatment of these methods would be beyond the scope of this paper- they are mentioned here to emphasize that, in practice, there are usually alter- natives to the "brute-force" method of gen- erating permutations. We will see one ex- ample of how permutation generation can sometimes be greatly improved with a backtracking technique. In the few applications that remain where permutation generation is really re- quired, it usually doesn't matter much which generation method is used, since the cost of processing the permutations far TABLE 1. APPROXIMATE TIME NEEDED TO GENERATE ALL PERMUTATIONS OF N (1 /zsec per permutation) N NI Time 1 1 2 2 3 6 4 24 5 120 6 720


View Full Document
Download Permutation Generation Methods
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Permutation Generation Methods and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Permutation Generation Methods 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?