Loopless Gray code enumeration and the Tower of Bucharest

DOI10.4230/LIPICS.FUN.2016.19zbMATH Open1369.68267arXiv1604.06707OpenAlexW3105854028MaRDI QIDQ5282817FDOQ5282817

Authors: Felix Herter, Günter Rote 

Publication date: 17 July 2017

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.

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

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

zbMATH Keywords

enumerationGray codeloopless generationTower of Hanoi

Mathematics Subject Classification ID

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

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)