# Inside the Binary Reflected Gray Code:
Flip-Swap Languages in 2-Gray Code Order

Joe Sawada Aaron Williams Dennis Wong

###### Abstract

A _flip-swap language_ is a set ${\bf S}$ of binary strings of length $n$ such
that ${\bf S}\cup\\{0^{n}\\}$ 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
$k$-ary Dyck words, 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
$O(n)$-amortized per string, except for prefix normal words of length $n$
which require $O(n^{1.864})$-amortized per string. Our work generalizes
results on necklaces and Lyndon words by Vajnovski [Inf. Process. Lett.
106(3):96$-$99, 2008].

##  1 Introduction

Combinatorial generation studies the efficient generation of each instance of
a combinatorial object, such as the $n!$ permutations of $\\{1,2,\ldots,n\\}$
or the $\frac{1}{n+1}\binom{2n}{n}$ binary trees with $n$ nodes. The research
area is fundamental to computer science and it has been covered by textbooks
such as _Combinatorial Algorithms for Computers and Calculators_ by Nijenhuis
and Wilf [27], _Concrete Mathematics: A Foundation for Computer Science_ by
Graham, Knuth, and Patashnik [9], and _The Art of Computer Programming, Volume
4A, Combinatorial Algorithms_ by Knuth [12]. In fact, Knuth’s section on
_Generating Basic Combinatorial Patterns_ is over 450 pages. The subject is
important to every day programmers, and Arndt’s _Matters Computational: Ideas,
Algorithms, Source Code_ is an excellent practical resource [1]. A primary
consideration is listing the instances of a combinatorial object so that
consecutive instances differ by a specified _closeness condition_. Lists of
this type are called _Gray codes_. This terminology is due to the eponymous
_binary reflected Gray code_ (_BRGC_) by Frank Gray, which orders the $2^{n}$
binary strings of length $n$ so that consecutive strings differ in one bit.
The BRGC was patented for a pulse code communication system in 1953 [10]. For
example, the order for $n=4$ is

$\displaystyle 0000,1000,1100,0100,0110,1110,1010,0010,$ (1) $\displaystyle
0011,1011,1111,0111,0101,1101,1001,0001.$

Variations that reverse the entire order or the individual strings are also
commonly used in practice and in the literature. We note that the order in (1)
is _cyclic_ because the last and first strings also differ by the closeness
condition, and this property holds for all $n$.

One challenge facing combinatorial generation is its relative surplus of
breadth and lack of depth111This is not to say that combinatorial generation
is always easy. For example, the ‘middle levels‘ conjecture was confirmed by
Mütze [14] after 30 years and effort by hundreds of researchers.. For example,
[1], [12], and [27] have separate subsections for different combinatorial
objects, and the majority of the Gray codes are developed from first
principles. Thus, it is important to encourage simple frameworks that can be
applied to a variety of combinatorial objects. Previous work in this direction
includes the following:

  1. 1.

the ECO framework developed by Bacchelli, Barcucci, Grazzini, and Pergola [2]
that generates Gray codes for a variety of combinatorial objects such as Dyck
words in constant amortized time per instance;

  2. 2.

the twisted lexico computation tree by Takaoka [22] that generates Gray codes
for multiple combinatorial objects in constant amortized time per instance;

  3. 3.

loopless algorithms developed by Walsh [25] to generate Gray codes for
multiple combinatorial objects, which extend algorithms initially given by
Ehrlich in [8];

  4. 4.

greedy algorithms observed by Williams [28] that provide a uniform
understanding for many previous published results;

  5. 5.

the reflectable language framework by Li and Sawada [13] for generating Gray
codes of $k$-ary strings, restricted growth strings, and $k$-ary trees with
$n$ nodes;

  6. 6.

the bubble language framework developed by Ruskey, Sawada and Williams [17]
that provides algorithms to generate shift Gray codes for fixed-weight
necklaces and Lyndon words, $k$-ary Dyck words, and representations of
interval graphs;

  7. 7.

the permutation language framework developed by Hartung, Hoang, Mütze and
Williams [11] that provides algorithms to generate Gray codes for a variety of
combinatorial objects based on encoding them as permutations.

We focus on an approach that is arguably simpler than all of the above: Start
with a known Gray code and then _filter_ or _induce_ the list based on a
subset of interest. In other words, the subset is listed in the relative order
given by a larger Gray code, and the resulting order is a _sublist (Gray
code)_ with respect to it. Historically, the first sublist Gray code appears
to be the _revolving door_ Gray code for combinations [26]. A _combination_ is
a length $n$ binary string with _weight_ (i.e. number of ones) $k$. The Gray
code is created by filtering the BRGC, as shown below for $n=4$ and $k=2$ (cf.
(1))

$\displaystyle\cancel{0000},\cancel{1000},1100,\cancel{0100},0110,\cancel{1110},1010,\cancel{0010},$
(2) $\displaystyle
0011,\cancel{1011},\cancel{1111},\cancel{0111},0101,\cancel{1101},1001,\cancel{0001}.$

This order is a _transposition Gray code_ as consecutive strings differ by
transposing two bits222When each string is viewed as the incidence vector of a
$k$-subset of $\\{1,2,\ldots,n\\}$, then consecutive $k$-subsets change via a
“revolving door” (i.e. one value enters and one value exits).. It can be
generated _directly_ (i.e. without filtering) by an efficient algorithm [26].
Transposition Gray codes are a special case of _2-Gray codes_ where
consecutive strings differ by flipping (i.e. complementing) at most two bits.
Vajnovszki [23] proved that necklaces and Lyndon words form a cyclic $2$-Gray
code in BRGC order, and efficient algorithms can generate these sublist Gray
codes directly [21]. Our goal is to expand upon the known languages that are
2-Gray codes in BRGC order, and which can be efficiently generated. To do
this, we introduce a new class of languages.

A _flip-swap language_ (with respect to 1) is a set ${\bf S}$ of length $n$
binary strings such that ${\bf S}\cup\\{0^{n}\\}$ is closed under two
operations (when applicable): (1) Flip the leftmost $1$; and (2) Swap the
leftmost $1$ with the bit to its right. A flip-swap language with respect to
$0$ is defined similarly. Flip-swap languages encode a wide variety of
combinatorial objects.

######  Theorem 1.1.

The following sets of length $n$ binary strings are flip-swap languages:

Flip-Swap languages (with respect to $1$) i. all strings ii. strings with weight $\leq k$ iii. strings $\leq\gamma$ iv. strings with $\leq k$ inversions re: $0^{*}1^{*}$ v. strings with $\leq k$ transpositions re: $0^{*}1^{*}$ vi. strings $<$ their reversal vii. strings $\leq$ their reversal (neckties) viii. strings $<$ their complemented reversal ix. strings $\leq$ their complemented reversal x. strings with forbidden $10^{t}$ xi. strings with forbidden prefix $1\gamma$ xii. $0$-prefix normal words xiii. necklaces (smallest rotation) xiv. Lyndon words xv. prenecklaces (smallest rotation) xvi. pseudo-necklaces with respect to $0^{*}1^{*}$ xvii. left factors of $k$-ary Dyck words xviii. feasible solutions to 0-1 knapsack problems  |  Flip-Swap languages (with respect to $0$) $\triangleright$ all strings $\triangleright$ strings with weight $\geq k$ $\triangleright$ strings $\geq\gamma$ $\triangleright$ strings with $\leq k$ inversions re: $1^{*}0^{*}$ $\triangleright$ strings with $\leq k$ transpositions re: $1^{*}0^{*}$ $\triangleright$ strings $>$ their reversal $\triangleright$ strings $\geq$ their reversal $\triangleright$ strings $>$ their complemented reversal $\triangleright$ strings $\geq$ their complemented reversal $\triangleright$ strings with forbidden $01^{t}$ $\triangleright$ strings with forbidden prefix $0\gamma$ $\triangleright$ $1$-prefix normal words $\triangleright$ necklaces (largest rotation) $\triangleright$ aperiodic necklaces (largest rotation) $\triangleright$ prenecklaces (largest rotation) $\triangleright$ pseudo-necklaces with respect to $1^{*}0^{*}$
---|---

Our second result is that every flip-swap language forms a cyclic $2$-Gray
code when listed in BRGC order. This generalizes the previous sublist BRGC
results [21, 23].

######  Theorem 1.2.

When a flip-swap language $\mathbf{S}$ is listed in BRGC order the resulting
listing is a 2-Gray code. If $\mathbf{S}$ includes $0^{n}$ then the listing is
cyclic.

Our third result is a generic successor rule, which efficiently computes the
next string in the $2$-Gray code of a flip-swap language, so long as a fast
membership test is given.

######  Theorem 1.3.

The languages in Theorem 1.1 can be generated in $O(n)$-amortized time per
string, with the exception of prefix normal words which require
$O(n^{1.864})$-time.

In Section 2, we formally define our version of the BRGC. In Section 3, we
prove Theorem 1.1, and define the flip-swap partially ordered set. In Section
4, we give our generic successor rule and prove Theorem 1.2. In Section 5, we
present a generic generation algorithm that list out each string of a flip-
swap language, and we prove Theorem 1.3.

##  2 The Binary Reflected Gray Code

Let $\mathbf{B}(n)$ denote the set of length $n$ binary strings. Let $BRGC(n)$
denote the listing of $\mathbf{B}(n)$ in BRGC order. Let $\overline{BRGC}(n)$
denote the listing $BRGC(n)$ in reverse order. Then $BRGC(n)$ can be defined
recursively as follows, where $\mathcal{L}\cdot x$ denotes the listing
$\mathcal{L}$ with the character $x$ appended to the end of each string:

$BRGC(n)=\begin{cases}0,1&\text{if $n=1$};\\\ BRGC(n-1)\cdot 0,\
\overline{BRGC}(n-1)\cdot 1&\text{if $n>1$.}\end{cases}$

For example, $BRGC(2)=00,10,11,01$ and $\overline{BRGC}(2)=01,11,10,00$, thus

$BRGC(3)=00{\bf 0},10{\bf 0},11{\bf 0},01{\bf 0},01{\bf 1},11{\bf 1},10{\bf
1},00{\bf 1}$.

This definition of BRGC order is the same as the one used by Vajnovzski [23].
When the strings are read from right-to-left, we obtain the classic definition
of BRGC order [10]. For flip-swap languages with respect to 0, we interchange
the roles of the 0s and 1s; however, for our discussions we will focus on
flip-swap languages with respect to 1. Table 1 illustrates $BRGC(4)$ and six
flip-swap languages listed in Theorem 1.1.

$n=4$ |  all | necklaces |  $0$-PNW | $\leq 1001$ | $k\leq 2$ | neckties
---|---|---|---|---|---|---
BRGC | i. | xiii. | xii. | iii. | ii. | vii.
0000 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
1000 | ✓ |  |  | ✓ | ✓ |
1100 | ✓ |  |  |  | ✓ |
0100 | ✓ |  |  | ✓ | ✓ |
0110 | ✓ |  | ✓ | ✓ | ✓ | ✓
1110 | ✓ |  |  |  |  |
1010 | ✓ |  |  |  | ✓ |
0010 | ✓ |  | ✓ | ✓ | ✓ | ✓
0011 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
1011 | ✓ |  |  |  |  | ✓
1111 | ✓ | ✓ |  |  |  | ✓
0111 | ✓ | ✓ | ✓ | ✓ |  | ✓
0101 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
1101 | ✓ |  |  |  |  |
1001 | ✓ |  |  | ✓ | ✓ | ✓
0001 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
(a) String membership in 6 flip-swap languages.

i. | xiii. | xii. | iii. | ii. | vii.
---|---|---|---|---|---
|  |  |  |  |
(b) Visualizating the 2-Gray codes in (a).

Table 1: Flip-swap languages ordered as sublists of the binary reflected Gray
code. Theorem 1.1 covers each language, so the resulting orders are 2-Gray
codes.

##  3 Flip-swap languages

In this section, we formalize some of the non-obvious flip-swap languages
stated in Theorem 1.1. Then we prove Theorem 1.1 for a subset of the listed
languages including necklaces, prefix normal words, and feasible solutions to
the 0-1 knapsack problems. The remainder of the languages are proved in the
Appendix.

Consider a binary string $\alpha=b_{1}b_{2}\cdots b_{n}$. The _weight_ of
$\alpha$ is the number of 1s it contains. An _inversion_ in $\alpha$ with
respect to $0^{*}1^{*}$ is an index pair $(i,j)$ such that $i<j$ and $b_{i}=1$
and $b_{j}=0$. The number of _transpositions_ of $\alpha$ with respect to
another binary string $\beta$ of length $n$ is the minimum number of adjacent
transpositions required to transform $\alpha$ to $\beta$.

A _necklace_ is the lexicographically smallest (largest) string in an
equivalence class under rotation. An _aperiodic necklace_ is a necklace that
cannot be written in the form $\beta^{j}$ for some $j<n$. A _Lyndon word_ is
an aperiodic necklace when using the lexicographically smallest string as the
representative. A _prenecklace_ is a prefix of a necklace. A _block_ with
respect to $0^{*}1^{*}$ is a maximal substring of the form $0^{*}1^{*}$. A
string $\alpha=b_{1}b_{2}\cdots b_{n}=B_{b}B_{b-1}\cdots B_{1}$ is a _pseudo-
necklace_ with respect to $0^{*}1^{*}$ if $B_{b}\leq B_{i}$ for all $1\leq
i<b$.

A _$k$ -ary Dyck word_ is a binary string of length $n=tk$ with $t$ copies of
$1$ and $t(k-1)$ copies of $0$ such that every prefix has at most $k-1$ copies
of $0$ for every $1$. The set of length $n$ prefixes of $k$-ary Dyck words is
called _left factors of $k$-ary Dyck words_.

Let $flip_{\alpha}(i)$ be the string obtained by complementing $b_{i}$. Let
$swap_{\alpha}(i,j)$ be the string obtained by swapping $b_{i}$ and $b_{j}$.
When the context is clear we use $flip(i)$ and $swap(i,j)$ instead of
$flip_{\alpha}(i)$ and $swap_{\alpha}(i,j)$. Also, let $\ell_{0}(\alpha)$
denote the position of the leftmost $0$ of $\alpha$ or $n+1$ if no such
position exists. Similarly, let $\ell_{1}(\alpha)$ denote the position of the
leftmost $1$ of $\alpha$ or $n+1$ if no such position exists. We now prove
that binary strings, necklaces, prefix normal words, and feasible solutions to
the 0-1 knapsack problems are flip-swap languages with respect to 1.

Binary strings: Obviously the set ${\bf B}(n)$ satisfies the two closure
properties of a flip-swap language and thus is a flip-swap language. In fact,
the BRGC order induces a cyclic $1$-Gray code for ${\bf B}(n)$ [12, 15].

Necklaces: Let ${\bf N}(n)$ be the set of necklaces of length $n$ and
$\alpha=0^{j}1b_{j+2}b_{j+3}\cdots b_{n}$ be a necklace in ${\bf N}(n)$. By
the definition of necklace, it is easy to see that
$flip_{\alpha}(\ell_{\alpha})=0^{j+1}b_{j+2}b_{j+3}\cdots b_{n}\in{\bf N}(n)$
and thus ${\bf N}(n)$ satisfies the flip-first property. For the swap-first
operation, observe that if $\alpha\neq 0^{n-1}1$ and $b_{j+2}=1$, then the
swap-first operation produces the same necklace. Otherwise if $\alpha\neq
0^{n-1}1$ and $b_{j+2}=0$, then the swap-first operation produces the string
$0^{j+1}1b_{j+3}b_{j+4}\cdots b_{n}$ which is clearly a necklace. Thus, the
set of necklaces is a flip-swap language.

Prefix normal words: A binary string $\alpha$ is _prefix normal_ with respect
to $0$ (also known as $0$-prefix normal word) if no substring of $\alpha$ has
more $0$s than its prefix of the same length. For example, the string
001010010111011 is a $0$-prefix normal word but the string 001010010011011 is
not because it has a substring of length $5$ with four $0$s while the prefix
of length $5$ has only three $0$s.

Observe that the set of $0$-prefix normal words of length $n$ satisfies the
two closure properties of a flip-swap language as the flip-first and swap-
first operations either increases or maintain the number of $0$s in its
prefix. Thus, the set of $0$-prefix normal words of length $n$ is a flip-swap
language.

Feasible solutions to $0$-$1$ knapsack problems: The input to a _$0$ -$1$
knapsack problem_ is a knapsack capacity $W$, and a set of $n$ items each of
which has a non-negative weight $w_{i}\geq 0$ and a value $v_{i}$. A subset of
items is _feasible_ if the total weight of the items in the subset is less
than or equal to the capacity $W$. Typically, the goal of the problem is to
find a feasible subset with the maximum value, or to decide if a feasible
subset exists with value $\geq c$.

Given the input to a $0$-$1$ knapsack problem, we reorder the items by non-
decreasing weight. That is, $w_{i}\geq w_{i+1}$ for $1\leq i\leq n-1$. Notice
that the incidence vectors of feasible subsets are now a flip-swap language.
More specifically, flipping any $1$ to $0$ causes the subset sum to decrease,
and so does swapping any $1$ with the bit to its right. Hence, the language
satisfies the flip-first and the swap-first closure properties and is a flip-
swap language.

###  3.1 Flip-Swap poset

In this section we introduce a poset whose ideals correspond to a flip-swap
language which includes the string $0^{n}$.

Let $\alpha=b_{1}b_{2}\cdots b_{n}$ be a length $n$ binary string. We define
$\tau(\alpha)$ as follows:

$\displaystyle\tau(\alpha)=$ $\displaystyle\alpha$ if $\alpha=0^{n}$,
$\displaystyle\tau(\alpha)=$ $\displaystyle flip_{\alpha}(\ell_{\alpha})$ if
$\alpha\neq 0^{n}$ and ($\ell_{\alpha}=n$ or $b_{\ell_{\alpha}+1}=1$) (flip-
first),  $\displaystyle\tau(\alpha)=$ $\displaystyle
swap_{\alpha}(\ell_{\alpha},\ell_{\alpha}+1)$ otherwise (swap-first).

Let $\tau^{t}(\alpha)$ denote the string that results from applying the $\tau$
operation $t$ times to $\alpha$. We define the binary relation $<_{R}$ on
${\bf B}(n)$ to be the transitive closure of the cover relation $\tau$, that
is $\beta<_{R}\alpha$ if $\beta\neq\alpha$ and $\beta=\tau^{t}(\alpha)$ for
some $t>0$. It is easy to see that the binary relation $<_{R}$ is irreflexive,
anti-symmetric and transitive. Thus $<_{R}$ is a strict partial order. The
relation $<_{R}$ on binary strings defines our flip-swap poset.

######  Definition 1.

The _flip-swap poset_ $\mathcal{P}(n)$ is a strict poset with ${\bf B}(n)$ as
the ground set and $<_{R}$ as the strict partial order.

Figure 2 shows the Hasse diagram of $\mathcal{P}(4)$ with the ideal for binary
strings of length $4$ that are lexicographically smaller or equal to $1001$ in
bold. Observe that $\mathcal{P}(n)$ is always a tree with $0^{n}$ as the
unique minimum element, and that its ideals are the subtrees that contain this
minimum.

######  Lemma 1.

A set ${\bf S}$ over ${\bf B}(n)$ that includes $0^{n}$ is a flip-swap
language if and only if ${\bf S}$ is an ideal of $\mathcal{P}(n)$.

###### Proof.

Let ${\bf S}$ be a flip-swap language over ${\bf B}(n)$ and $\alpha$ be a
string in ${\bf S}$. Since ${\bf S}$ is a flip-swap language, ${\bf S}$
satisfies the flip-first and swap-first properties and thus $\tau(\alpha)$ is
a string in ${\bf S}$. Therefore every string $\gamma<_{R}\alpha$ is in ${\bf
S}$ and hence ${\bf S}$ is an ideal of $\mathcal{P}(n)$. The other direction
is similar. ∎

If S is a set of binary strings and $\gamma$ is a binary string, then the
_quotient_ of S and $\gamma$ is ${\bf S}/\gamma=\\{\alpha\ |\
\alpha\gamma\in{\bf S}\\}$.

(a) The flip-swap poset $\mathcal{P}(4)$.

(b) An ideal of $\mathcal{P}(4)$.

Figure 2: Flip-swap languages are the ideals of the flip-swap poset. The ideal
in (b) contains the $4$-bit binary strings that are $\leq 1001$ with respect
to lexicographic order.

######  Lemma 2.

If ${\bf S}_{1}$ and ${\bf S}_{2}$ are flip-swap languages and $\gamma$ is a
binary string, then ${\bf S}_{1}\cap{\bf S}_{2}$, ${\bf S}_{1}\cup{\bf S}_{2}$
and ${\bf S}_{1}/\gamma$ are flip-swap languages.

###### Proof.

Let ${\bf S}_{1}$ and ${\bf S}_{2}$ be two flip-swap languages and let
$\gamma$ be a binary string. The intersection and union of ideals of any poset
are also ideals of that poset, so ${\bf S}_{1}\cap{\bf S}_{2}$ and ${\bf
S}_{1}\cup{\bf S}_{2}$ are flip-swap languages. Now consider $\alpha\in{\bf
S}_{1}/\gamma$.

Suppose $\alpha\in{\bf S}_{1}/\gamma$ for some non-empty $\gamma$ where
$j=|\alpha|$. This means that $\alpha\gamma\in{\bf S}_{1}$. Consider three
cases depending $\ell_{\alpha\gamma}$. If $\ell_{\alpha\gamma}<j$, then
clearly $\tau(\alpha\gamma)=\tau(\alpha)\gamma$. From Lemma 1,
$\tau(\alpha)\gamma\in{\bf S}_{1}$ and thus $\tau(\alpha)\in{\bf
S}_{1}/\gamma$. If $\ell_{\alpha\gamma}=j$, then $\alpha=0^{j-1}1$ and
$\tau(\alpha)=0^{j}$. Since ${\bf S}_{1}$ is a flip-swap language
$0^{j}\gamma\in{\bf S}_{1}$. Again this implies that $\tau(\alpha)\in{\bf
S}_{1}/\gamma$. If $\ell_{\alpha\gamma}>j$ then $\alpha=0^{j}$ and
$\tau(\alpha)=\alpha$ in this case. For each case we have shown that
$\tau(\alpha)\in{\bf S}_{1}/\gamma$ and thus ${\bf S}_{1}/\gamma$ is a flip-
swap language by Lemma 1. ∎

######  Corollary 1.

Flip-swap languages are closed under union, intersection, and quotient.

###### Proof.

Let ${\bf S}_{A}$ and ${\bf S}_{B}$ be flip-swap languages and $\gamma$ be a
binary string. Since ${\bf S}_{A}$ and ${\bf S}_{B}$ can be represented by
ideals of the flip-swap poset, possibly excluding $0^{n}$, by Lemma 2 the sets
${\bf S}_{A}\cap{\bf S}_{B}$, ${\bf S}_{A}\cup{\bf S}_{B}$ and ${\bf
S}_{A}/\gamma$ are flip-swap languages. ∎

######  Lemma 3.

If $\alpha\gamma$ is a binary string in a flip-swap language ${\bf S}$, then
$0^{|\alpha|}\gamma\in{\bf S}$.

###### Proof.

This result follows from the flip-first property of flip-swap languages. ∎

##  4 A generic successor rule for flip-swap languages

Consider any flip-swap language ${\bf S}$ that includes the string $0^{n}$.
Let $\mathcal{BRGC}({\bf S})$ denote the listing of $\bf S$ in BRGC order.
Given a string $\alpha\in\mathbf{S}$, we define a generic _successor rule_
that computes the string following $\alpha$ in the cyclic listing
$\mathcal{BRGC}({\bf S})$.

Let $\alpha=b_{1}b_{2}\cdots b_{n}$ be a string in ${\bf S}$. Let $t_{\alpha}$
be the leftmost position such that $flip_{\alpha}(t_{\alpha})\in{\bf S}$ when
$|{\bf S}|>1$, such a $t_{\alpha}$ exists since ${\bf S}$ satisfies the flip-
first property and $|{\bf S}|>1$. Recall that $\ell_{\alpha}$ is defined to be
the position of the leftmost $1$ of $\alpha$ (or $|\alpha|+1$ if no such
position exists). Notice that $t_{\alpha}\leq\ell_{\alpha}$ when $|{\bf S}|>1$
since ${\bf S}$ is a flip-swap language.

Necklaces |  Parity of $w(\alpha)$ | $t_{\alpha}$ | $\ell_{\alpha}$ | Successor | Case
---|---|---|---|---|---
000000 | even | $6$ |  | $flip2(5,6)$ |  (4c)
000011 | even | $3$ |  | $flip2(2,3)$ |  (4c)
011011 | even | $2$ |  | $flip(2)$ |  (4b)
001011 | odd |  | $3$ | $flip(4)$ |  (4e)
001111 | even | $2$ |  | $flip2(1,2)$ |  (4c)
111111 | even | $1$ |  | $flip(1)$ |  (4b)
011111 | odd |  | $2$ | $flip(3)$ |  (4e)
010111 | even | $3$ |  | $flip(2)$ |  (4b)
000111 | odd |  | $4$ | $flip(5)$ |  (4e)
000101 | even | $2$ |  | $flip(2)$ |  (4b)
010101 | odd |  | $2$ | $flip2(2,3)$ |  (4d)
001101 | odd |  | $3$ | $flip(4)$ |  (4e)
001001 | even | $3$ |  | $flip(3)$ |  (4b)
000001 | odd |  |  | $flip(6)$ |  (4a)
Table 2: The necklaces of length 6 induced by successive applications the
function $f$ starting from $000000$. The sixth column of the table lists out
the corresponding rules in $f$ that apply to each necklace to obtain the next
necklace.

Let $flip2_{\alpha}(i,j)$ be the string obtained by complementing both $b_{i}$
and $b_{j}$. When the context is clear we use $flip2(i,j)$ instead of
$flip2_{\alpha}(i,j)$. Also, let $w(\alpha)$ denote the number of $1$s of
$\alpha$. We claim that the following function $f$ computes the next string in
the cyclic ordering $\mathcal{BRGC}({\bf S})$:

$\displaystyle f(\alpha)=$ $\displaystyle 0^{n}$ if $\alpha=0^{n-1}1$; (4a)
$\displaystyle f(\alpha)=$ $\displaystyle flip_{\alpha}(t_{\alpha})$ if
$w(\alpha)$ is even and ($t_{\alpha}=1$ or
$flip2_{\alpha}(t_{\alpha}-1,t_{\alpha})\notin{\bf S}$); (4b) $\displaystyle
f(\alpha)=$ $\displaystyle flip2_{\alpha}(t_{\alpha}-1,t_{\alpha})$ if
$w(\alpha)$ is even and $flip2_{\alpha}(t_{\alpha}-1,t_{\alpha})\in{\bf S}$;
(4c) $\displaystyle f(\alpha)=$ $\displaystyle
flip2_{\alpha}(\ell_{\alpha},\ell_{\alpha}+1)$ if $w(\alpha)$ is odd and
$flip_{\alpha}(\ell_{\alpha}+1)\notin{\bf S}$; (4d) $\displaystyle f(\alpha)=$
$\displaystyle flip_{\alpha}(\ell_{\alpha}+1)$ if $w(\alpha)$ is odd and
$flip_{\alpha}(\ell_{\alpha}+1)\in{\bf S}$. (4e)

Thus, successive applications of the function $f$ on a flip-swap language
${\bf S}$, starting with the string $0^{n}$, list out each string in ${\bf S}$
in BRGC order. As an illustration of the function $f$, successive applications
of this rule for the set of necklaces of length $6$ starting with the necklace
$000000$ produce the listing in Table 2.

######  Theorem 4.1 ().

If ${\bf S}$ is a flip-swap language including the string $0^{n}$ and $|{\bf
S}|>1$, then $f(\alpha)$ is the string immediately following the string
$\alpha$ in ${\bf S}$ in the cyclic ordering $\mathcal{BRGC}({\bf S})$.

We will provide a detailed proof of this theorem in the next subsection.
Observe that each rule in $f$ complements at most two bits and thus successive
strings in ${\bf S}$ differ by at most two bit positions. Observe that when
$0^{n}$ is excluded from ${\bf S}$, then $\mathcal{BRGC}({\bf S})$ is still a
$2$-Gray code (although not necessarily cyclic). This proves Theorem 1.2.

###  4.1 Proof of Theorem 4.1

This section proves Theorem 4.1. We begin with a lemma by Vajnovszki [23], and
a remark that is due to the fact that $0^{n-1}1$ is in a flip-swap language
${\bf S}$ when $|{\bf S}|>1$.

######  Lemma 4.

Let $\alpha=b_{1}b_{2}\cdots b_{n}$ and $\beta$ be length $n$ binary strings
such that $\alpha\neq\beta$. Let $r$ be the rightmost position in which
$\alpha$ and $\beta$ differ. Then $\alpha$ comes before $\beta$ in BRGC order
(denoted by $\alpha\prec\beta$) if and only if $w(b_{r}b_{r+1}\cdots b_{n})$
is even.

######  Remark 1.

A flip-swap language ${\bf S}$ in BRGC order ends with $0^{n-1}1$ when $|{\bf
S}|>1$.

Let $succ({\bf S},\alpha)$ be the _successor_ of $\alpha$ in ${\bf S}$ in BRGC
order (i.e. the string after $\alpha$ in the cyclic ordering
$\mathcal{BRGC}({\bf S})$). Next we provide two lemmas, and then prove Theorem
4.1.

######  Lemma 5.

Let ${\bf S}$ be a flip-swap language with $|{\bf S}|>1$ and $\alpha$ be a
string in ${\bf S}$. Let $t_{\alpha}$ be the leftmost position such that
$flip_{\alpha}(t_{\alpha})\in{\bf S}$. If $w(\alpha)$ is even, then
$t_{\alpha}$ is the rightmost position in which $\alpha$ and $succ({\bf
S},\alpha)$ differ.

###### Proof.

By contradiction. Let $\alpha=b_{1}b_{2}\cdots b_{n}$ and $\beta=succ({\bf
S},\alpha)$. Let $r$ be the rightmost position in which $\alpha$ and $\beta$
differ with $r\neq t_{\alpha}$. If $t_{\alpha}>r$, then $\beta$ has the suffix
$1b_{r+1}b_{r+2}\cdots b_{n}$ since $b_{r}=0$ because
$r<t_{\alpha}\leq\ell_{\alpha}$. Thus by the flip-first property,
$0^{r-1}1b_{r+1}b_{r+2}=flip_{\alpha}(r)\in{\bf S}$ and $r<t_{\alpha}$, a
contradiction.

Otherwise if $t_{\alpha}<r$, then let $\gamma=flip_{\alpha}(t_{\alpha})$.
Clearly $\gamma\neq\alpha$. Now observe that $w(b_{t}b_{t+1}\cdots b_{n})$ is
even because $t_{\alpha}\leq\ell_{\alpha}$ and $w(\alpha)$ is even, and thus
by Lemma 4, $\alpha\prec\gamma$. Also, $\gamma$ has the suffix
$b_{r}b_{r+1}\cdots b_{n}$ and $w(b_{r}b_{r+1}\cdots b_{n})$ is even because
$\alpha\prec\beta$ and $r$ is the rightmost position $\alpha$ and $\beta$
differ, and thus also by Lemma 4, $\gamma\prec\beta$. Thus
$\alpha\prec\gamma\prec\beta$, a contradiction. Therefore $r=t_{\alpha}$. ∎

######  Lemma 6.

Let ${\bf S}$ be a flip-swap language with $|{\bf S}|>1$ and $\alpha\neq
0^{n-1}1$ be a string in ${\bf S}$. If $w(\alpha)$ is odd, then
$\ell_{\alpha}+1$ is the rightmost position in which $\alpha$ and $succ({\bf
S},\alpha)$ differ.

###### Proof.

Since $\alpha\neq 0^{n-1}1$ and $w(\alpha)$ is odd, $\ell_{\alpha}<n-1$. We
now prove the lemma by contradiction. Let $\alpha=b_{1}b_{2}\cdots b_{n}$ and
$\beta=succ({\bf S},\alpha)$. Let $r\neq\ell_{\alpha}+1$ be the rightmost
position in which $\alpha$ and $\beta$ differ. If $r<\ell_{\alpha}+1$, then
$w(b_{r}b_{r+1}\cdots b_{n})$ is odd but $\alpha\prec\beta$, a contradiction
by Lemma 4. Otherwise if $r>\ell_{\alpha}+1$, then let
$\gamma=flip2_{\alpha}(\ell_{\alpha},\ell_{\alpha}+1)$. Clearly
$\gamma\neq\alpha$, and by the flip-first and swap-first properties,
$\gamma\in{\bf S}$. Also, observe that
$w(b_{\ell_{\alpha}+1}b_{\ell_{\alpha}+2}\cdots b_{n})$ is even because
$w(\alpha)$ is odd, and thus by Lemma 4, $\alpha\prec\gamma$. Further,
$\gamma$ has the suffix $b_{r}b_{r+1}\cdots b_{n}$ and $w(b_{r}b_{r+1}\cdots
b_{n})$ is even because $\alpha\prec\beta$ and $r$ is the rightmost position
$\alpha$ and $\beta$ differ, and thus also by Lemma 4, $\gamma\prec\beta$.
Thus $\alpha\prec\gamma\prec\beta$, a contradiction. Therefore
$r=\ell_{\alpha}+1$. ∎

###### Proof of Theorem 4.1.

Let $\alpha=a_{1}a_{2}\cdots a_{n}$ and $\beta=succ({\bf
S},\alpha)=b_{1}b_{2}\cdots b_{n}$. Let $t_{\alpha}$ be the leftmost position
such that $flip_{\alpha}(t_{\alpha})\in{\bf S}$. First we consider the case
when $\alpha=0^{n-1}1$. Recall that the first string in ${\bf B}(n)$ in BRGC
order is $0^{n}$ [15] and $0^{n}$ is a string in ${\bf S}$ by Lemma 3. Also,
the last string in ${\bf S}$ in BRGC order is $0^{n-1}1$ by Remark 1 when
$|{\bf S}|>1$. Thus the string that appears immediately after $\alpha$ in the
cyclic ordering $\mathcal{BRGC}({\bf S})$ is $f(\alpha)$ when
$\alpha=0^{n-1}1$. In the remainder of the proof, $\alpha\neq 0^{n-1}1$ and we
consider the following two cases.

Case 1:

$w(\alpha)$ is even: If $t_{\alpha}=1$, then clearly
$\beta=flip_{\alpha}(t_{\alpha})=f(\alpha)$. For the remainder of the proof,
$t_{\alpha}>1$.

Since $t_{\alpha}\leq\ell_{\alpha}$, $flip2_{\alpha}(t_{\alpha}-1,t_{\alpha})$
has the prefix $0^{t_{\alpha}-2}1$. We now consider the following two cases.
If $flip2_{\alpha}(t_{\alpha}-1,t_{\alpha})\notin{\bf S}$, then
$flip_{\alpha}(t_{\alpha})$ is the only string in ${\bf S}$ that has
$t_{\alpha}$ as the rightmost position that differ with $\alpha$ and has the
prefix $0^{t-2}$. Therefore, $\beta=flip_{\alpha}(t_{\alpha})=f(\alpha)$.
Otherwise, $flip2_{\alpha}(t_{\alpha}-1,t_{\alpha})$ and
$flip_{\alpha}(t_{\alpha})$ are the only strings in ${\bf S}$ that have
$t_{\alpha}$ as the rightmost position that differ with $\alpha$ and have the
prefix $0^{t_{\alpha}-2}$. By Lemma 4,
$flip2_{\alpha}(t_{\alpha}-1,t_{\alpha})\prec flip_{\alpha}(t_{\alpha})$ since
$w(1\overline{a}_{t_{\alpha}}a_{t_{\alpha}+1}a_{t_{\alpha}+2}\cdots a_{n})$ is
even. Thus, $\beta=flip2_{\alpha}(t_{\alpha}-1,t_{\alpha})=f(\alpha)$.

Case 2:

$w(\alpha)$ is odd: By Lemma 6, $\beta$ has the suffix
$\overline{a}_{\ell_{\alpha}+1}a_{\ell_{\alpha}+2}a_{\ell_{\alpha}+3}\cdots
a_{n}$. If $flip_{\alpha}(\ell_{\alpha}+1)\notin{\bf S}$, then by the flip-
first and swap-first properties,
$flip2_{\alpha}(\ell_{\alpha},\ell_{\alpha}+1)$ is the only string in ${\bf
S}$ that has $\ell_{\alpha}+1$ as the rightmost position that differ with
$\beta$. Thus,
$\beta=flip2_{\alpha}(\ell_{\alpha},\ell_{\alpha}+1)=f(\alpha)$. Otherwise by
Lemma 4, any string $\gamma\in{\bf S}$ with the suffix
$\overline{a}_{\ell_{\alpha}+1}a_{\ell_{\alpha}+2}a_{\ell_{\alpha}+3}\cdots
a_{n}$ and $\gamma\neq flip_{\alpha}(\ell_{\alpha}+1)$ has
$flip_{\alpha}(\ell_{\alpha}+1)\prec\gamma$ because
$w(1\overline{a}_{\ell_{\alpha}+1}a_{\ell_{\alpha}+2}a_{\ell_{\alpha}+3}\cdots
a_{n})$ is even. Thus, $\beta=flip_{\alpha}(\ell_{\alpha}+1)=f(\alpha)$.

Therefore, the string immediately after $\alpha$ in the cyclic ordering
$\mathcal{BRGC}({\bf S})$ is $f(\alpha)$. ∎

##  5 Generation algorithm for flip-swap languages

In this section we present a generic algorithm to generate $2$-Gray codes for
flip-swap languages via the function $f$.

A naïve approach to implement $f$ is to find $t_{\alpha}$ by test flipping
each bit in $\alpha$ to see if the result is also in the set when $w(\alpha)$
is even; or test flipping the ($\ell_{\alpha}+1$)-th bit of $\alpha$ to see if
the result is also in the set when $w(\alpha)$ is odd. Since
$t_{\alpha}\leq\ell_{\alpha}$, we only need to examine the length
$\ell_{\alpha}-1$ prefix of $\alpha$ to find $t_{\alpha}$. Such a test can be
done in $O(nm)$ time, where $O(m)$ is the time required to complete the
membership test of the set under consideration. Pseudocode of the function $f$
is given in Algorithm 1.

To list out each string of a flip-swap language ${\bf S}$ in BRGC order, we
can repeatedly apply the function $f$ until it reaches the starting string. We
also maintain $w(\alpha)$ and $\ell_{\alpha}$ which can be easily maintained
in $O(n)$ time for each string generated. We also add a condition to avoid
printing the string $0^{n}$ if $0^{n}$ is not a string in ${\bf S}$.
Pseudocode for this algorithm, starting with the string $0^{n}$, is given in
Algorithm 2. The algorithm can easily be modified to generate the
corresponding counterpart of ${\bf S}$ with respect to $0$.

A simple analysis shows that the algorithm generates ${\bf S}$ in $O(nm)$-time
per string. A more thorough analysis improves this to $O(n+m)$-amortized time
per string.

######  Theorem 5.1.

If ${\bf S}$ is a flip-swap language, then the algorithm BRGC produces
$\mathcal{BRGC}(S)$ in $O(n+m)$-amortized time per string, where $O(m)$ is the
time required to complete the membership tester for ${\bf S}$.

###### Proof.

Let $\alpha=a_{1}a_{2}\cdots a_{n}$ be a string in ${\bf S}$. Clearly $f$ can
be computed in $O(n)$ time when $w(\alpha)$ is odd. Otherwise when $w(\alpha)$
is even, the while loop in line 5 of Algorithm 1 performs a membership tester
on each string $\beta=b_{1}b_{2}\cdots b_{n}$ in ${\bf S}$ with
$b_{\ell_{\alpha}}b_{\ell_{\alpha}+1}\cdots
b_{n}=a_{\ell_{\alpha}}a_{\ell_{\alpha}+1}\cdots a_{n}$ and
$w(b_{1}b_{2}\cdots b_{\ell_{\alpha}-1})=1$. Observe that each of these
strings can only be examined by the membership tester once, or otherwise the
while loop in line 5 of Algorithm 1 produces the same $t_{\alpha}$ which
results in a duplicated string, a contradiction. Thus, the total number of
membership testers performed by the algorithm is bound by $|{\bf S}|$, and
therefore $f$ runs in $O(m)$-amortized time per string. Finally, since the
other part of the algorithm runs in $O(n)$ time per string, the algorithm BRGC
runs in $O(n+m)$-amortized time per string. ∎

The membership tests in this paper can be implemented in $O(n)$ time and
$O(n)$ space; see [3, 7, 20] for necklaces, Lyndon words, prenecklaces and
pseudo-necklaces of length $n$. One exception is the test for prefix normal
words of length $n$, which requires $O(n^{1.864})$ time and $O(n)$ space [5].
Together with the above theorem, this proves Theorem 1.3.

Visit the Combinatorial Object Server [6] for a C implmentation of our
algorithms.

Algorithm 1 Pseudocode of the implementation of the function $f$.

1:

2:function $f$($\alpha$)

3: if $\alpha=0^{n-1}1$ then $flip_{\alpha}(n)$

4: else if $w(\alpha)$ is even then

5: $t_{\alpha}\leftarrow\ell_{\alpha}$

6: while $t_{\alpha}>1$ and $flip_{\alpha}(t_{\alpha}-1)\in{\bf S}$ do
$t_{\alpha}\leftarrow t_{\alpha}-1$

7: if $t_{\alpha}\neq 1$ and $flip2_{\alpha}(t_{\alpha}-1,t_{\alpha})\in{\bf
S}$ then $\alpha\leftarrow flip2_{\alpha}(t_{\alpha}-1,t_{\alpha})$

8: else $\alpha\leftarrow flip_{\alpha}(t_{\alpha})$

9: else

10: if $flip_{\alpha}(\ell_{\alpha}+1)\notin{\bf S}$ then $\alpha\leftarrow
flip2_{\alpha}(\ell_{\alpha},\ell_{\alpha}+1)$

11: else $\alpha\leftarrow flip_{\alpha}(\ell_{\alpha}+1)$

Algorithm 2 Algorithm to list out each string of a flip-swap language ${\bf
S}$ in BRGC order.

1:

2:procedure BRGC

3: $\alpha=b_{1}b_{2}\cdots b_{n}\leftarrow 0^{n}$

4: do

5: if $\alpha\neq 0^{n}$ or $0^{n}\in{\bf S}$ then Print$(\alpha)$

6: $f(\alpha)$

7: $w(\alpha)\leftarrow 0$

8: for $i$ from $n$ down to $1$ do

9: if $b_{i}=1$ then $w(\alpha)\leftarrow w(\alpha)+1$

10: if $b_{i}=1$ then $\ell_{\alpha}\leftarrow i$

11: while $\alpha\neq 0^{n}$

## References

  * [1] J. Arndt.  Matters Computational: Ideas, Algorithms, Source Code.  Springer, 2011.
  * [2] S. Bacchelli, E. Barcucci, E. Grazzini, and E. Pergola.  Exhaustive generation of combinatorial objects by ECO.  Acta Informatica, 40(8):585–602, 2004.
  * [3] K. S. Booth.  Lexicographically least circular substrings.  Inf. Process. Lett., 10(4/5):240–242, 1980.
  * [4] B. Bultena and F. Ruskey.  An Eades-McKay algorithm for well-formed parenthesis strings.  Inf. Process. Lett., 68(5):255–259, 1998.
  * [5] T. M. Chan and M. Lewenstein.  Clustered integer 3SUM via additive combinatorics.  In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC 15, pages 31–40, New York, NY, USA, 2015.
  * [6] COS++.  The Combinatorial Object Server.  http://combos.org/brgc.
  * [7] J. P. Duval.  Factorizing words over an ordered alphabet.  J. Algorithms, 4(4):363–381, 1983.
  * [8] G. Ehrlich.  Loopless algorithms for generating permutations, combinations, and other combinatorial configurations.  J. ACM, 20(3):500–513, 1973.
  * [9] R. Graham, D. Knuth, and O. Patashnik.  Concrete Mathematics: A Foundation for Computer Science.  Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1994.
  * [10] F. Gray.  Pulse code communication, 1953.  US Patent 2,632,058.
  * [11] E. Hartung, H. P. Hoang, T. Mütze, and A. Williams.  Combinatorial generation via permutation languages.  In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’20, page 1214–1225, USA, 2020.
  * [12] D. Knuth.  The Art of Computer Programming. Volume 4, fascicule 2., Generating all tuples and permutations.  The Art of Computer Programming. Addison-Wesley, Upper Saddle River (N.J.), 2005.  Autre tirage : 2010.
  * [13] Y. Li and J. Sawada.  Gray codes for reflectable languages.  Inf. Process. Lett., 109(5):296 – 300, 2009.
  * [14] T. Mütze.  Proof of the middle levels conjecture.  Proceedings of the London Mathematical Society, 112:677––713, 2016.
  * [15] F. Ruskey.  Combinatorial Generation.  Working version (1j-CSC 425/520) edition, 2003.
  * [16] F. Ruskey and A. Proskurowski.  Generating binary trees by transpositions.  J. Algorithms, 11(1):68 – 84, 1990.
  * [17] F. Ruskey, J. Sawada, and A. Williams.  Binary bubble languages and cool-lex order.  J. Comb. Theory Ser. A, 119(1):155 – 169, 2012.
  * [18] F. Ruskey and A. Williams.  Generating balanced parentheses and binary trees by prefix shifts.  In Proceedings of the Fourteenth Symposium on Computing: The Australasian Theory - Volume 77, CATS ’08, pages 107–115, Darlinghurst, Australia, 2008.
  * [19] C. Savage.  A survey of combinatorial Gray codes.  SIAM Rev., 39(4):605–629, 1997.
  * [20] J. Sawada and A. Williams.  A Gray code for fixed-density necklaces and Lyndon words in constant amortized time.  Theor. Comput. Sci., 502:46 – 54, 2013.
  * [21] J. Sawada, A. Williams, and D. Wong.  Necklaces and Lyndon words in colexicographic and reflected Gray code order.  J. Discrete Algorithms, 46-47:25–35, 2017.
  * [22] T. Takaoka.  An $O(1)$ time algorithm for generating multiset permutations.  In Algorithms and Computation, 10th International Symposium, ISAAC ’99, Chennai, India, December 16-18, 1999, Proceedings, volume 1741 of Lecture Notes in Computer Science, pages 237–246. Springer, 1999.
  * [23] V. Vajnovszki.  More restrictive Gray codes for necklaces and Lyndon words.  Inf. Process. Lett., 106(3):96–99, 2008.
  * [24] V. Vajnovszki and T. Walsh.  A loop-free two-close Gray-code algorithm for listing $k$-ary Dyck words.  J. Discrete Algorithms, 4(4):633–648, 2006.
  * [25] T. Walsh.  Generating Gray codes in $O(1)$ worst-case time per word.  In Discrete Mathematics and Theoretical Computer Science, 4th International Conference, DMTCS 2003, Dijon, France, July 7-12, 2003. Proceedings, volume 2731 of LNCS, pages 73–88. Springer, 2003.
  * [26] H. S. Wilf.  A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects.  Adv. Math., 24:281–291, 1977.
  * [27] H. S. Wilf and A. Nijenhuis.  Combinatorial Algorithms: For Computers and Calculators.  Academic Press, 2nd edition, 1978.
  * [28] A. Williams.  The greedy Gray code algorithm.  In 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings, pages 525–536, 2013.

Appendix: Proofs for flip-swap languages

This section provides the proofs for the remainder of the languages in Theorem
1.1. Unless otherwise stated, the discussion of flip-swap languages are with
respect to 1.

### Binary strings with weight $\leq k$

Recall the weight of a binary string is the number of 1s it contains. Let
${\bf S}$ be the set of binary strings of length $n$ having weight less than
or equal to some $k$. Observe that ${\bf S}$ satisfies the two closure
properties of a flip-swap language as the flip-first and swap-first operations
either decrease or maintain the weight. Thus, ${\bf S}$ is a flip-swap
language.

### Binary strings $\leq\gamma$

Let ${\bf S}$ be the set of binary strings of length $n$ with each string
lexicographically smaller or equal to some string $\gamma$. Observe that ${\bf
S}$ satisfies the two closure properties of a flip-swap language as the flip-
first and swap-first operations either make the resulting string
lexicographically smaller or produce the same string. Thus, ${\bf S}$ is a
flip-swap language.

### Binary strings with $\leq k$ inversions

Recall that an _inversion_ with respect to $0^{*}1^{*}$ in a binary string
$\alpha=b_{1}b_{2}\cdots b_{n}$ is any $b_{i}=1$ and $b_{j}=0$ such that
$i<j$. For example when $\alpha=100101$, it has $4$ inversions:
$(b_{1},b_{2}),(b_{1},b_{3}),(b_{1},b_{5}),(b_{4},b_{5})$. Let ${\bf S}$ be
the set of binary strings of length $n$ with less than or equal to $k$
inversions with respect to $0^{*}1^{*}$. Observe that ${\bf S}$ satisfies the
two closure properties of a flip-swap language as the flip-first and swap-
first operations either decrease or maintain the number of inversions. Thus,
${\bf S}$ is a flip-swap language.

### Binary strings with $\leq k$ transpositions

Recall that the number of _transpositions_ of a binary string
$\alpha=b_{1}b_{1}\cdots b_{n}$ with respect to $0^{*}1^{*}$ is the minimum
number of $swap(i,j)$ operations required to change $\alpha$ into the form
$0^{*}1^{*}$. For example, the number of transpositions of the string $100101$
is $1$. Let ${\bf S}$ be the set of binary strings of length $n$ with less
than or equal to $k$ transpositions with respect to $0^{*}1^{*}$. Observe that
${\bf S}$ satisfies the two closure properties of a flip-swap language as the
flip-first and swap-first operations either decrease or maintain the number of
transpositions. Thus, ${\bf S}$ is a flip-swap language.

### Binary strings $<\text{or}\leq$ their reversal

Let ${\bf S}$ be the set of binary strings of length $n$ with each string
lexicographically smaller than their reversal. Observe that ${\bf S}$
satisfies the swap-first property as the swap-first operation either produces
the same string, or makes the resulting sting lexicographically smaller while
its reversal lexicographically larger. Furthermore, ${\bf S}\cup\\{0^{n}\\}$
satisfies the flip-first property as the flip-first operation complements the
most significant bit of $\alpha$ but the least significant bit of its reversal
when $w(\alpha)>1$; or otherwise produces the string $0^{n}$ when
$w(\alpha)=1$. Thus, ${\bf S}$ is a flip-swap language. The proof for the set
of binary strings of length $n$ with each string lexicographically smaller
than or equal to their reversal is similar to the proof for ${\bf S}$.

Equivalence class of strings under reversal has also been called neckties
[19].

### Binary strings $<\text{or}\leq$ their complemented reversal

Let ${\bf S}$ be the set of binary strings of length $n$ with each string
lexicographically smaller than (or equal to) its complemented reversal.
Observe that ${\bf S}$ satisfies the flip-first property as the flip-first
operation makes the resulting string lexicographically smaller while its
complemented reversal lexicographically larger. Furthermore, ${\bf S}$
satisfies the swap-first property as the swap-first operation either produces
the same string, or complements the most significant bit of $\alpha$ and also
a $1$ of its complemented reversal. Thus, the resulting string must also be
less than its complemented reversal. Thus, ${\bf S}$ is a flip-swap language.

### Binary strings with forbidden $10^{t}$

Let ${\bf S}$ be the set of binary strings of length $n$ without the substring
$10^{t}$. Observe that ${\bf S}$ satisfies the two closure properties of a
flip-swap language as the flip-first and swap-first operations do not create
the substring $10^{t}$. Thus, ${\bf S}$ is a flip-swap language.

### Binary strings with forbidden prefix $1\gamma$

Let ${\bf S}$ be the set of binary strings of length $n$ without the prefix
$1\gamma$. Observe that ${\bf S}$ satisfies the two closure properties of a
flip-swap language as the flip-first and swap-first operations either create a
string with the prefix $0$ or produce the same string. Thus, ${\bf S}$ is a
flip-swap language.

### Lyndon words

Let ${\bf L}(n)$ denote the set of Lyndon words of length $n$. Since ${\bf
N}(n)$ is a flip-swap language and ${\bf L}(n)\cup\\{0^{n}\\}\subseteq{\bf
N}(n)$, it suffices to show that applying the flip-first or the swap-first
operation on a Lyndon word either yields an aperiodic string or the string
$0^{n}$.

Clearly ${\bf L}(n)\cup\\{0^{n}\\}$ satisfies the two closure properties of a
flip-swap language when $\alpha\in\\{0^{n},0^{n-1}1\\}$. Thus in the remaining
of the proof, $\alpha\notin\\{0^{n},0^{n-1}1\\}$. We first prove by
contradiction that ${\bf L}(n)\cup\\{0^{n}\\}$ satisfies the flip-first
closure property. Let $\alpha=0^{j}1b_{j+2}b_{j+3}\cdots b_{n}$ be a string in
${\bf L}(n)\cup\\{0^{n}\\}$. Suppose that ${\bf L}(n)\cup\\{0^{n}\\}$ does not
satisfy the flip-first closure property and $flip_{\alpha}(\ell_{\alpha})$ is
periodic. Thus $flip_{\alpha}(\ell_{\alpha})=(0^{j+1}\beta)^{t}$ for some
string $\beta$ and $t\geq 2$. Observe that
$\alpha=0^{j}1\beta(0^{j+1}\beta)^{t-1}$ which is clearly not a Lyndon word, a
contradiction. Therefore ${\bf L}(n)\cup\\{0^{n}\\}$ satisfies the flip-first
closure property.

Then similarly we prove by contradiction that ${\bf L}(n)\cup\\{0^{n}\\}$
satisfies the swap-first property. If $b_{j+2}=1$, then applying the swap-
first operation on $\alpha$ produces the same Lyndon word. Thus in the
remaining of the proof, $b_{j+2}=0$. Suppose that ${\bf L}(n)\cup\\{0^{n}\\}$
does not satisfy the swap-first closure property such that $\alpha\in{\bf
L}(n)\cup\\{0^{n}\\}$ but $swap_{\alpha}(\ell_{\alpha},\ell_{\alpha}+1)$ is
periodic. Thus
$swap_{\alpha}(\ell_{\alpha},\ell_{\alpha}+1)=(0^{j+1}1\beta)^{t}$ for some
string $\beta$ and $t\geq 2$. Thus $\alpha$ contains the prefix $0^{j}1$ but
also the substring $0^{j+1}1$ in its suffix which is clearly not a Lyndon
word, a contradiction. Thus, ${\bf L}(n)$ is a flip-swap language.

In [23], Vajnovszki proved that the BRGC order induces a cyclic $2$-Gray code
for the set of Lyndon words of length $n$.

### Prenecklaces

Recall that a string $\alpha$ is a _prenecklace_ if it is a prefix of some
necklace. In Section 3 we prove that applying the flip-first or the swap-first
operation on a necklace yields a necklace. Thus by the definition of
prenecklace, applying the flip-first or the swap-first operation on a
prenecklace also creates a string that is a prefix of a necklace. Thus, the
set of prenecklaces of length $n$ is a flip-swap language.

### Pseudo-necklaces

Recall that a _block_ with respect to $0^{*}1^{*}$ is a maximal substring of
the form $0^{*}1^{*}$. Each block $B_{i}$ with respect to $0^{*}1^{*}$ can be
represented by two integers $(s_{i},t_{i})$ corresponding to the number of
$0$s and $1$s respectively. For example, the string $\alpha=000110100011001$
can be represented by $B_{4}B_{3}B_{2}B_{1}=(3,2)(1,1)(3,2)(2,1)$. A block
$B_{i}=(s_{i},t_{i})$ is said to be _lexicographically smaller_ than a block
$B_{j}=(s_{j},t_{j})$ (denoted by $B_{i}<B_{j}$) if $s_{i}<s_{j}$ or
$s_{i}=s_{j}$ with $t_{i}<t_{j}$.

A string $\alpha=b_{1}b_{2}\cdots b_{n}=B_{b}B_{b-1}\cdots B_{1}$ is a
_pseudo-necklace_ with respect to $0^{*}1^{*}$ if $B_{b}\leq B_{i}$ for all
$1\leq i<b$. Observe that the set of pseudo-necklaces of length $n$ satisfies
the two closure properties of a flip-swap language as the flip-first and swap-
first operations do not make the first block $B_{b}$ lexicographically larger,
while the remaining blocks either remain the same or become lexicographically
larger. Thus, the set of pseudo-necklaces of length $n$ is a flip-swap
language.

In [21], the authors proved that the BRGC order induces a cyclic $2$-Gray code
for the set of pseudo-necklaces of length $n$.

### Left factors of $k$-ary Dyck words

Recall that a _$k$ -ary Dyck word_ is a binary string of length $n=tk$ with
$t$ copies of $1$ and $t(k-1)$ copies of $0$ such that every prefix has at
most $k-1$ copies of $0$ for every $1$. It is well-known that $k$-ary Dyck
words are in one-to-one correspondence with $k$-ary trees with $t$ internal
nodes. When $k=2$, Dyck words are counted by the Catalan numbers and are
equivalent to _balanced parentheses_. As an example, $110100$ is a $2$-ary
Dyck word and is also a balanced parentheses string while $100110$ is not a
$2$-ary Dyck word nor a balanced parentheses because its prefix of length
three contains more $0$s than $1$s. $k$-ary Dyck words and balanced
parentheses strings are well studied and have lots of applications including
trees and stack-sortable permutations [4, 16, 18, 24].

The set of $k$-ary Dyck words of length $n$ is not a flip-swap language with
respect to $0$ since $110100$ is a $2$-ary Dyck word but $111100$ is not. The
set of length $n$ prefixes of $k$-ary Dyck words is, however, a flip-swap
language with respect to $0$. This set is also called _left factors of $k$-ary
Dyck words_. Let ${\bf S}$ be the set of left factors of $k$-ary Dyck words.
Observe that ${\bf S}$ satisfies the two closure properties of a flip-swap
language with respect to $0$ as the flip-first and swap-first operations do
not increase the number $0$s in the prefix. Thus, ${\bf S}$ is a flip-swap
language with respect to $0$.