Bauslaugh, Bruce; Ruskey, Frank Generating alternating permutations lexicographically. (English) Zbl 0692.68026 BIT 30, No. 1, 17-26 (1990). 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. Cited in 6 Documents MathOverflow Questions: Is there a planar network whose path give a TNN matrix whose entries are Eulerian numbers? MSC: 68Q25 Analysis of algorithms and problem complexity 68R99 Discrete mathematics in relation to computer science 05A05 Permutations, words, matrices Keywords:permutations; algorithms PDFBibTeX XMLCite \textit{B. Bauslaugh} and \textit{F. Ruskey}, BIT 30, No. 1, 17--26 (1990; Zbl 0692.68026) Full Text: DOI Online Encyclopedia of Integer Sequences: Euler or up/down numbers: e.g.f. sec(x) + tan(x). Also for n >= 2, half the number of alternating permutations on n letters (A001250). Number of down-up permutations of n+3 starting with n+1. Number of down-up permutations of n+4 starting with n+1. Number of down-up permutations of n+5 starting with n+1. Number of down-up permutations of n+6 starting with n+1. Number of down-up permutations of n+4 starting with 4. Number of down-up permutations of n+5 starting with 5. Triangle of Euler-Bernoulli or Entringer numbers read by rows: T(n,k) is the number of down-up permutations of n+1 starting with k+1. Triangle of Euler-Bernoulli or Entringer numbers. 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.