Abstract:
In 1986 S. Sattolo introduced a simple algorithm for uniform random generation
of cyclic permutations on a fixed number of symbols. This algorithm is very similar
to the standard method for generating a random permutation, but is less well
known.
We consider both methods in a unified way, and discuss their relation with
exhaustive generation methods. We analyse several random variables associated
with the algorithms and find their grand probability generating functions, which
gives easy access to moments and limit laws.
