c Birkhauser Verlag, Basel, 2008 Annals of Combinatorics Random and Exhaustive Generation of Permutations and Cycles

AMS Subject Classication: 68W20, 68W40, 68Q25, 05A05 Abstract. In 1986 Sattolo introduced a simple algorithm for uniform random generation of cyclic permutations on a xed 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 unied way, and discuss their relation with exhaustive generation methods. We analyse sev-eral random variables associated with the algorithms and nd their grand probability generating functions, which gives easy access to moments and limit laws