Random and Exhaustive
Generation of Permutations and Cycles

Mark C. Wilson

Department of Computer
Science, University of Auckland, Private Bag 92019,
Auckland, New Zealand
**AMS Subject Classification: **68W20, 68W40, 68Q25, 05A05
**Keywords: **Sattolo's
algorithm, Mahonian permutation statistic

mcw@cs.auckland.ac.nz

Annals of Combinatorics 12 (4) pp.505-516 December, 2008

Abstract:

In 1986 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.
References:

1. R. Durstenfeld, Algorithm 235: random permutation, Commun. ACM 7 (1964) p. 420.

2. R.A. Fisher and F. Yates, Example 12, Statistical Tables, London, 1938.

3. D. Gries and J.Y. Xue, Generating a random cyclic permutation, BIT 28 (3) (1988) 569-572.

4. D.E. Knuth, The Art of Computer Programming, Vol. 2, Addison-Wesley, Reading, 1969.

v5. D.E. Knuth, The Art of Computer Programming, Vol. 4, Addison-Wesley, Upper Saddle River, NJ, 2005.6. R. Mantaci and F. Rakotondrajao, A permutation representation that knows what Eulerian means, Discrete Math. Theoret. Comput. Sci. 4 (2001) 101-108.

7. H.M. Mahmoud, Mixed distributions in Sattolo's algorithm for cyclic permutations via randomization and derandomization, J. Appl. Probab. 40 (2003) 790-796.

8. W. Myrvold and F. Ruskey, Ranking and unranking permutations in linear time, Inform. Process. Lett. 79 (6) (2001) 281-284.

9. H. Prodinger, On the analysis of an algorithm to generate a random cyclic permutation, Ars Combin. 65 (2002) 7578; http://math.sun.ac.za/~prodinger/abstract /abs 161.htm.

10. S. Sattolo, An algorithm to generate a random cyclic permutation, Inform. Process. Lett. 22 (1986) 315-317.

11. H. Wilf, East Side, West Side, lecture notes available from http://www.cis.upenn.edu/~ wilf/lecnotes.html.

12. M.C.Wilson, Probability generating functions for Sattolo's algorithm, J. Iranian Statist. Soc. 3 (2004) 297-308.