<figure><img src="image_1.png" /></figure>

HAL
open science

# Greedy Gray Codes for some Restricted Classes of Binary Words

Nathanaël Hassler, Vincent Vajnovszki, Dennis Wong

► To cite this version:

Nathanaël Hassler, Vincent Vajnovszki, Dennis Wong. Greedy Gray Codes for some Restricted Classes of Binary Words. GASCom 2024, Jun 2024, Bordeaux, France. pp.108 - 112, 10.4204/eptcs.403.23. hal-04979112

HAL Id: hal-04979112

https://hal.science/hal-04979112v1

Submitted on 5 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Greedy Gray Codes for some Restricted Classes of Binary Words

Nathanaël Hassler

Vincent Vajnovszki

Laboratoire d'Informatique de Bourgogne
Dijon, France

nathanael.hassler@ens-rennes.fr

vincent.vajnovszki@u-bourgogne.fr

Dennis Wong

Macao Polytechnic University
Macao, China

cwong@uoguelph.ca

We investigate the existence of greedy Gray codes, based on the choice of the first element in the code, for two classes of binary words: generalized Fibonacci words and generalized Dyck words.

# 1 Introduction

## 1.1 Constrained binary words

### 1's run constrained binary words

Let $n, p \in \mathbb{N}$, $p \ge 2$, and $F_n(p)$ be the set of length $n$ binary words with no $p$ consecutive 1's. $F_n(2)$ is counted by the Fibonacci numbers $f_n$, and in general, $F_n(p)$ is counted by the $p$-order Fibonacci numbers $f_n^{(p)}$. Now let $k \in \mathbb{N}$, and $F_n(p, k)$ be the subset of words in $F_n(p)$ of weight $k$ (i.e., with exactly $k$ 1's). $F_n(p, k)$ is counted by the univariate $p$-nomial coefficient.

### Prefix constrained binary words

Let $k, n, p \in \mathbb{N}$ with $(p+1)k \le n$, and $C_n(p, k)$ be the set of length $n$ binary words of weight $k$ with the property that any prefix contains at least $p$ times as many 0's as 1's. In particular:

* $C_n(0, k)$ is the set of length $n$ binary words of weight $k$ (combinations in binary word representation),

* $C_{2n}(1, n)$ is the set of length $2n$ Dyck words, and it is counted by the Catalan numbers $\binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n+1}\binom{2n}{n}$,

* $C_{3n}(2, n)$ is in bijection with size $3n$ ternary trees (see A001764 in [4]).

More generally, $C_{(p+1)n}(p, n)$ is counted by $\frac{1}{pn+1}\binom{(p+1)n}{n}$, known as the Pfaff–Fuss–Catalan numbers, and the cardinality of $C_n(p, k)$ is established for instance in [5, Equation (2)], using generating functions:

$$|C_n(p, k)| = \binom{n}{k} - p \binom{n}{k-1}. \qquad (1)$$
## 1.2 Gray codes and greedy algorithms

A Gray code for a class of combinatorial objects is a list that contains each object from the class exactly once such that any two consecutive objects in the list differ only by a 'small change' [3]. In this paper we restrict ourselves to Gray codes for restricted classes of same length and same weight binary words (the weight of a binary word being its number of 1's). The 'small changes' we consider here are homogeneous transpositions: two binary words differ by a homogeneous transposition if one can be obtained from the other by transposing a 1 with a 0, and there are no 1's between the transposed bits. A Gray code is called homogeneous if consecutive words differ in a such a way. A list of words is suffix partitioned if words with the same suffix are consecutive in the list.

The next definition of the greedy Gray code algorithm is a specialisation of that introduced in [6] to particular cases of binary words, see also [7].

**Definition 1.1.** For a set $S$ of same length and same weight binary words the greedy Gray code algorithm to obtain a Gray code list $\mathcal{L}$ for the set $S$ is:

1. Initialize $\mathcal{L}$ with a particular word in $S$.

2. For the last word in $\mathcal{L}$, homogeneously transposes the leftmost possible 1 with the leftmost possible 0, such that the obtained word is in $S$ but not in $\mathcal{L}$.

3. If at point 2. a new word is obtained, then append it to the list $\mathcal{L}$ and return to point 2.

In the following we will say that the list $\mathcal{L}$ is obtained by applying the greedy algorithm for $S$ to $\alpha$, where $\alpha$ is the initial word of $\mathcal{L}$. Depending on the choice of $\alpha$, it can happen that the obtained list $\mathcal{L}$ is not an exhaustive one for $S$.

# 2 Tail partitioned lists

The tail of a binary word is its unique suffix of the form $011\cdots1$, and the only words with no tail have the form $11\cdots1$. Note that 0 is also a tail, for the words ending by 0.

A list of binary words is increasing (decreasing) tail partitioned if words with tails of length $\ell$ appear before (after) words with tail of length $\ell+1$, for any $\ell \ge 1$.

**Definition 2.1.** A list $\mathcal{L}$ of same length binary words is recursive tail partitioned if it is empty, or

* it is increasing or decreasing tail partitioned, and

* for any tail $t$, the list obtained by: (i) considering the sublist of $\mathcal{L}$ of words with tail $t$, then (ii) erasing the tail $t$ in each word of this sublist, is in turn recursive tail partitioned.

In the following $\cdot$ denotes the concatenation (of two words, or of each word in a list with a word) and the comma appends lists. With this notation, $\mathcal{L}$ is a recursive tail partitioned list if it is empty or has the form

$$ \mathcal{L} = \mathcal{L}_1 \cdot 01^u, \mathcal{L}_2 \cdot 01^{u+1}, \mathcal{L}_3 \cdot 01^{u+2}, \dots, \mathcal{L}_{\ell+1} \cdot 01^{u+\ell} \quad (2) $$

or the form

$$ \mathcal{L} = \mathcal{L}_1 \cdot 01^{u+\ell}, \mathcal{L}_2 \cdot 01^{u+\ell-1}, \mathcal{L}_3 \cdot 01^{u+\ell-2}, \dots, \mathcal{L}_{\ell+1} \cdot 01^u \quad (3) $$

for some $u, \ell \ge 0$, and each list $\mathcal{L}_i$, is in turn recursive tail partitioned.

We remark that the list in (2) is not necessarily the reverse of that in (3). Clearly, a recursive tail partitioned list (r-t partitioned list for short) is a suffix partitioned list.

**Theorem 2.2.** If the list $\mathcal{L}$ is a homogeneous and suffix partitioned Gray code for a set of (same length and same weight) binary words, then $\mathcal{L}$ is an r-t partitioned list.
# 3 Main results

## 3.1 Fibonacci words $F_n(2, k)$

In this subsection we show that for any $\alpha \in F_n(2, k)$, by applying the greedy algorithm for $F_n(2, k)$ to $\alpha$, a suffix partitioned list is obtained, and we characterize the words $\alpha$ such that the greedy algorithm yields an exhaustive list for $F_n(2, k)$. Moreover, for every $\alpha \in F_n(2, k)$ we characterize the last word in the obtained list.

For $n < 2k - 1$, $F_n(2, k)$ is empty and in two particular cases $F_n(2, k)$ is a singleton set.

**Fact 3.1.** If $k = 0$, then $F_n(2, k) = \{0^n\}$, and if $n = 2k - 1$, then $F_n(2, k) = \{1(01)^{k-1}\}$.

For $\alpha \in F_n(2, k)$ we denote by $\mathcal{F}(\alpha)$ the list obtained by applying the greedy algorithm for $F_n(2, k)$ to $\alpha$.

For $n, k$ with $n \ge 2k$, let $\alpha_{n,k}^i = 0^i 1 (01)^{k-1} 0^{n-2k+1-i}$, for $0 \le i \le n - 2k + 1$. Furthermore, let $\gamma_{n,k} := \alpha_{n,k}^{n-2k+1} = 0^{n-2k}(01)^k$. We denote by $\text{GenF}(n,k)$ the set of words $\alpha \in F_n(2, k)$ such that $\mathcal{F}(\alpha)$ is a homogeneous Gray code for $F_n(2, k)$. Equivalently, $\alpha \in \text{GenF}(n,k)$ if and only if $\mathcal{F}(\alpha)$ contains every word of $F_n(2, k)$.

**Theorem 3.2.** Let $n \in \mathbb{N}^*$. Then for all $k$ with $n \ge 2k$, we have

1. $\alpha_{n,k}^i \in \text{GenF}(n,k)$ for all $0 \le i \le n - 2k$, and $\mathcal{F}(\alpha_{n,k}^i)$ is a suffix partitioned list, with $\gamma_{n,k}$ as last word.

2. $\gamma_{n,k} \in \text{GenF}(n,k)$, $\mathcal{F}(\gamma_{n,k})$ is a suffix partitioned list and its last word is

(i) $\alpha_{n,k}^0$ if $k$ is even,

(ii) $\alpha_{n,k}^{n-2k}$ if $k$ is odd.

In the next lemma, we extend the result of 1. in Theorem 3.2 concerning the last element of $\mathcal{F}(\alpha)$ to each $\alpha \in F_n(2, k)$.

**Lemma 3.3.** Let $n \ge 2k$. For any $\alpha \in F_n(2, k)$ with $\alpha \ne \gamma_{n,k}$, the last word of $\mathcal{F}(\alpha)$ is $\gamma_{n,k}$.

Now we generalise the property for $\mathcal{F}(\alpha)$ to be suffix partitioned to each word of $F_n(2, n)$.

**Lemma 3.4.** Let $n \ge 2k - 1$. For any $\alpha \in F_n(2, k)$, $\mathcal{F}(\alpha)$ is a suffix partitioned list.

Now we are able to completely describe the set $\text{GenF}(n,k)$.

**Proposition 3.5.** Let $n \ge 2k - 1$. Then

$$ \text{GenF}(n,k) = \{0^i 1 (01)^{k-1} 0^{n-2k+1-i} \mid 0 \le i \le n - 2k + 1\}. $$

In particular, $|\text{GenF}(n,k)| = n - 2k + 2$.

## 3.2 $C_n(p, k)$

For $n, p, k$ such that $n \ge (p+1)k$ and $\alpha \in C_n(p, k)$, we denote by $\mathcal{D}_p(\alpha)$ the list obtained by applying the greedy algorithm for $C_n(p, k)$ to $\alpha$. Let also $\text{Gen}_p(n, k)$ be the set of words $\alpha \in C_n(p, k)$ such that $\mathcal{D}_p(\alpha)$ is a homogeneous Gray code for $C_n(p, k)$. Equivalently, $\alpha \in \text{Gen}_p(n, k)$ if and only if $\mathcal{D}_p(\alpha)$ contains every word of $C_n(p, k)$. Since the situation is a bit more complicated than the one for Fibonacci words, for clarity we first investigate the case $p \in \mathbb{N}$, explaining every details of the proofs. Then we explain how the results are generalised to any $p \in \mathbb{R}$, not necessarily describing each proof.
### 3.2.1 $p \in \mathbb{N}$

We start by investigating the case $p \in \mathbb{N}$. We fix such a $p$ throughout this section. For $n \ge (p+1)k$, let $\alpha_{n,k}^{i,j} := 0^{p-j}1^{j-1}0^i1(0^p1)^{k-j}0^{n-(p+1)k}$ (resp. $\alpha_{n,k} = 1^k0^{n-k}$) for $i = 0, \dots, p-1$ and $j = 1, \dots, k$ if $p \ge 1$ (resp. if $p=0$), and $\beta_{n,k}^i := 0^i1^k0^{n-i-k}$ for $i = pk+1, \dots, n-k$. Because it plays a special role, we will use different notation for $\beta_{n,k}^{n-k}$, so we set $\gamma_{n,k} := \beta_{n,k}^{n-k} = 0^{n-k}1^k$.

**Theorem 3.6.** Let $n \ge (p+1)k$, with $k \ge 1$.

1. For all $0 \le i \le p-1$ and $1 \le j \le k$, we have $\alpha_{n,k}^{i,j} \in \text{Gen}_p(n,k)$ (resp. $\alpha_{n,k} \in \text{Gen}_0(n,k)$), and $\mathcal{D}_p(\alpha_{n,k}^{i,j})$ (resp. $\mathcal{D}_0(\alpha_{n,k})$) is a suffix partitioned list with $\gamma_{n,k}$ as last word.

2. For all $j$, $pk+1 \le j \le n-k-1$, we have $\beta_{n,k}^j \in \text{Gen}_p(n,k)$, and $\mathcal{D}_p(\beta_{n,k}^j)$ is a suffix partitioned list with $\gamma_{n,k}$ as last word.

3. $\gamma_{n,k} \in \text{Gen}_p(n,k)$, $\mathcal{D}_p(\gamma_{n,k})$ is a suffix partitioned list and its last word is

(i) $0^p1$ if $(n,k) = (p+1,1)$,

(ii) $\beta_{n,k}^{n-k-1} = 0^{n-k-1}1^k0$ if $k$ is odd and $n \ne (p+1)k$,

(iii) $\alpha_{n,k}^{1,k-1} = 0^{(k-1)p-1}1^{k-2}010^p1$ if $k \ge 3$ is odd and $n = (p+1)k$ (resp. $\alpha_{n,k} = 1^k$ if $p=0$),

(iv) $\alpha_{n,k}^{1,k} = 0^{kp-1}1^{k-1}010^{n-(p+1)k}$ if $k$ is even (resp. $\alpha_{n,k} = 1^k0^{n-k}$ if $p=0$).

**Lemma 3.7.** Let $n \ge (p+1)k$. For all $\alpha \in C_n(p,k)$, with $\alpha \ne \gamma_{n,k}$, $\mathcal{D}_p(\alpha)$ ends with $\gamma_{n,k}$.

**Lemma 3.8.** Let $n \ge 1$. Then for all $k$ with $n \ge (p+1)k$, and for each $\alpha \in C_n(p,k)$, $\mathcal{D}_p(\alpha)$ is a suffix partitioned list.

**Proposition 3.9.** Let $n \ge (p+1)k$. If $p \ge 1$ then

$$ \text{Gen}_p(n,k) = \bigcup_{j=1}^{k} \{0^{p-j}1^{j-1}0^i1(0^p1)^{k-j}0^{n-(p+1)k} \mid 0 \le i \le p-1\} \\ \cup \{0^i1^k0^{n-i-k} \mid pk+1 \le i \le n-k\}. $$

If $p=0$ then $\text{Gen}_0(n,k) = \{0^i1^k0^{n-i-k} \mid 0 \le i \le n-k\}$. In particular,

$$ |\text{Gen}_p(n,k)| = n - k + 1 - p. $$

**Remark 3.10.** Propositions 3.5 and 3.9 highlight the fact that the choice of the first element for the greedy algorithm is crucial. Indeed, only a few elements will produce a Gray code for $F_n(2,k)$ or $C_n(p,k)$ with this algorithm.

### 3.2.2 $p \in \mathbb{R}_+$

The previous results can be generalized to $C_n(p,k)$ for any $p \in \mathbb{R}_+$. In particular we have the following result:

**Theorem 3.11.** Let $p \in \mathbb{R}_+$ and $n \ge (p+1)k$. Then

$$ |\text{Gen}_p(n,k)| = n - k + 1 - \lceil p \rceil. $$
## 3.3 Algorithmic considerations

Building on the previous results, the last part presents CAT algorithms that greedily generate Gray code for $C_n(p, k)$ and $F_n(2, k)$, which we omit in this abstract.

## References

[1] A. Bultena & F. Ruskey (1998): *An Eades-McKay algorithm for well-formed parentheses strings*. Information Processing Letters 68, pp. 255-259, doi:10.1016/S0020-0190(98)00171-9.

[2] P. Eades & B. McKay (1984): *An algorithm for generating subsets of fixed size with a strong minimal change property*. Information Processing Letters 19, pp. 131-133, doi:10.1016/0020-0190(84)90091-7.

[3] Torsten Mütze (2023): *Combinatorial Gray codes – an updated survey*. Electronic Journal of Combinatorics 30(3):DS26, doi:10.37236/11023.

[4] N.J.A. Sloane: *The On-Line Encyclopedia of Integer Sequences*. Available at http://oeis.org/.

[5] V. Vajnovszki & T. Walsh (2006): *A loop-free two-close Gray code algorithm for listing k-ary Dyck words*. Journal of Discrete Algorithms 4(4), pp. 633-648, doi:10.1016/j.jda.2005.07.003.

[6] A. Williams (2013): *The greedy Gray code algorithm*. In: Proceedings of the 13th international conference on Algorithms and Data Structures, p. 525-536, doi:10.1007/978-3-642-40104-6_46.

[7] D. Wong & V. Vajnovszki (2023): *Greedy Gray codes for Dyck words and ballot sequences*. In: Computing and Combinatorics. COCOON 2023, Lecture Notes in Computer Science 14423, Springer, pp. 29-40, doi:10.1007/978-3-031-49193-1_3.