Generating Alternating Permutations Lexicographically
Bruce Bauslaugh,
Department of Computer Science,
University of Victoria, Canada.
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
A permutation
p1 p2 ... pn
is alternating if
p1 < p2 > p3
< p4 ...
We present a constant average-time algorithm for generating all
alternating permutations in lexicographic order.
Ranking and unranking algorithms are also derived.
-
The postscript file is 168,596 bytes,
the dvi file is 38,948 bytes.
-
Appeared in BIT 30 (1990) 17-26.
-
Bruce Bauslaugh
is currently with the Department of Mathematics at the
University of Calgary.
Selected Publications that refer to this paper:
-
Jean-Luc and Remi Vernay,
Whole mirror duplication-random loss model and pattern
avoiding permutations,
Information Processing Letters, 110 (2010) 474-480.
-
Jean-Luc Baril,
More restrictive Gray codes for some classes of pattern
avoiding permutations,
Information Processing Letters, 109 (2009) 799-804.
-
Ting Kuo,
A New Method for Generating Permutations in Lexicographic Order,
Journal of Science and Engineering Technology, 5 (2009) 21-29.
Back to list of publications.