Abstract
We first present a simple recursive algorithm that generates cyclic rotation Gray codes for stamp foldings and semi-meanders, where consecutive strings differ by a stamp rotation. These are the first known Gray codes for stamp foldings and semi-meanders, and we thus solve an open problem posted by Sawada and Li (2012) [17]. We then introduce an iterative algorithm that generates the same rotation Gray codes for stamp foldings and semi-meanders. Both the recursive and iterative algorithms generate stamp foldings and semi-meanders in constant amortized time and O(n)-amortized time per string respectively, using a linear amount of memory.
Original language | English |
---|---|
Article number | 115053 |
Journal | Theoretical Computer Science |
Volume | 1031 |
DOIs | |
Publication status | Published - 21 Mar 2025 |
Keywords
- Binary reflected Gray code
- CAT algorithm
- Gray code
- Meanders
- Reflectable language
- Semi-meanders
- Stamp foldings