Constant time generation of derangements

DOI10.1016/j.ipl.2004.02.006zbMath1171.05301OpenAlexW2054943314MaRDI QIDQ2390248

James F. Korsh, Paul S. jun. LaFollette

Publication date: 21 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.02.006

zbMATH Keywords

algorithmsfixed pointscombinatorial problemsderangementsgray codeloopless

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Permutations, words, matrices (05A05)

Related Items

Lexicographic ranking and unranking of derangements in cycle notation ⋮ Efficient generation of random derangements with the expected distribution of cycle lengths ⋮ More restrictive Gray codes for some classes of pattern avoiding permutations ⋮ Listing combinatorial objects in parallel ⋮ On fixed points of permutations. ⋮ Gray code for derangements ⋮ Efficient linear-time ranking and unranking of derangements

Cites Work

• Unnamed Item
• On the loopless generation of binary tree sequences
• Loopless generation of linear extensions of a poset
• An algorithm for generating subsets of fixed size with a strong minimal change property
• Gray code for derangements
• On O(1) Time Algorithms for Combinatorial Generation
• Generating Multiset Permutations in Constant Time
• Loopless Generation of Trees with Specified Degrees
• Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations