Flip-swap languages in binary reflected Gray code order
2022
A is a set of binary strings of length such that is closed under two operations (when applicable): (1) Flip the leftmost 1; and (2) Swap the leftmost 1 with the bit to its right. Flip-swap languages model many combinatorial objects including necklaces, Lyndon words, prefix normal words, left factors of -ary Dyck words, lattice paths with at most flaws, and feasible solutions to 0-1 knapsack problems. We prove that any flip-swap language forms a cyclic 2-Gray code when listed in binary reflected Gray code (BRGC) order. Furthermore, a generic successor rule computes the next string when provided with a membership tester. The rule generates each string in the aforementioned flip-swap languages in -amortized per string, except for prefix normal words of length which require -amortized per string. Our work generalizes results on necklaces and Lyndon words by Vajnovszki (2008) .
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI