Generating Gray codes for weak orders in constant amortized time

DOI10.1016/J.DISC.2020.111992MaRDI QIDQ785788zbMATH OpenOpenAlexFDO

Authors D. Kharzeev

Publication date 12 August 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2020.111992

zbMATH Keywords

Gray codeweak orderCAT algorithmshift Gray codeCayley permutationreflectable language

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics in computer science (68R05) Analysis of algorithms (68W40) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Generating 2-Gray codes for ballot sequences in constant amortized time
• Gray Codes for the Ideals of Interval Orders
• scientific article; zbMATH DE number 2040940
• More restricted growth functions: Gray codes and exhaustive generation
• Combinatorial generation via permutation languages. I: Fundamentals

Cites work

• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 1522933 (Why is no real title available?)
• scientific article; zbMATH DE number 7051269 (Why is no real title available?)
• scientific article; zbMATH DE number 3443655 (Why is no real title available?)
• A Survey of Combinatorial Gray Codes
• A loop-free algorithm for generating the linear extensions of a poset
• A loopless algorithm for generating the permutations of a multiset
• An asymptotic equivalent for the number of total preorders on a finite set
• Cayley permutations
• Combinatorial generation via permutation languages
• Efficient universal cycle constructions for weak orders
• Generating Multiset Permutations in Constant Time
• Gray code for Cayley permutations
• Gray codes for reflectable languages
• Greedy universal cycle constructions for weak orders
• Loopless generation of linear extensions of a poset
• On the Factorization of Squarefree Integers
• Research problems on Gray codes and universal cycles
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• The number of weak orderings of a finite set

Cited in

(2)

• Greedy universal cycle constructions for weak orders
• Generating 2-Gray codes for ballot sequences in constant amortized time

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Generating Gray codes for weak orders in constant amortized time

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