Generating random alternating permutations in time $n\log n$
P. Marchal, Université Paris, Sorbonne Paris Cité · 2012
We introduce an algorithm generating uniformly distributed random alternating permutations of length n in time n log n. 1 The main result An alternating permutation σ of {1,2,...N} is a permutation such that σ(1)> σ(2) σ(4)... Alternating permutations are a very classical topic in combinatorics. See for instance the survey [ST] for numerous references. The basic result, which dates back from the 19th century [A], states that if pN is the probability that a permutation of {1,2,...N} chosen uniformly at random is alternating, then pNx N = sec x + tanx