Random and exhaustive generation of permutations and cycles. Wilson, M. C. *Annals of Combinatorics*, 12(4):509-520, SP Birkhäuser Verlag Basel, 2009.

Paper abstract bibtex

Paper abstract bibtex

In 1986 S. 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.

@article{wilson2009random, title={Random and exhaustive generation of permutations and cycles}, author={Wilson, Mark C.}, journal={Annals of Combinatorics}, volume={12}, number={4}, pages={509-520}, year={2009}, publisher={SP Birkh{\"a}user Verlag Basel}, keywords={algorithms, combinatorics}, url_Paper={https://link.springer.com/content/pdf/10.1007/s00026-009-0003-3.pdf}, abstract={In 1986 S. 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.} }

Downloads: 0

{"_id":"B2oGQwaftuy67dA4z","bibbaseid":"wilson-randomandexhaustivegenerationofpermutationsandcycles-2009","author_short":["Wilson, M. C."],"bibdata":{"bibtype":"article","type":"article","title":"Random and exhaustive generation of permutations and cycles","author":[{"propositions":[],"lastnames":["Wilson"],"firstnames":["Mark","C."],"suffixes":[]}],"journal":"Annals of Combinatorics","volume":"12","number":"4","pages":"509-520","year":"2009","publisher":"SP Birkhäuser Verlag Basel","keywords":"algorithms, combinatorics","url_paper":"https://link.springer.com/content/pdf/10.1007/s00026-009-0003-3.pdf","abstract":"In 1986 S. 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.","bibtex":"@article{wilson2009random,\n title={Random and exhaustive generation of permutations and cycles},\n author={Wilson, Mark C.},\n journal={Annals of Combinatorics},\n volume={12},\n number={4},\n pages={509-520},\n year={2009},\n publisher={SP Birkh{\\\"a}user Verlag Basel},\n keywords={algorithms, combinatorics},\n url_Paper={https://link.springer.com/content/pdf/10.1007/s00026-009-0003-3.pdf},\n abstract={In 1986 S. Sattolo introduced a simple algorithm for uniform random\ngeneration of cyclic permutations on a fixed number of symbols. This\nalgorithm is very similar to the standard method for generating a random\npermutation, but is less well known. We consider both methods in a\nunified way, and discuss their relation with exhaustive generation\nmethods. We analyse several random variables associated with the\nalgorithms and find their grand probability generating functions, which\ngives easy access to moments and limit laws.}\n}\n\n","author_short":["Wilson, M. C."],"key":"wilson2009random","id":"wilson2009random","bibbaseid":"wilson-randomandexhaustivegenerationofpermutationsandcycles-2009","role":"author","urls":{" paper":"https://link.springer.com/content/pdf/10.1007/s00026-009-0003-3.pdf"},"keyword":["algorithms","combinatorics"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://drive.google.com/uc?export=download&id=1NEXsxwRAx2CWt43v0y0jyZdP1LdOS_xF","dataSources":["AJqx2GM6kFj3JDh8G","yx9ivfGLzvFNsg4LH","QdFdNQZBZSvbPbp7t","o2FBsFrZMS3PxguCG","SjBh38uzaGjRinwq8","M2T285kj8vXfTkGDx","2zimNJgtWEiEM2L3J","TAyBmAZAcnenc4YET","BCqQErP8wgW48bwvt","YjweTJPHHEQ85Pems"],"keywords":["algorithms","combinatorics"],"search_terms":["random","exhaustive","generation","permutations","cycles","wilson"],"title":"Random and exhaustive generation of permutations and cycles","year":2009}