Gray code for derangements

DOI10.1016/j.dam.2003.06.002zbMath1044.05002OpenAlexW2103479416MaRDI QIDQ1827847

Jean-Luc Baril, Vicentiu Vajnovszki

Publication date: 6 August 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2003.06.002

zbMATH Keywords

derangementsGray codesGenerating algorithmsRestricted permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10) Source coding (94A29)

Related Items (20)

Lexicographic ranking and unranking of derangements in cycle notation ⋮ Constant time generation of derangements ⋮ Gray code for permutations with a fixed number of cycles ⋮ Loopless algorithms to generate maximum length Gray cycles wrt. \(k\)-character substitutions ⋮ Loop-free Gray code algorithm for the \textbf{e}-restricted growth functions ⋮ Efficient generation of random derangements with the expected distribution of cycle lengths ⋮ Prefix partitioned Gray codes for particular cross-bifix-free sets ⋮ Combinatorial Gray codes for classes of pattern avoiding permutations ⋮ Loop-free Gray code algorithms for the set of compositions ⋮ Gray codes and lexicographical combinatorial generation for nonnesting and sparse nonnesting set partitions ⋮ Generating restricted classes of involutions, Bell and Stirling permutations ⋮ More restrictive Gray codes for some classes of pattern avoiding permutations ⋮ Hamiltonian paths for involutions in the square of a Cayley graph ⋮ Gray codes for signed involutions ⋮ A general exhaustive generation algorithm for Gray structures ⋮ Listing combinatorial objects in parallel ⋮ On fixed points of permutations. ⋮ Gray codes for non-crossing partitions and dissections of a convex polygon ⋮ Gray codes, loopless algorithm and partitions ⋮ Efficient linear-time ranking and unranking of derangements

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A CAT algorithm for generating permutations with a fixed number of inversions
• An algorithm for generating subsets of fixed size with a strong minimal change property
• Generating permutations with given ups and downs
• Generating permutations of a bag by interchanges
• Gray visiting Motzkins
• A loopless algorithm for generating the permutations of a multiset
• Constant time generation of derangements
• A new algorithm for generating derangements
• Loopless generation of up-down permutations

This page was built for publication: Gray code for derangements