×

Generating alternating permutations lexicographically. (English) Zbl 0692.68026

Summary: A permutation \(\pi_ 1\pi_ 2...\pi_ n\) is alternating if \(\pi_ 1<\pi_ 2>\pi_ 3<\pi_ 4... \). We present a constant average-time algorithm for generating all alternating permutations in lexicographic order. Ranking and unranking algorithms are also derived.

MSC:

68Q25 Analysis of algorithms and problem complexity
68R99 Discrete mathematics in relation to computer science
05A05 Permutations, words, matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] L. Comtet:Advanced Combinatorics. D. Reidel, 1974.
[2] R. C. Entringer:A combinatorial interpretation of the Euler and Bernoulli numbers. Nieuw Archief voor Wiskunde 14:241–246, 1966. · Zbl 0145.01402
[3] T. Hough and F. Ruskey:An efficient implementation of the Eades, Hickey, Read adjacent interchange combination generation algorithm. J. Combinat. Math. and Combinat. Computing, 4:79–86, 1988. · Zbl 0676.05003
[4] A. D. Kalvin and Y. L. Varol:On the generation of all topological sortings. J. Algorithms, 4:150–162, 1983. · Zbl 0509.68054 · doi:10.1016/0196-6774(83)90042-1
[5] R. Kemp:Fundamentals of the Average Case Analysis of Particular Algorithms. Wiley-Teubner, 1984. · Zbl 0638.68026
[6] D. E. Knuth:Sorting and Searching. Addison-Wesley, 1973. · Zbl 0302.68010
[7] D. E. Knuth and T. J. Buckholtz:Computing of Tangent, Euler, and Bernoulli numbers. Math. Computation, 21:663–688, 1967. · Zbl 0178.04401 · doi:10.1090/S0025-5718-1967-0221735-9
[8] A. Nijenhuis and H. S. Wilf:Combinatorial Algorithms, 2nd Ed. Academic Press, 1978. · Zbl 0476.68047
[9] R. J. Ord-Smith:Generation of permutations in lexicographic order (algorithm 323). Comm. ACM, 2:117, 1968. · doi:10.1145/362896.362913
[10] G. Pruesse and F. Ruskey:Transposition Generation of the Linear Extensions of Certain Posets. Technical Report DCS-91-IR, U. Victoria, 1988. · Zbl 0757.05075
[11] E. M. Reingold, J. Nievergelt, and N. Deo:Combinatorial Algorithms: Theory and Practice. Prentice-Hall, 1977. · Zbl 0367.68032
[12] F. Ruskey:Transposition Generation of Alternating Permutations. Technical Report DCS-90-IR. U. Victoria, 1988. · Zbl 0731.05002
[13] F. Ruskey and A. Proskurowski:Generating binary trees by transpositions. J. Algorithms, to appear. · Zbl 0709.05016
[14] R. Sedgewick:Permutation generation methods. Computing Surveys, 9:137–164, 1977. · Zbl 0358.05003 · doi:10.1145/356689.356692
[15] H. S. Wilf:A unified setting for sequencing, ranking and selection algorithms for combinatorial objects. Advances in Math., 24:281–291, 1977. · Zbl 0354.05041
[16] S. Zaks:Lexicographic generation of ordered trees. Theoretical Computer Science, 10:63–82, 1980. · Zbl 0422.05026 · doi:10.1016/0304-3975(80)90073-0
[17] S. Zaks and D. Richards:Generating trees and other combinatorial objects lexicographically. SIAM J. Computing, 8:73–81, 1979. · Zbl 0406.05026 · doi:10.1137/0208006
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.