Random and exhaustive generation of permutations and cycles

DOI10.1007/S00026-009-0003-3zbMATH Open1231.68281arXivmath/0702753OpenAlexW3106118972MaRDI QIDQ659769FDOQ659769

Mark C. Wilson

Publication date: 24 January 2012

Published in: Annals of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/math/0702753

Recommendations

• Probability generating functions for Sattolo's algorithm
• Mixed distributions in Sattolo's algorithm for cyclic permutations via randomization and derandomization
• scientific article; zbMATH DE number 3557795
• Generating a random cyclic permutation
• Observations on the generation of permutations from random sequences

zbMATH Keywords

Mahonian permutation statisticSattolo's algorithm

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Ranking and unranking permutations in linear time
• A permutations representation that knows what ``Eulerian means
• Generating a random cyclic permutation
• Probability generating functions for Sattolo's algorithm
• Mixed distributions in Sattolo's algorithm for cyclic permutations via randomization and derandomization
• Title not available (Why is that?)

Cited In (10)

• Title not available (Why is that?)
• Integrated strategy for generating permutation
• Efficient enumeration of cyclic permutations in situ
• The sorting index
• Mixed distributions in Sattolo's algorithm for cyclic permutations via randomization and derandomization
• Observations on the generation of permutations from random sequences
• Title not available (Why is that?)
• Random generation with cycle type restrictions
• Generating a random cyclic permutation
• Efficient generation of random derangements with the expected distribution of cycle lengths

This page was built for publication: Random and exhaustive generation of permutations and cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659769)