Loopless Gray code enumeration and the Tower of Bucharest

DOI10.4230/LIPICS.FUN.2016.19MaRDI QIDQ5282817zbMATH OpenOpenAlexFDO

Authors Felix Herter, Günter Rote

Publication date 17 July 2017

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

zbMATH Keywords

enumerationGray codeloopless generationTower of Hanoi

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Algorithms on strings (68W32) Combinatorial games (91A46)

Abstract: We give new algorithms for generating all n-tuples over an alphabet of m letters, changing only one letter at a time (Gray codes). These algorithms are based on the connection with variations of the Towers of Hanoi game. Our algorithms are loopless, in the sense that the next change can be determined in a constant number of steps, and they can be implemented in hardware. We also give another family of loopless algorithms that is based on the idea of working ahead and saving the work in a buffer.

Recommendations

• Loopless Gray code enumeration and the Tower of Bucharest
• Loop-free Gray code algorithms for the set of compositions
• Gray codes, loopless algorithm and partitions
• Efficient loopless generation of Gray codes for \(k\)-ary trees.
• Gray codes for necklaces and Lyndon words of arbitrary base

Cited in

(4)

• Space-optimal quasi-Gray codes with logarithmic read complexity
• Loopless Gray code enumeration and the Tower of Bucharest
• Loopless Functional Algorithms
• A constant-time algorithm for middle levels Gray codes

This page was built for publication: Loopless Gray code enumeration and the Tower of Bucharest

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