DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2016.19

Loopless Gray Code Enumeration and the Tower of Bucharest

Authors: Felix Herter and Günter Rote

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

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.

Cite as

Felix Herter and Günter Rote. Loopless Gray Code Enumeration and the Tower of Bucharest. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{herter_et_al:LIPIcs.FUN.2016.19,
  author =	{Herter, Felix and Rote, G\"{u}nter},
  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 =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.19},
  URN =		{urn:nbn:de:0030-drops-58863},
  doi =		{10.4230/LIPIcs.FUN.2016.19},
  annote =	{Keywords: Tower of Hanoi, Gray code, enumeration, loopless generation}
}

Search Results

Documents authored by Herter, Felix

Loopless Gray Code Enumeration and the Tower of Bucharest

Abstract

Cite as

Thanks for your feedback!

Could not send message