<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 4" %>
Random and Exhaustive Generation of Permutations and Cycles
Mark C. Wilson
Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand
mcw@cs.auckland.ac.nz
Annals of Combinatorics 12 (4) pp.505-516 December, 2008
AMS Subject Classification: 68W20, 68W40, 68Q25, 05A05
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.
Keywords: Sattolo's algorithm, Mahonian permutation statistic

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) 75–78; 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.