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

• A permutations representation that knows what ``Eulerian means
• Generating a random cyclic permutation
• 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?)
• 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)

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

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)