×

zbMATH — the first resource for mathematics

A new algorithm for generation of permutations. (English) Zbl 0542.68054
Summary: A new algorithm for generating permutations is presented, that generates the next permutation by reversing a certain suffix of its predecessor. The average size of this suffix is less than \(e\cong 2.8\). It is shown how to find the position of a given permutation and how to construct the permutation of a given position, where the position refers to the order in which the permutations are generated, and is also new.

MSC:
68R99 Discrete mathematics in relation to computer science
05A05 Permutations, words, matrices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] N. Dershowitz,A simplified loop-free algorithm for generating permutations, BIT 15 (1975), 158–164. · Zbl 0317.05006
[2] G. Ehrlich,Loopless algorithm for generating permutations, combinations and other combinatorial configurations, J. ACM 20, 3 (1973), 500–513. · Zbl 0266.68018
[3] G. Ehrlich,Algorithm 466, Permu., Comm. ACM 16, 11 (1973), 690–691.
[4] S. Even,Algorithmic Combinatorics, Macmillan, New York, (1973), 2–11.
[5] W. H. Gates and C. H. Papadimitriou,Bounds for sorting by prefix reversals, Discrete Mathematics 27 (1979), 47–57. · Zbl 0397.68062
[6] S. M. Johnson,Generation of permutations by adjacent transpositions, Math. Comput. 17 (1963), 282–285. · Zbl 0114.01203
[7] E. M. Reingold, J. Nievergelt and N. Deo,Combinatorial Algorithms, Prentice-Hall, New Jersey, (1977), 161–171. · Zbl 0367.68032
[8] R. Sedgewick,Permutation generation methods, Computing Surveys, 9, 2 (1977), 137–164. · Zbl 0358.05003
[9] H. F. Trotter,Algorithm 115, Perm., Comm. ACM 5, 8 (1962), 434–435.
[10] American Mathematical Monthly 82, 1 (1975), 1010.
[11] American Mathematical Monthly 84, 4 (1977), 296. · Zbl 0359.00016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.