Random and Exhaustive Generation of Permutations and Cycles |
| |
Authors: | Mark C Wilson |
| |
Institution: | (1) Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand |
| |
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 |
本文献已被 SpringerLink 等数据库收录! |
|