Random and exhaustive generation of permutations and cycles

DOI10.1007/S00026-009-0003-3MaRDI QIDQ659769zbMATH OpenOpenAlexFDO

Authors Mark C. Wilson

Publication date 24 January 2012

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 2176112 (Why is no real title available?)
• scientific article; zbMATH DE number 2188461 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• A permutations representation that knows what ``Eulerian means
• Generating a random cyclic permutation
• Mixed distributions in Sattolo's algorithm for cyclic permutations via randomization and derandomization
• Probability generating functions for Sattolo's algorithm
• Ranking and unranking permutations in linear time

Cited in

(17)

• Efficient generation of random derangements with the expected distribution of cycle lengths
• scientific article; zbMATH DE number 2127730 (Why is no real title available?)
• Integrated strategy for generating permutation
• Efficient enumeration of cyclic permutations in situ
• Probability generating functions for Sattolo's algorithm
• Preserving the number of cycles of length k in a growing uniform permutation
• A new generation tree for permutations, preserving the number of fixed points
• The sorting index
• Random generation of permutations of the symmetric group or the alternating group
• Description and generation of permutations containing cycles
• Mixed distributions in Sattolo's algorithm for cyclic permutations via randomization and derandomization
• Generating random permutations by coin tossing: classical algorithms, new analysis, and modern implementation
• Observations on the generation of permutations from random sequences
• scientific article; zbMATH DE number 2188461 (Why is no real title available?)
• Random generation with cycle type restrictions
• Generating restricted classes of involutions, Bell and Stirling permutations
• Generating a random cyclic permutation

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)