Gray code for derangements

DOI10.1016/j.dam.2003.06.002zbMath1044.05002MaRDI 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

derangements; Gray codes; Generating algorithms; Restricted permutations

Mathematics Subject Classification ID

05A05: Permutations, words, matrices

68R10: Graph theory (including graph drawing) in computer science

94A29: Source coding

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item