A general exhaustive generation algorithm for Gray structures
From MaRDI portal
Abstract: Starting from a succession rule for Catalan numbers, we define a procedure encoding and listing the objects enumerated by these numbers such that two consecutive codes of the list differ only for one digit. Gray code we obtain can be generalized to all the succession rules with the stability property: each label has in its production two labels and , always in the same position, regardless of . Because of this link, we define Gray structures the sets of those combinatorial objects whose construction can be encoded by a succession rule with the stability property. This property is a characteristic that can be found among various succession rules, as the finite, factorial or transcendental ones. We also indicate an algorithm which is a very slight modification of the Walsh's one, working in a O(1) worst-case time per word for generating Gray codes.
Recommendations
- A technique for generating Gray codes
- A loopless algorithm for generating \((k, m)\)-ary trees in gray-code order
- Efficient generation of the ideals of a poset in Gray code order
- Loop-free Gray code algorithms for the set of compositions
- Loopless generation of Gray codes for \(k\)-ary trees
- Efficient loopless generation of Gray codes for \(k\)-ary trees.
- Generating a Gray code for P-sequences
- scientific article; zbMATH DE number 1933234
- A Technique for Generating Specialized Gray Codes
- Efficient coroutine generation of constrained Gray sequences
Cites work
- scientific article; zbMATH DE number 2040940 (Why is no real title available?)
- Approximating algebraic functions by means of rational ones
- ECO:a methodology for the enumeration of combinatorial objects
- Efficient generation of the binary reflected gray code and its applications
- Exhaustive generation of combinatorial objects by ECO
- Generating binary trees by transpositions
- Generating functions for generating trees
- Generating trees and forbidden subsequences
- Generating trees and the Catalan and Schröder numbers
- Generation of Permutations by Adjacent Transposition
- Gray code for derangements
- Gray codes for involutions
- Gray visiting Motzkins
- On the equivalence problem for succession rules
- Pattern matching for permutations
- Random generation of trees and other combinatorial objects
- Some combinatorial interpretations of q-analogs of Schröder numbers
- The number of Baxter permutations
Cited in
(13)- Mixed succession rules: the commutative case
- Exhaustive generation of combinatorial objects by ECO
- Combinatorial generation via permutation languages. I: Fundamentals
- Avoiding cross-bifix-free binary words
- scientific article; zbMATH DE number 5975298 (Why is no real title available?)
- On the exhaustive generation of generalized ballot sequences in lexicographic and Gray code order
- Exhaustive generation for ballot sequences in lexicographic and Gray code order
- Efficient generation of restricted growth words
- Combinatorial Gray codes for classes of pattern avoiding permutations
- More restrictive Gray codes for some classes of pattern avoiding permutations
- scientific article; zbMATH DE number 2040940 (Why is no real title available?)
- Generalized algorithm for restricted weak composition generation
- Generating 2-Gray codes for ballot sequences in constant amortized time
This page was built for publication: A general exhaustive generation algorithm for Gray structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q995753)
