Séminaire du 21 juin 04, by Mark C. Wilson.

Sattolo's algorithm

In 1986 Sattolo introduced a very simple algorithm for uniform random generation of cyclic permutations of a fixed number of symbols. Recently, H. Prodinger and H. Mahmoud analysed various quantities associated with the algorithm. The former used recurrences to derive mean and variance exactly, while the latter used a probabilistic approach and identified limiting distributions. Here we determine the "grand" probability generating function using the symbolic method.

Virginie Collette
Last modified: Fri Jun 18 16:45:09 CEST 2004