A general exhaustive generation algorithm for Gray structures

DOI10.1007/S00236-007-0053-0zbMATH Open1127.68113arXivmath/0703262OpenAlexW1975955357MaRDI QIDQ995753FDOQ995753

Authors: Antonio Bernini, Elisabetta Grazzini, E. Pergola, R. Pinzani 

Publication date: 10 September 2007

Published in: Acta Informatica (Search for Journal in Brave)

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 $(k)$ has in its production two labels $c_1$ and $c_2$, always in the same position, regardless of $k$. 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.

Full work available at URL: https://arxiv.org/abs/math/0703262

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

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Exact enumeration problems, generating functions (05A15) Nonnumerical algorithms (68W05)

Cites Work

• Generating functions for generating trees
• Generating binary trees by transpositions
• Pattern matching for permutations
• Generating trees and the Catalan and Schröder numbers
• Generation of Permutations by Adjacent Transposition
• ECO:a methodology for the enumeration of combinatorial objects
• The number of Baxter permutations
• Some combinatorial interpretations of \(q\)-analogs of Schröder numbers
• Exhaustive generation of combinatorial objects by ECO
• Generating trees and forbidden subsequences
• Title not available (Why is that?)
• Efficient generation of the binary reflected gray code and its applications
• Gray visiting Motzkins
• Gray code for derangements
• Gray codes for involutions
• Approximating algebraic functions by means of rational ones
• Random generation of trees and other combinatorial objects
• On the equivalence problem for succession rules

Cited In (10)

• Combinatorial generation via permutation languages. I. Fundamentals
• Mixed succession rules: the commutative case
• Exhaustive generation of combinatorial objects by ECO
• Avoiding cross-bifix-free binary words
• Title not available (Why is that?)
• Efficient generation of restricted growth words
• Combinatorial Gray codes for classes of pattern avoiding permutations
• Title not available (Why is that?)
• More restrictive Gray codes for some classes of pattern avoiding permutations
• Generalized algorithm for restricted weak composition generation

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)