Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2016.19
URN: urn:nbn:de:0030-drops-58863
URL: https://drops.dagstuhl.de/opus/volltexte/2016/5886/
Herter, Felix ; Rote, Günter
Loopless Gray Code Enumeration and the Tower of Bucharest
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{herter_et_al:LIPIcs:2016:5886,
author = {Felix Herter and G{\"u}nter Rote},
title = {{Loopless Gray Code Enumeration and the Tower of Bucharest}},
booktitle = {8th International Conference on Fun with Algorithms (FUN 2016)},
pages = {19:1--19:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-005-7},
ISSN = {1868-8969},
year = {2016},
volume = {49},
editor = {Erik D. Demaine and Fabrizio Grandoni},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5886},
URN = {urn:nbn:de:0030-drops-58863},
doi = {10.4230/LIPIcs.FUN.2016.19},
annote = {Keywords: Tower of Hanoi, Gray code, enumeration, loopless generation}
}
| Keywords: | Tower of Hanoi, Gray code, enumeration, loopless generation | |
| Seminar: | 8th International Conference on Fun with Algorithms (FUN 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 02.06.2016 |
