License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5886/
Go to the corresponding LIPIcs Volume Portal

Herter, Felix ; Rote, Günter

Loopless Gray Code Enumeration and the Tower of Bucharest

pdf-format:
29.pdf (1 MB)

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
Collection: 8th International Conference on Fun with Algorithms (FUN 2016)
Issue Date: 2016
Date of publication: 02.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI