Random and exhaustive generation of permutations and cycles. (English) Zbl 1231.68281
Summary: 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.
MSC:
| 68W20 | Randomized algorithms |
| 68W40 | Analysis of algorithms |
| 68Q25 | Analysis of algorithms and problem complexity |
| 05A05 | Permutations, words, matrices |
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] | Gries D., Xue J.Y.: Generating a random cyclic permutation. BIT 28(3), 569–572 (1988) · Zbl 0656.68076 · doi:10.1007/BF01941134 |
| [4] | Knuth D.E.: The Art of Computer Programming, Vol. 2. Addison-Wesley, Reading (1969) · Zbl 0191.18001 |
| [5] | Knuth D.E.: The Art of Computer Programming, Vol. 4. Addison-Wesley, Upper Saddle River, NJ (2005) · Zbl 1127.68068 |
| [6] | Mantaci R., Rakotondrajao F.: A permutation representation that knows what ”Eulerian” means. Discrete Math. Theoret. Comput. Sci. 4, 101–108 (2001) · Zbl 0965.05002 |
| [7] | Mahmoud H.M.: Mixed distributions in Sattolo’s algorithm for cyclic permutations via randomization and derandomization. J. Appl. Probab. 40, 790–796 (2003) · Zbl 1041.60009 · doi:10.1239/jap/1059060904 |
| [8] | Myrvold W., Ruskey F.: Ranking and unranking permutations in linear time. Inform. Process. Lett. 79(6), 281–284 (2001) · Zbl 1032.68670 · doi:10.1016/S0020-0190(01)00141-7 |
| [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/\(\sim\)prodinger/abstract/abs161.htm . · Zbl 1072.05503 |
| [10] | Sattolo S.: An algorithm to generate a random cyclic permutation. Inform. Process. Lett. 22, 315–317 (1986) · doi:10.1016/0020-0190(86)90073-6 |
| [11] | H.Wilf, East Side,West Side, lecture notes available from http://www.cis.upenn.edu/\(\sim\)wilf/lecnotes.html . |
| [12] | Wilson M.C.: Probability generating functions for Sattolo’s algorithm. J. Iranian Statist. Soc. 3, 297–308 (2004) · Zbl 1499.05016 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
