Generate a variety of objects represented by bitstrings that appear as 2-Gray codes when listed in binary reflected Gray code (BRGC) order.
The binary reflected Gray code is a classical ordering of all bitstrings of length $n$ where successive strings differ by a single bit flip [Gra53].
The listings have the recursive definition $\Gamma_n = \Gamma_{n-1}\cdot 0, ~\Gamma_{n-1}^R\cdot 1,$ where $\Gamma^R$ denotes the listing $\Gamma$ in reverse order and $\Gamma_1 = 0,1$.
Natural representations of many combinatorial objects appear as 2-Gray codes when listed in BRGC order.
A large class of such languages are known as flip-swap languages.
A flip-swap language (with respect to 1) is a subset $S$ of the length $n$ bitstrings such that $S \cup \{0^n\}$ is closed under two operations (where applicable):
(1) flipping the leftmost 1, and (2) swapping the leftmost 1 with the bit to its right.
Examples include:
- bitstrings
- necklaces
- Lyndon words
- prenecklaces
- pseudo-necklaces
- bitstrings < their reversal
- bitstrings ≤ their reversal (neckties)
- bitstrings with weight ≤ $k$
- bitstrings with forbidden $10^k$
- bitstrings with forbidden prefix $\beta=1\beta'$
- bitstrings < their complemented reversal
- bitstrings ≤ their complemented reversal
- bitstrings ≤ β
- bitstrings with ≤ $k$ inversions with respect to $0^*1^*$
- bitstrings with ≤ $k$ transpositions with respect to $0^*1^*$
- 0-prefix normal words
- left factors of $k$-ary Dyck words
- feasible solutions to 0-1 knapsack problems
where
necklaces and their relatives are defined with respect to a lexicographically smallest representative.
Each of the above languages includes the string $0^n$ except for Lyndon words and bitstrings that are strictly less than their reversal.
Flip-swap languages (with respect to 0) can be defined similarly by interchanging the roles of 0 and 1.
They appear as 2-Gray codes in BRGC ordering when the roles of 0 and 1 are also interchanged in the definition of $\Gamma$.
Examples include:
- bitstrings
- necklaces
- aperiodic necklaces
- prenecklaces
- pseudo-necklaces
- bitstrings > their reversal
- bitstrings ≥ their reversal
- bitstrings with weight ≥ $k$
- bitstrings with forbidden $01^k$
- bitstrings with forbidden prefix $\beta=0\beta'$
- bitstrings > their complemented reversal
- bitstrings ≥ their complemented reversal
- bitstrings ≥ β
- bitstrings with ≤ $k$ inversions with respect to $1^*0^*$
- bitstrings with ≤ $k$ transpositions with respect to $1^*0^*$
- 1-prefix normal words
where
necklaces and their relatives are defined with respect to a lexicographically largest representative.
Each of the above languages includes the string $1^n$ except for aperiodic necklaces and bitstrings that are strictly greater than their reversal.
Each of these languages can be generated in $O(n)$ time per generated bitstring by applying a successor rule approach, with the exception of prefix normal words.
By considering a recursive approach, most listings can be implemented in $O(1)$-amortized time including necklaces and Lyndon words [SWW17].
For more details on flip-swap languages, see [SWW22].
For information specifically related to necklaces and Lyndon words see [SWW17, Vaj08].
Generating bitstrings whose weight range is bounded from below and above is possible with our trimmed BRGC algorithms.