Uniformly generating derangements with fixed number of cycles in polynomial time

MaRDI QIDQ6126504zbMATH OpenFDO

Authors Jittat Fakcharoenphol

Publication date 9 April 2024

Full work available at URL https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1555

zbMATH Keywords

derangementdynamic programmingpolynomial time algorithmrandom generation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Bell and Stirling numbers (11B73) Combinatorics in computer science (68R05) Dynamic programming (90C39)

Recommendations

• Efficient generation of random derangements with the expected distribution of cycle lengths
• Linear-time generation of uniform random derangements encoded in cycle notation
• Generating random derangements
• Constant time generation of derangements
• A new generation tree for permutations, preserving the number of fixed points

Cites work

• Efficient generation of random derangements with the expected distribution of cycle lengths
• Efficient linear-time ranking and unranking of derangements
• Gaussian limiting distributions for the number of components in combinatorial structures
• Generating random derangements
• scientific article; zbMATH DE number 1774199 (Why is no real title available?)
• Integer multiplication in time \(O(n\log n)\)
• Linear-time generation of uniform random derangements encoded in cycle notation
• Mersenne twister
• Ranking and unranking permutations in linear time
• The Feller coupling for random derangements
• The sampling theory of selectively neutral alleles

This page was built for publication: Uniformly generating derangements with fixed number of cycles in polynomial time

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