Snake-in-the-box codes under the $\ell _{\infty }$-metric for rank modulation

Abstract

In the rank modulation scheme, Gray codes are very useful in the realization of flash memories. For a Gray code in this scheme, two adjacent codewords are obtained by using some “push-to-the-top” operations. Moreover, snake-in-the-box codes under the $\ell _{\infty }$-metric ($\ell _{\infty }$-snakes) are Gray codes, which can be capable of detecting one $\ell _{\infty }$-error. In this paper, we give two constructions of $\ell _{\infty }$-snakes. On the one hand, inspired by Yehezkeally and Schwartz’s construction, we present a new construction of the $\ell _{\infty }$-snake. The length of this $\ell _{\infty }$-snake is longer than the length of the $\ell _{\infty }$-snake constructed by Yehezkeally and Schwartz. On the other hand, we also give another construction of $\ell _{\infty }$-snakes by using ${\mathcal {K}}$-snakes and obtain the longer $\ell _{\infty }$-snakes than the previously known ones.

1 Introduction

Flash memory is a non-volatile storage medium that is both electrically programmable and erasable. It has been widely used because of its reliability, relative low cost, and high storage density. In flash memories, a block which contains many cells can maintain a block of charge levels to represent information. However, the flash memory has its inherent asymmetry between cell programming (injecting cells with charge) and cell erasure (removing charge from cells). That is to say, increasing the charge level of a single cell (cell programming) is an easy operation, but decreasing the charge level of a single cell (cell erasure) is a very difficult process. In the programming operation, some cells may be injected with extra charge. This will lead to overshooting of charge. Hence, overprogramming (overshooting of charge) is a severe problem because of some very difficult cell erasure operations.

The rank modulation scheme has been recently proposed in [9] to overcome these problems. In this scheme, one permutation is induced by relative rankings of the charge levels on a group of cells instead of using absolute values of charge levels. This permutation is used to represent information. Specifically, assume that $c_1,c_2,\ldots ,c_n\in {\mathbb {R}}$ represent charge levels of $n\in {\mathbb {N}}$ cells respectively, these charge levels induce one permutation $\pi =[\pi (1),\ldots ,\pi (n)]\in S_n$ such that $c_{\pi (1)}>c_{\pi (2)}>\cdot \cdot \cdot >c_{\pi (n)}$, where $S_n$ is the set of all the permutations over $\{1,2,\ldots ,n\}$. In the rank modulation scheme, the cell programming uses only “push-to-the-top” operations [9]. That is, a cell is programmed by raising the charge level of this cell above those of all others in the block. Hence, in the manner, the overprogramming is no longer a problem.

If the relative rankings are changed because of injection of much extra charge or leakage in the cells, the permutation induced by the relative rankings will be different from the desired permutation, i.e., this leads to an encoding error. Hence, some error models have been studied for rank modulation, including the $\ell _{\infty }$-metric [11, 15], the Ulam metric [4], and the Kendall’s $\tau$-metric [1, 10, 12, 17]. In this paper, we will focus on the $\ell _{\infty }$-metric and the Kendall’s $\tau$-metric.

The $\ell _{\infty }$-distance [15] between two permutations $\pi ,\sigma \in S_n$ is the maximal number of indices difference between $\pi$ and $\sigma$. For example, the $\ell _{\infty }$-distance between $\pi =[1,2,3]$ and $\sigma =[3,1,2]$ is 2, since $\max \limits _{i\in \{1,2,3\}}|\sigma (i)-\pi (i)|=2$. Moreover, the Kendall’s$\tau$-distance [15] between two permutations $\pi , \sigma \in S_n$ is the minimum number of adjacent transpositions required to obtain the permutation $\sigma$ from $\pi$, where an adjacent transposition is an exchange of two distinct adjacent elements. For example, the Kendall’s $\tau$-distance between $\pi =[1,2,3]$ and $\sigma =[3,1,2]$ is 2, since we can do the adjacent transpositions $[1,2,3]\rightarrow [1,3,2]\rightarrow [3,1,2]$.

In the rank modulation scheme, Gray codes are important codes which represent information in flash memories. In [9], Jiang et al. proposed the Gray codes by using “push-to-the-top” operations. Recently, Gray codes for rank modulation have been studied in [5, 6, 10, 15]. In addition, a snake-in-the-box code is a Gray code in which the distance between any two distinct codewords in the code under a given metric is at least 2. Thus, this code can detect a single error in one codeword. In this paper, we will focus on the snake-in-the-box codes under the $\ell _{\infty }$-metric and the Kendall’s $\tau$-metric.

In [15], Yehezkeally and Schwartz constructed directly a snake-in-the-box code of length $\lceil \frac{n}{2}\rceil !(\lfloor \frac{n}{2}\rfloor +(\lfloor \frac{n}{2}\rfloor -1)!)$ in $S_{n}$ under the $\ell _{\infty }$-metric. In this paper, we will improve on this result. On the one hand, we will construct a snake-in-the-box code of length $\lceil \frac{n}{2}\rceil !(\lfloor \frac{n}{2}\rfloor +(\lfloor \frac{n}{2}\rfloor )!)$ in $S_{n}$ under the $\ell _{\infty }$-metric. On the other hand, we will also construct the longer snake-in-the-box code under the $\ell _{\infty }$-metric by using some snake-in-the-box codes under the Kendall’s $\tau$-metric. Specifically, when $n=4k+1$ and $k\ge 3$, we can obtain a snake-in-the-box code of length $\frac{(\lceil n/2\rceil !)^2}{2}$ in $S_{n}$ under the $\ell _{\infty }$-metric. When $n=4k+3$ or $n=4k+4$, and $k\ge 2$, we can obtain a snake-in-the-box code of length $\frac{(\lceil n/2\rceil +1)!\cdot \lfloor n/2\rfloor !}{2}$ in $S_{n}$ under the $\ell _{\infty }$-metric.

The rest of this paper is organized as follows. In Sect. 2, we will give some basic definitions for the rank modulation scheme and notations required in this paper. In Sect. 3, we give directly two constructions of snake-in-the-box codes in $S_n$ under the $\ell _{\infty }$-metric. In Sect. 4, we compare our results with the previous ones. Section 5 concludes this paper.

2 Preliminaries

In this section, we will give some definitions and notations mentioned in [8, 15] and [2].

We let $[n]\triangleq \{1,2,\ldots ,n\}$ and let $\pi \triangleq [\pi (1),\pi (2),\ldots ,\pi (n)]$ be a permutation over [n]. Let $S_n$ be the set of all the permutations over [n]. For $\sigma ,\pi \in S_n$, their multiplication $\pi \circ \sigma$ is denoted by the composition of $\sigma$ on $\pi$, i.e., $\pi \circ \sigma (i)=\sigma (\pi (i))$, for all $i\in [n]$. Under this multiplication operation, $S_n$ is a noncommutative group. Let $\pi ^{-1}$ be the inverse element of $\pi$, for $\pi \in S_n$, and let $A_n$ be the subgroup of all even permutations over [n].

Given n flash memory cells, we name these cells $1,2,\ldots ,n$. Let $(c_1,c_2,\ldots ,c_n) \in {\mathbb {R}}^{n}$ be a vector of n real-valued variables, where $c_{i}$ is the charge level of the i-th cell for all $i\in [n]$. In the rank modulation scheme, the n distinct variables $c_1,\ldots ,c_n$ induce one permutation, denoted by $\pi =[\pi (1),\ldots ,\pi (n)]\in S_n$ iff $c_{\pi (1)}>c_{\pi (2)}>\cdot \cdot \cdot >c_{\pi (n)}$.

Definition 1

Given a set ${\mathcal {S}}$ and a set of transformations $T\subset \{f|f:{\mathcal {S}}\rightarrow {\mathcal {S}}\}$, a Gray code over ${\mathcal {S}}$ of size M, is a sequence $C=(c_0,c_1,\ldots ,c_{M-1})$ of M different elements from ${\mathcal {S}}$, called codewords, in which for each $i\in [M-1]$ there exists some ${\tilde{t}}_i\in T$ such that $c_i={\tilde{t}}_i(c_{i-1})$.

For convenience, we denote a transformation sequence of the Gray code C by ${\mathcal {T}}_C$, i.e., ${\mathcal {T}}_C=({\tilde{t}}_1,{\tilde{t}}_2,\ldots ,{\tilde{t}}_{M-1})$. The Gray code is called complete if $M=|{\mathcal {S}}|$, and cyclic if there exists ${\tilde{t}}_{M}\in T$ such that $c_0={\tilde{t}}_{M}(c_{M-1})$.

Consider the Gray codes for rank modulation in flash memories, we have ${\mathcal {S}}=S_n$ and the set of transformations comprises of all the “push-to-the-top” operations in $S_n$, defined by $T_n$. Next, we denote by $t_i:S_n\rightarrow S_n$ one “push-to-the-top” operation on index i, for $2\le i\le n$, that is,

$$\begin{aligned} t_i([a_1,a_2,\ldots ,a_{i-1},a_i,a_{i+1},\ldots ,a_n])=[a_i,&a_1,a_2,\ldots ,a_{i-1}, a_{i+1},\ldots ,a_n], \end{aligned}$$

and a p-transition will be an abbreviation of a “push-to-the-top” operation. Therefore, $T_n=\{t_2,t_3,\ldots ,t_n\}$.

A sequence of p-transitions is called a transition sequence. Given an initial permutation $\pi _0$ in $S_n$ and a transition sequence $(t_{\alpha (1)},t_{\alpha (2)},\ldots ,t_{\alpha (L)})$ with $\alpha (i)\in [n]$ for all $i\in [L]$, we can obtain a sequence of permutations $\pi _0,\pi _1,\ldots ,\pi _L$ in $S_n$, where $\pi _i=t_{\alpha (i)}(\pi _{i-1})$ for all $i\in [L]$. When $\pi _L=\pi _0$ and $\pi _i\ne \pi _j$ for each pair $0\le i<j<L$, the permutation sequence $(\pi _0,\pi _1,\ldots ,\pi _{L-1})$ is a cyclic Gray code, denoted by $C_n$. The transition sequence ${\mathcal {T}}_{C_n}$ is $(t_{\alpha (1)},t_{\alpha (2)},\ldots ,t_{\alpha (L)})$.

Let $d: S\times S \rightarrow {\mathbb {N}}$ be a distance function, which induces a metric ${\mathcal {M}}$ over S. In the following, we will introduce Gray code capable of detecting a single error.

Definition 2

Let ${\mathcal {M}}$ be a metric over S induced by a distance measure d. A cyclic (resp. noncyclic) snake-in-the-box over S under the metric ${\mathcal {M}}$ by using transitions T is a cyclic (resp. noncyclic) Gray code C over S by using T, in which for any two distinct elements $\pi ,\sigma \in C$, we have that $d(\pi ,\sigma )\ge 2$.

In the following, we consider $S=S_n$ and transitions $T=T_n$. For convenience, we call a cyclic (resp. noncyclic) snake-in-the-box code C of size M over $S_n$ under the metric ${\mathcal {M}}$, using transitions $T_n$, a cyclic (resp. noncyclic) $(n,M,{\mathcal {M}})$-snake, or a cyclic (resp. noncyclic) ${\mathcal {M}}$-snake. Moreover, we directly use an ${\mathcal {M}}$-snake and an $(n,M,{\mathcal {M}})$-snake to represent a cyclic ${\mathcal {M}}$-snake and a cyclic $(n,M,{\mathcal {M}}$-snake, respectively, otherwise, we will specially write as a noncyclic ${\mathcal {M}}$-snake or a noncyclic $(n,M,{\mathcal {M}})$-snake.

In this paper, we will consider two metrics: Kendall’s $\tau$-metric ${\mathcal {K}}$ and $\ell _{\infty }$-metric, with their ${\mathcal {K}}$-snakes and $\ell _{\infty }$-snakes, respectively. The Kendall’s $\tau$-distance and the $\ell _{\infty }$-distance over $S_n$ are defined as follows.

Definition 3

For any two permutations $\sigma ,\pi \in S_n$, the $\ell _{\infty }$-distance between two permutations $\pi ,\sigma$, denoted by $d_{\infty }(\pi ,\sigma )$, is the maximal number of indices difference between $\pi$ and $\sigma$. Specially, we have the following expression for $d_{\infty }(\sigma ,\pi )$,

$$\begin{aligned} d_{\infty }(\sigma ,\pi )=\max \limits _{i\in [n]}|\sigma (i)-\pi (i)|. \end{aligned}$$

Given a permutation $\pi =[a_1,\ldots ,a_n]\in S_n$, an adjacent transposition is an exchange of two distinct adjacent elements $a_i, a_{i+1}$, in $\pi$, for some $1\le i\le n-1$.

Definition 4

For any two permutations $\sigma ,\pi \in S_n$, the Kendall’s $\tau$-distance between two permutations $\pi , \sigma$, denoted by $d_K(\pi ,\sigma )$, is the minimum number of adjacent transpositions required to obtain the permutation $\sigma$ from $\pi$. Specially, we have the following expression for $d_K(\pi ,\sigma )$,

$$\begin{aligned} d_{K}(\sigma ,\pi )=|\{(i,j):\sigma ^{-1}(i)<\sigma ^{-1}(j) \wedge \pi ^{-1}(i)>\pi ^{-1}(j)\}|. \end{aligned}$$

Furthermore, let $C_{{\mathcal {T}}_{C}}^{\pi _0}$ be an $(n,M,{\mathcal {M}})$-snake, where ${\mathcal {T}}_C$ is its transition sequence and $\pi _0$ is its first permutation. Here, we let $C_{{\mathcal {T}}_{C}}^{\pi _0}\triangleq (\pi _0,\pi _1,\ldots ,\pi _{M-1})$ and ${\mathcal {T}}_{C}\triangleq (t_{\alpha (1)},t_{\alpha (2)},\ldots ,t_{\alpha (M)})$ such that $\pi _i=t_{\alpha (i)}(\pi _{i-1})$ for every $i\in [M-1]$ and $t_{\alpha (M)}(\pi _{M-1})=\pi _0$.

In [9], Jiang et al. presented an n-length rank modulation Gray code (n-RMGC) by using “push-to-the-top” transitions. They [9] also proposed a cyclic and complete n-RMGC, $C_{{\mathcal {T}}_{n}}$, where ${\mathcal {T}}_{n}$ is its transition sequence. For convenience, we define ${\mathcal {T}}_{n}\triangleq (t_{\gamma _{n}(1)},t_{\gamma _{n}(2)}\ldots ,t_{\gamma _{n}(n!)})$. Yehezkeally and Schwartz [15] constructed an $(n,M,\ell _{\infty })$-snake, whose size is $\lceil \frac{n}{2}\rceil !(\lfloor \frac{n}{2}\rfloor +(\lfloor \frac{n}{2}\rfloor -1)!)$ for all $n\ge 4$.

Having the above definitions and notations, we will present two constructions of $\ell _{\infty }$-snakes in the following section.

3 Main results

3.1 Construction of $\ell _{\infty }$-snakes by using cyclic and complete RMGCs

In this subsection, we give one construction of $\ell _{\infty }$-snakes by using cyclic and complete RMGCs. In order to use the code constructions presented in [9], we will give the following two lemmas.

Lemma 1

[9, Theorem 4] For all $n\ge 3$, there exists a cyclic and complete $(n-1)$-RMGC, denoted by $C_{{\mathcal {T}}_{n-1}}$, where ${\mathcal {T}}_{n-1}\triangleq (t_{\gamma _{n-1}(1)},\ldots ,t_{\gamma _{n-1}((n-1)!)})$.

Lemma 2

[9, Theorem 7] For all $n\ge 4$, given a cyclic and complete $(n-1)$-RMGC, $C_{{\mathcal {T}}_{n-1}}$, denoted by one transition sequence ${\mathcal {T}}_{n-1}=(t_{\gamma _{n-1}(1)},t_{\gamma _{n-1}(2)},\ldots ,t_{\gamma _{n-1}((n-1)!)})$, then the following transition sequence, $(t_{\gamma _{n}(1)},t_{\gamma _{n}(2)}\ldots ,t_{\gamma _{n}(n!)})$, defines an n-RMGC, denoted by $C_{{\mathcal {T}}_{n}}$, that is cyclic and complete:

$$\begin{aligned} t_{\gamma _{n}(k)}= {\left\{ \begin{array}{ll} t_{n-\gamma _{n-1}(\lceil k/n\rceil )+1}, &{} k \equiv 1 (\text { mod }n),\\ t_n, &{} \text {otherwise } \end{array}\right. } \end{aligned}$$

(1)

for all $k\in [n!]$.

By the above lemmas, we can obtain some properties of this RMGC which we will use later.

Lemma 3

For any $n\ge 3$, there exists a cyclic and complete n-RMGC, denoted by $C_{{\mathcal {T}}_{n}}$, where its transition sequence ${\mathcal {T}}_{n}=(t_{\gamma _{n}(1)},\ldots ,t_{\gamma _{n}(n!)})$, such that for any $j\in \{2,3,\ldots ,n\}$, we have that

$$\begin{aligned} t_{\gamma _{n}(i)}=t_j \end{aligned}$$

for some $i\in [n!]$.

Proof

We prove this lemma by induction. By Lemma 1, we have a cyclic and complete n-RMGC, denoted by $C_{{\mathcal {T}}_{n}}$, with its transition sequence ${\mathcal {T}}_{n}=(t_{\gamma _{n}(1)},\ldots ,t_{\gamma _{n}(n!)})$ for any $n\ge 3$. By the construction of [9, Fig. 2], we have one transition sequence of a cyclic and complete 3-RMGC, denoted by $C_{{\mathcal {T}}_{3}}$, where ${\mathcal {T}}_{3}=(t_2,t_3,t_3,t_2,t_3,t_3)$. Hence, for any $j\in \{2,3\}$, there exists i such that

$$\begin{aligned} t_{{\gamma }_{3}(i)}=t_j. \end{aligned}$$

When $n=m$, assume that for any $j\in \{2,3,\ldots ,m\}$, we have that

$$\begin{aligned} t_{\gamma _{m}(i)}=t_j \end{aligned}$$

(2)

for some $i\in [m!]$.

By Lemma 2 and $C_{{\mathcal {T}}_{m}}$, when $n=m+1$, we have a cyclic and complete $(m+1)$-RMGC, denoted by $C_{{\mathcal {T}}_{m+1}}$, with its transition sequence ${\mathcal {T}}_{m+1}=(t_{\gamma _{m+1}(1)},\ldots ,t_{\gamma _{m+1}((m+1)!)})$, where

$$\begin{aligned} t_{\gamma _{m+1}(k)}= {\left\{ \begin{array}{ll} t_{m+2-\gamma _m(\lceil k/(m+1)\rceil )}, &{} k\equiv 1 ( \hbox {mod } m+1),\\ t_{m+1}, &{} \text {otherwise } \end{array}\right. } \end{aligned}$$

(3)

for all $k\in [(m+1)!]$. Since $\gamma _m(\lceil k/(m+1)\rceil )$ ranges over $2,3,\ldots ,m$, by (3), for any $j\in \{2,3,\ldots ,m+1\}$, we can obtain that

$$\begin{aligned} t_{\gamma _{m+1}(i)}=t_j \end{aligned}$$

for some $i\in [(m+1)!]$.

So, there exists a cyclic and complete n-RMGC, denoted by $C_{{\mathcal {T}}_{n}}$, with its transition sequence ${\mathcal {T}}_{n}=(t_{\gamma _{n}(1)},\ldots ,t_{\gamma _{n}(n!)})$ such that for any $j\in \{2,3,\ldots ,n\}$, we have that

$$\begin{aligned} t_{\gamma _{n}(i)}=t_j \end{aligned}$$

for some $i\in [n!]$. This completes the proof by induction.$\square$

The following lemma gives one construction of a basic block which is useful for the construction of $\ell _{\infty }$-snakes by using cyclic and complete RMGCs.

Lemma 4

For all $n\ge 6$, let $\{a_{j}\}_{j=1}^{Q}$ be a set of even integers of [n] and $\{b_{j}\}_{j=1}^{P}$ be a set of odd integers of [n], where $Q=\lfloor \frac{n}{2}\rfloor$ and $P=\lceil \frac{n}{2}\rceil$. Let $\sigma =[b_1,a_2,a_3\ldots ,a_Q,a_1,b_2,b_3,\ldots ,b_P]$ be an initial permutation such that $|a_1-b_1|\ge 2$. Then, there exist two noncyclic $(n,Q!+Q,\ell _{\infty })$-snakes. One noncyclic $(n,Q!+Q,\ell _{\infty })$-snake, denoted by $C_{{\mathcal {T}}_C}^{\sigma ,\pi _1}$, is starting with $\sigma$ and ending with one permutation $\pi _1$, where

$$\begin{aligned} \pi _1=[a_2,a_3,\ldots ,a_{Q-1},a_Q,a_1,b_1,b_2,\ldots ,b_P]. \end{aligned}$$

Another noncyclic $(n,Q!+Q,\ell _{\infty })$-snake, denoted by ${\hat{C}}_{{\mathcal {T}}_{{\hat{C}}}}^{\sigma ,\pi _2}$, is starting with $\sigma$ and ending with one permutation $\pi _2$, where

$$\begin{aligned} \pi _2=[a_2,a_3,\ldots ,a_{Q-1},a_1,a_Q,b_1,b_2,\ldots ,b_P]. \end{aligned}$$

Proof

We prove only the existence of $C_{{\mathcal {T}}_C}^{\sigma ,\pi _1}$, since the proof of the existence of ${\hat{C}}_{{\mathcal {T}}_{{\hat{C}}}}^{\sigma ,\pi _2}$ is similar. For convenience, let $C_{{\mathcal {T}}_C}^{\sigma ,\pi _1}\triangleq (\sigma _0,\sigma _1,\ldots ,\sigma _{Q!+Q-1})$ and ${\mathcal {T}}_C\triangleq (t_{{\alpha }_{1}(1)},t_{{\alpha }_{1}(2)},\ldots ,t_{{\alpha }_{1}(Q!+Q-1)})$.

Now, by Lemma 1, there exists a cyclic and complete Q-RMGC with its transition sequence ${\mathcal {T}}_Q$, where

$$\begin{aligned} {\mathcal {T}}_Q=(t_{\gamma _{Q}(1)},t_{\gamma _{Q}(2)},\ldots ,t_{\gamma _{Q}(Q!)}). \end{aligned}$$

(4)

By Lemma 3, since $Q\ge 3$, we have that

$$\begin{aligned} t_{\gamma _{Q}(s_1)}=t_{Q}~ \text {and}~t_{\gamma _{Q}(s_2)}=t_{Q-1}~~\text {for some } s_1,s_2\in [Q!]. \end{aligned}$$

(5)

By (4) and (5), we can obtain two transition sequences, denoted by ${\mathcal {T}}_{Q}^{1}$ and ${\mathcal {T}}_{Q}^{2}$, where

$$\begin{aligned} {\mathcal {T}}_{Q}^{1}=(t_{\gamma _{Q}(s_1+1)},t_{\gamma _{Q}(s_1+2)},\ldots , t_{\gamma _{Q}(Q!)},t_{\gamma _{Q}(1)},t_{\gamma _{Q}(2)},\ldots , t_{\gamma _{Q}(s_1)}) \end{aligned}$$

and

$$\begin{aligned} {\mathcal {T}}_{Q}^{2}=(t_{\gamma _{Q}(s_2+1)},t_{\gamma _{Q}(s_2+2)},\ldots , t_{\gamma _{Q}(Q!)},t_{\gamma _{Q}(1)},t_{\gamma _{Q}(2)},\ldots , t_{\gamma _{Q}(s_2)}). \end{aligned}$$

For convenience, we define ${\mathcal {T}}_{Q}^{j}\triangleq (t_{\beta _{j}(1)},t_{\beta _{j}(2)},\ldots ,t_{\beta _{j}(Q!)})$ for $j=1,2$. Applying some transition sequence ${\mathcal {T}}_{Q}^{j}$ on one initial permutation ${\hat{\pi }}$, where ${\hat{\pi }}=[c_1,c_2,\ldots ,c_Q]\in S_Q$, we can obtain a cyclic and complete Q-RMGC, denoted by $C_{{\mathcal {T}}_{Q}^{j}}^{{\hat{\pi }}}$, with its last permutation ${\tilde{\pi }}_j$ for $j=1,2$. By the construction of ${\mathcal {T}}_{Q}^{j}$, when $j=1$, we have that

$$\begin{aligned} {\tilde{\pi }}_1=[c_2,c_3,\ldots ,c_{Q-1},c_Q,c_1]. \end{aligned}$$

(6)

When $j=2$, we have that

$$\begin{aligned} {\tilde{\pi }}_2=[c_2,c_3,\ldots ,c_{Q-1},c_1,c_Q]. \end{aligned}$$

Next, we construct the transition sequence of $C_{{\mathcal {T}}_C}^{\sigma ,\pi _1}$. We let $\sigma _0\triangleq \sigma$, then $\sigma _0=[b_1,a_2,\ldots ,a_Q,a_1,b_2,\ldots ,b_P]$. When $1\le j\le Q-1$, we let $t_{\alpha _{1}(j)}=t_Q$. When $j=Q$, we let $t_{\alpha _{1}(Q)}=t_{Q+1}$. If $Q+1\le j\le Q!+Q-1$, we use the transition sequence ${\mathcal {T}}_{Q}^{1}$ to construct the transition $t_{\alpha _{1}(j)}$, and let $t_{\alpha _{1}(j)}=t_{\beta _{1}(j-Q)}$.

Finally, we will prove that for any $0\le i<j\le Q!+Q-1$, we have that $d_{\infty }(\sigma _i,\sigma _j)\ge 2$. By the construction of $t_{\alpha _{1}(j)}$, when $1\le j\le Q-2$, we have that

$$\begin{aligned} \sigma _j=[a_{Q+1-j},\ldots ,a_Q,b_1,a_2,\ldots ,a_{Q-j},a_1,b_2,\ldots ,b_P]. \end{aligned}$$

When $j=Q-1$, we have that

$$\begin{aligned} \sigma _{Q-1}=[a_2,\ldots ,a_Q,b_1,a_1,b_2,\ldots ,b_P]. \end{aligned}$$

When $j=Q$, we have that

$$\begin{aligned} \sigma _Q=[a_1,a_2,\ldots ,a_Q,b_1,b_2,\ldots ,b_P]. \end{aligned}$$

(7)

By (6) and (7), we can obtain that

$$\begin{aligned} \pi _1=\sigma _{Q!+Q-1}=[a_2,\ldots ,a_Q,a_1,b_1,\ldots ,b_P]. \end{aligned}$$

(8)

When $0\le i<j\le Q-1$, we obtain easily that

$$\begin{aligned} d_{\infty }(\sigma _i,\sigma _j)\ge 2. \end{aligned}$$

(9)

When $0\le i\le Q-1~\text {and}~Q\le j\le Q!+Q-1$, we have $\sigma _i(Q+1)=a_1~\text {and}~\sigma _j(Q+1)=b_1$, then

$$\begin{aligned} d_{\infty }(\sigma _i,\sigma _j)\ge&|\sigma _i(Q+1)-\sigma _j(Q+1)|\nonumber \\ =&|a_1-b_1|\nonumber \\ \ge&2. \end{aligned}$$

(10)

When $Q\le i<j\le Q!+Q-1$, we know that the first Q elements of $\sigma _i$ and $\sigma _j$ are different permutations over $\{a_j\}_{j=1}^{Q}$. Since $\{a_j\}_{j=1}^{Q}$ is a set of even integers, then

$$\begin{aligned} d_{\infty }(\sigma _i,\sigma _j)\ge 2. \end{aligned}$$

(11)

Hence, by (8)–(11), we can obtain a noncyclic $(n,Q!+Q,\ell _{\infty })$-snake $C_{{\mathcal {T}}_C}^{\sigma ,\pi _1}$ starting with $\sigma$ and ending with $\pi _1=[a_2,a_3,\ldots ,a_Q,a_1,b_1,b_2,\ldots ,b_P]$.

Similarly, we can construct another noncyclic $(n,Q!+Q,\ell _{\infty })$-snake ${\hat{C}}_{{\mathcal {T}}_{{\hat{C}}}}^{\sigma ,\pi _2}$. Let ${\mathcal {T}}_{{\hat{C}}}\triangleq (t_{{\alpha }_{2}(1)},t_{{\alpha }_{2}(2)},\ldots ,t_{{\alpha }_{2}(Q!+Q-1)})$ and ${\hat{C}}_{{\mathcal {T}}_{{\hat{C}}}}^{\sigma ,\pi _2}\triangleq ({\hat{\sigma }}_0,{\hat{\sigma }}_1,\ldots ,{\hat{\sigma }}_{Q!+Q-1})$. Analogously, when $1\le j\le Q-1$, we let $t_{\alpha _{2}(j)}=t_Q$. When $j=Q$, we let $t_{\alpha _{2}(Q)}=t_{Q+1}$. If $Q+1\le j\le Q!+Q-1$, we let $t_{\alpha _{2}(j)}=t_{\beta _{2}(j-Q)}$. We define ${{\hat{\sigma }}}_0=\sigma$. As the above discussion, we can also obtain another noncyclic $(n,Q!+Q,\ell _{\infty })$-snake ${\hat{C}}_{{\mathcal {T}}_{{\hat{C}}}}^{\sigma ,\pi _2}$ starting with $\sigma$ and ending with $\pi _2=[a_2,a_3,\ldots ,a_{Q-1},a_1,a_Q,b_1,b_2,\ldots ,b_P]$. $\square$

Next we present an example to illustrate the constructions in Lemma 4.

Example 1

Consider $n=6$, we have that $P=Q=3$. By Lemma 4, we will construct two kinds of noncyclic $\ell _{\infty }$-snakes which are basic building blocks for $\ell _{\infty }$-snakes. Now, we will start this example with an initial permutation, denoted by $\sigma _0=[1,4,2,6,3,5]$. In order to construct the blocks, we need one transition sequence of a cyclic and complete 3-RMGC, i.e, ${\mathcal {T}}_3=(t_2,t_3,t_3,t_2,t_3,t_3)$. By Lemma 4, we can obtain two transition sequences ${\mathcal {T}}_{C}$ and ${\mathcal {T}}_{{\hat{C}}}$, where

$$\begin{aligned} {\mathcal {T}}_{C}=(t_3,t_3,t_4,t_2,t_3,t_3,t_2,t_3) \end{aligned}$$

and

$$\begin{aligned} {\mathcal {T}}_{{\hat{C}}}=(t_3,t_3,t_4,t_3,t_3,t_2,t_3,t_3). \end{aligned}$$

Next, we will give two noncyclic $(6,3!+3,\ell _{\infty })$-snakes by the two transition sequences and $\sigma _0$. One noncyclic $(6,3!+3,\ell _{\infty })$-snake is constructed by ${\mathcal {T}}_{C}$ and $\sigma _0$, which is depicted by Fig. 1 as follows.

Another noncyclic $(6,3!+3,\ell _{\infty })$-snake is constructed by ${\mathcal {T}}_{{\hat{C}}}$ and $\sigma _0$, which is depicted by Fig. 2 as follows.

Fig. 1

A noncyclic $(6,3!+3,\ell _{\infty })$-snake constructed by ${\mathcal {T}}_{C}$ and $\sigma _0$

Fig. 2

A noncyclic $(6,3!+3,\ell _{\infty })$-snake constructed by ${\mathcal {T}}_{{\hat{C}}}$ and $\sigma _0$

In the following, by Lemma 4, we will give one construction of an $(n,M,\ell _{\infty })$-snake of size $M=\lceil \frac{n}{2}\rceil !(\lfloor \frac{n}{2}\rfloor +\lfloor \frac{n}{2}\rfloor !)$. Suppose $P\triangleq \lceil \frac{n}{2}\rceil$ and $Q\triangleq \lfloor \frac{n}{2}\rfloor$, then [n] has P odd elements and Q even ones. Consider $n\ge 6$, we let $\sigma _0$ be the first permutation of the $\ell _{\infty }$-snake, where

$$\begin{aligned} \sigma _0=[1,4,\ldots ,2Q-2,2,2Q,3,5\ldots ,2P-1]. \end{aligned}$$

(12)

First, we construct one transition sequence, denoted by ${\mathcal {T}}=\{t_{\gamma (1)},t_{\gamma (2)},\ldots ,t_{\gamma (M)}\}$. ${\mathcal {T}}$ and $\sigma _0$ can yield one permutation sequence, denoted by $C_{{\mathcal {T}}}=(\sigma _0,\sigma _1,\ldots ,\sigma _{M})$, where the codewords satisfy $\sigma _j=t_{\gamma (j)}(\sigma _{j-1})$ for all $1\le j\le M$.

By Lemma 1, we take a cyclic and complete P-RMGC by using the following transition sequence

$$\begin{aligned} {\mathcal {T}}_P=(t_{\gamma _{P}(1)},t_{\gamma _{P}(2)},\ldots ,t_{\gamma _{P}(P!)}). \end{aligned}$$

(13)

By Lemma 4, we can obtain two noncyclic $(n,M_1,\ell _{\infty })$-snakes of size $M_1=Q!+Q$, $C_{{\mathcal {T}}_C}^{\sigma ,\pi _1}$ and ${\hat{C}}_{{\mathcal {T}}_{{\hat{C}}}}^{\sigma ,\pi _2}$, respectively, where $\sigma , \pi _1, \pi _2$ are defined in Lemma 4. $C_{{\mathcal {T}}_C}^{\sigma ,\pi _1}$ is given by the following transition sequence

$$\begin{aligned} {\mathcal {T}}_C=(t_{\alpha _{1}(1)},t_{\alpha _{1}(2)},\ldots ,t_{\alpha _{1}(M_1-1)}). \end{aligned}$$

(14)

Similarly, ${\hat{C}}_{{\mathcal {T}}_{{\hat{C}}}}^{\sigma ,\pi _2}$ is determined by the following transition sequence

$$\begin{aligned} {\mathcal {T}}_{{\hat{C}}}=(t_{\alpha _{2}(1)},t_{\alpha _{2}(2)},\ldots ,t_{\alpha _{2}(M_1-1)}). \end{aligned}$$

(15)

By (12)–(15), we construct the transition sequence ${\mathcal {T}}=(t_{\gamma (1)},\ldots ,t_{\gamma (M)})$. When we use one transition sequence ${\mathcal {T}}_C$ or ${\mathcal {T}}_{{\hat{C}}}$, we must guarantee the initial permutation to satisfy the condition $|a_1-b_1|\ge 2$ of $\sigma$ in Lemma 4. Here, for all $1\le k \le P!$, $\sigma _{(k-1)\cdot (Q!+Q)}$ is the initial permutation. Moreover, $b_1=\sigma _0(1)=1,\sigma _0(Q)=2~\text {and}~a_1=\sigma _0(Q+1)=2Q$ for $\sigma _0$. According to the construction of $\sigma _0$ and Lemma 4, for all $2\le k \le P!$ and $\sigma _{(k-1)\cdot (Q!+Q)}$, we have $a_1=2~\text {or}~2Q$. In order to satisfy these conditions, we construct the transition sequence ${\mathcal {T}}$ as follows.

For all $1\le k\le P!$, we let

$$\begin{aligned} t_{\gamma (k\cdot (Q!+Q))}=t_{\gamma _{P}(k)+Q}. \end{aligned}$$

(16)

By (16), $\sigma _{k\cdot (Q!+Q)}(1)=\sigma _{(k-1)\cdot (Q!+Q)}(\gamma _{P}(k)+Q)$ for all $1\le k\le P!$. When we pick one transition sequence ${\mathcal {T}}_C$ or ${\mathcal {T}}_{{\hat{C}}}$ to apply on $\sigma _{(k-1)\cdot (Q!+Q)}$, by Lemma 4, we obtain that $\sigma _{k\cdot (Q!+Q)}(Q+1)=\sigma _{(k-1)\cdot (Q!+Q)}(Q+1)~\text {or}~\sigma _{(k-1)\cdot (Q!+Q)}(Q)$ for all $1\le k\le P!$. Hence, $\sigma _{k\cdot (Q!+Q)}(1)=\sigma _{(k-1)\cdot (Q!+Q)}(\gamma _{P}(k)+Q)$ and $\sigma _{k\cdot (Q!+Q)}(Q+1)=\sigma _{(k-1)\cdot (Q!+Q)}(Q+1)~\text {or}~\sigma _{(k-1)\cdot (Q!+Q)}(Q)$ for all $1\le k\le P!$. That’s, $\sigma _{(k-1)\cdot (Q!+Q)}(\gamma _{P}(k)+Q)$ and $\sigma _{k\cdot (Q!+Q)}(Q+1)$ are $b_1$ and $a_1$ in Lemma 4 respectively. In order to satisfy the condition $|a_1-b_1|\ge 2$ of $\sigma$ in Lemma 4 for all $1\le k\le P!-1$, we choose one transition sequence ${\mathcal {T}}_C$ or ${\mathcal {T}}_{{\hat{C}}}$ by using the following method.

For all $1\le k\le P!$ and $1\le j\le Q!+Q-1$, when $|\sigma _{(k-1)\cdot (Q!+Q)}(\gamma _{P}(k)+Q)=1~\text {or}~3$, if $\sigma _{(k-1)\cdot (Q!+Q)}(Q+1)=2Q$, we let

$$\begin{aligned} t_{\gamma ((k-1)\cdot (Q!+Q)+j)}=t_{\alpha _{1}(j)}, \end{aligned}$$

(17)

else if $\sigma _{(k-1)\cdot (Q!+Q)}(Q)=2Q$, we let

$$\begin{aligned} t_{\gamma ((k-1)\cdot (Q!+Q)+j)}=t_{\alpha _{2}(j)}. \end{aligned}$$

(18)

Hence, when $|\sigma _{(k-1)\cdot (Q!+Q)}(\gamma _{P}(k)+Q)=1~\text {or}~3$, by using one transition sequence ${\mathcal {T}}_C$ or ${\mathcal {T}}_{{\hat{C}}}$ applied on $\sigma _{(k-1)\cdot (Q!+Q)}$, we always have $\sigma _{k\cdot (Q!+Q)}(Q+1)=2Q$. Then, $|\sigma _{k\cdot (Q!+Q)}(1)-\sigma _{k\cdot (Q!+Q)}(Q+1)|\ge 2$. When $|\sigma _{(k-1)\cdot (Q!+Q)}(\gamma _{P}(k)+Q)=2Q-1$, if $\sigma _{(k-1)\cdot (Q!+Q)}(Q+1)=2$, we let

$$\begin{aligned} t_{\gamma ((k-1)\cdot (Q!+Q)+j)}=t_{\alpha _{1}(j)}, \end{aligned}$$

(19)

else if $\sigma _{(k-1)\cdot (Q!+Q)}(Q)=2$, we let

$$\begin{aligned} t_{\gamma ((k-1)\cdot (Q!+Q)+j)}=t_{\alpha _{2}(j)}. \end{aligned}$$

(20)

Hence, when $|\sigma _{(k-1)\cdot (Q!+Q)}(\gamma _{P}(k)+Q)=2Q-1$, by using one transition sequence ${\mathcal {T}}_C$ or ${\mathcal {T}}_{{\hat{C}}}$ applied on $\sigma _{(k-1)\cdot (Q!+Q)}$, we always have $\sigma _{k\cdot (Q!+Q)}(Q+1)=2$. Then, $|\sigma _{k\cdot (Q!+Q)}(1)-\sigma _{k\cdot (Q!+Q)}(Q+1)|\ge 2$. When $|\sigma _{(k-1)\cdot (Q!+Q)}(\gamma _{P}(k)+Q)=5,7,\ldots ,2Q-3$, we arbitrarily choose one $\alpha _{1}$ or $\alpha _{2}$, i.e.,

$$\begin{aligned} t_{\gamma ((k-1)\cdot (Q!+Q)+j)}=t_{\alpha _{1}(j)}~\text {or}~t_{\alpha _{2}(j)}. \end{aligned}$$

(21)

Thus, when $|\sigma _{(k-1)\cdot (Q!+Q)}(\gamma _{P}(k)+Q)=5,7,\ldots ,2Q-3$, by using one transition sequence ${\mathcal {T}}_C$ or ${\mathcal {T}}_{{\hat{C}}}$ applied on $\sigma _{(k-1)\cdot (Q!+Q)}$, we have $|\sigma _{k\cdot (Q!+Q)}(1)-\sigma _{k\cdot (Q!+Q)}(Q+1)|\ge 2$. Here, when $|\sigma _{(k-1)\cdot (Q!+Q)}(\gamma _{P}(k)+Q)=5,7,\ldots ,~\text {or}~2Q-3$, we can choose some $\alpha _{1}$ or $\alpha _{2}$ such that the number of choices of $\alpha _{2}$ is an even number.

Hence, this construction of the transition sequence satisfies the the condition $|a_1-b_1|\ge 2$ of $\sigma$ in Lemma 4. Next, we will prove that $C_{{\mathcal {T}}}$ is an $\ell _{\infty }$-snake in the following theorem.

Theorem 1

For all $n\ge 6$, there exist an $(n,M,\ell _{\infty })$-snake of size $M=\lceil \frac{n}{2}\rceil ! (\lfloor \frac{n}{2}\rfloor +\lfloor \frac{n}{2}\rfloor !)$.

Proof

By the construction of $C_{{\mathcal {T}}}$ and Lemma 4, for all $1\le k\le P!$, we have that

$$\begin{aligned} |\sigma _{k\cdot (Q!+Q)}(1)-\sigma _{k\cdot (Q!+Q)}(Q+1)|\ge 2. \end{aligned}$$

(22)

Since $\sigma _{0}(1)=1, \sigma _{0}(Q+1)=2Q$, then $|\sigma _{0}(1)-\sigma _{0}(Q+1)|\ge 2$. Thus, for all $0\le k\le P!-1$, $\sigma _{k\cdot (Q!+Q)}$ satisfies the condition of Lemma 4.

By the construction of $C_{{\mathcal {T}}}$ and Lemma 4, for all $0\le k\le P!-1,~0\le i<j\le Q!+Q-1$, we have that

$$\begin{aligned} d_{\infty }(\sigma _{k(Q!+Q)+i},\sigma _{k(Q!+Q)+j})\ge 2. \end{aligned}$$

Furthermore, for $k,{\tilde{k}}\in [P!]~\text {and}~k<{\tilde{k}}$, since the code generated by its transition sequence ${\mathcal {T}}_P=(t_{\gamma _{P}(1)},t_{\gamma _{P}(2)},\ldots ,t_{\gamma _{P}(P!)})$ is a cyclic and complete P-RMGC code, we are assured that for all $0\le j,{\tilde{j}}\le Q!+Q-1$, the last $P-1$ elements of both $\sigma _{(k-1)(Q!+Q)+j}$ and $\sigma _{({\tilde{k}}-1)(Q!+Q)+{\tilde{j}}}$ are all odd and represent two distinct permutations. Hence, we have that

$$\begin{aligned} d_{\infty }(\sigma _{(k-1)(Q!+Q)+j},\sigma _{({\tilde{k}}-1)(Q!+Q)+{\tilde{j}}})\ge 2. \end{aligned}$$

Finally, we will prove that $\sigma _{P!(Q!+Q)}=\sigma _0$. Since the code generated by the transition sequence ${\mathcal {T}}_P=(t_{\gamma _{P}(1)},t_{\gamma _{P}(2)},\ldots ,t_{\gamma _{P}(P!)})$ is a cyclic and complete P-RMGC code, we have that $\sigma _{P!(Q!+Q)}(1)=1$. By the construction of $\sigma _0$, ${\mathcal {T}}$, and Lemma 4, the number of times of ${\mathcal {T}}_{{\hat{C}}}$ chosen (i.e., $\alpha _2$) over the entire construction is even. Then, we can obtain that $\sigma _{P!(Q!+Q)}=\sigma _0.$

So, $C_{{\mathcal {T}}}$ is an $(n,M,\ell _{\infty })$-snake of size $M=\lceil \frac{n}{2}\rceil ! (\lfloor \frac{n}{2}\rfloor +\lfloor \frac{n}{2}\rfloor !)$. $\square$

Next we present an example to illustrate the construction in Theorem 1.

Example 2

For this example, consider $n=6$ (i.e., $P=Q=3$ ), we need one transition sequence of a cyclic and complete 3-RMGC, i.e., ${\mathcal {T}}_3=(t_3,t_3,t_2,t_3,t_3, t_2 )$. We start our cyclic $(6,54,\ell _{\infty })$-snake described in Fig. 3 with the same permutation $\sigma _0$ in Example 5, and use the two kinds of basic noncyclic $\ell _{\infty }$-snakes presented in Example 5 as building blocks.

In Fig. 3, “$\Downarrow (1)$” stands for an omitted transition sequence ${\mathcal {T}}_{C}=(t_3,t_3,t_4,t_2,t_3,t_3,t_2,t_3)$. While “$\Downarrow (2)$” stands for another omitted transition sequence ${\mathcal {T}}_{{\hat{C}}}=(t_3,t_3,t_4,t_3,t_3,t_2,t_3,t_3).$ When $n=6$, by using one cyclic and complete 3-RMGC, we indeed construct a cyclic $\ell _{\infty }$-snake of size 54.

Fig. 3

A $(6,54,\ell _{\infty })$-snake obtained by using a cyclic and complete 3-RMGC

3.2 Construction of $\ell _{\infty }$-snakes by using ${\mathcal {K}}$-snakes

In this subsection, we will construct $\ell _{\infty }$-snakes by using some snake-in-the-box codes under the Kendall’s $\tau$-metric. In order to present the construction, we need some notations and lemmas of snake-in-the-box codes under the Kendall’s $\tau$-metric.

Given a permutation $\pi =[a_1,\ldots ,a_n]\in S_n$, an adjacent transposition is an exchange of two distinct adjacent elements $a_i, a_{i+1}$, in $\pi$, for some $1\le i\le n-1$. The Kendall’s$\tau$-distance [15] between two permutations $\pi , \sigma \in S_n$, denoted by $d_K(\pi ,\sigma )$, is the minimum number of adjacent transpositions required to obtain the permutation $\sigma$ from $\pi$. A ${\mathcal {K}}$-snake is a Gray code such that $d_{{\mathcal {K}}}(\sigma ,\pi )\ge 2$ for any two distinct permutations $\sigma$ and $\pi$ in the code. Moreover, the Kendall’s $\tau$-metric is right invariant [3], that is, for every three permutations $\sigma ,\pi ,\rho \in S_n$, we have $d_{K}(\sigma ,\pi )=d_{K}(\sigma \circ \rho ,\pi \circ \rho )$. For convenience, we denote by an $(n,M,{\mathcal {K}})$-snake a ${\mathcal {K}}$-snake of size M in $S_n$. In order to establish our results, we need the following results on ${\mathcal {K}}$-snakes.

Lemma 5

[7] For each $n\ge 3$, there exists a $(2n+1,M_{2n+1},{\mathcal {K}})$-snake in $A_{2n+1}$ of size $M_{2n+1}=\frac{(2n+1)!}{2}$ with the transition sequence including $t_{2n+1}$. The largest $(5,M_5,{\mathcal {K}})$-snake has $M_5=57$.

Furthermore, we require the following lemmas for constructing $\ell _{\infty }$-snakes by using ${\mathcal {K}}$-snakes.

Lemma 6

Suppose $\{a_j\}_{j=1}^{n}$, $n\ge 2$, is a set of integers of the same parity. Let $\sigma _{i}=[\sigma _{i}(1),\ldots ,\sigma _{i}(n),\sigma _{i}(n+1),b_{n+2},\ldots ,b_{m}]\in S_m$ for $i=1,2$, where $\sigma _1\ne \sigma _2,$$\{\sigma _{i}(j)\}_{j=1}^{n+1}=\{a_j\}_{j=1}^{n}\cup \{x\}$ for $i=1,2$, and the parity of x differs from that of the elements of $\{a_j\}_{j=1}^{n}$. If $\sigma _1$ and $\sigma _2$ are both odd permutations or even permutations, then $d_{\infty }(\sigma _1,\sigma _2)\ge 2$.

Proof

Since $\sigma _1\ne \sigma _2$, then $d_{\infty }(\sigma _1,\sigma _2)\ge 1$. Suppose $d_{\infty }(\sigma _1,\sigma _2)<2$, we have that $d_{\infty }(\sigma _1,\sigma _2)=1$. We let $\sigma _1=[a_1,a_2,\ldots ,a_i,x,a_{i+1}\ldots ,a_n,b_{n+2},\ldots ,b_m]$, $|a_{j_1}-x|=1$, and $|a_{j_2}-x|=1$, where $j_1,j_2\in [n]$. When $i>j_1$ and $i>j_2$, since $\{a_j\}_{j=1}^{n}$ have the same parity and $d_{\infty }(\sigma _1,\sigma _2)=1$, then $\sigma _2=[a_1,\ldots ,a_{j_1-1},x,a_{j_1+1},\ldots ,a_{i},a_{j_1},a_{i+1},\ldots ,a_{n},b_{n+2},\ldots ,b_m]$ or $\sigma _2=[a_1,\ldots ,a_{j_2-1},x,a_{j_2+1},\ldots ,a_{i},a_{j_2},a_{i+1},\ldots ,a_{n},b_{n+2},\ldots ,b_m]$. Similarly, in all the cases, $\sigma _2$ can be obtained from $\sigma _1$ using one transposition of $a_{j_i}$ and x for $i=1~\text {or}~2$. Then, the parity of $\sigma _1$ differs from the parity of $\sigma _2$, which causes a contradiction. Hence, we have that $d_{\infty }(\sigma _1,\sigma _2)\ge 2$. $\square$

Lemma 7

Suppose $C_n$ is an $(n,M_n,{\mathcal {K}})$-snake in $A_n$ with its first permutation $\pi _0$ and one transition sequence ${\mathcal {T}}_{C_n}=(t_{\alpha (1)},t_{\alpha (2)},\ldots ,t_{\alpha (M_n)})$. For any $\sigma _0\in S_n$, by applying the transition sequence ${\mathcal {T}}_{C_n}$ on the permutation $\sigma _0$, we can obtain another $(n,M_n,{\mathcal {K}})$-snake, denoted by ${\hat{C}}_n=(\sigma _0,\sigma _1,\ldots ,\sigma _{M_n-1})$, where $\sigma _j=t_{\alpha (j)}(\sigma _{j-1})$ for all $j\in [M_n-1]$. Moreover, all the permutations of ${\hat{C}}_n$ have the same parity.

Proof

By [14, Lemma 3], we have that ${\hat{C}}_n$ is an $(n,M_n,{\mathcal {K}})$-snake and $\sigma _i\circ \sigma _0^{-1}=\pi _i\circ \pi _{0}^{-1}$ for all $i\in [M_n-1]\cup \{0\}$. Since the Kendall’s $\tau$-metric is right invariant and $\sigma _i\circ \sigma _0^{-1}=\pi _i\circ \pi _{0}^{-1}$, for any two distinct $i,j\in [M_n-1]\cup \{0\}$, we can obtain that $d_{K}(\sigma _i,\sigma _j)=d_{K}(\pi _i,\pi _j)$. So, when $C_n$ is an $(n,M_n,{\mathcal {K}})$-snake in $A_n$, we have that all the permutations of ${\hat{C}}_n$ have the same parity. $\square$

The following lemma gives the construction of a basic block which is useful for the construction of $\ell _{\infty }$-snakes by using ${\mathcal {K}}$-snakes.

Lemma 8

Let $\{a_{j}\}_{j=1}^{Q}$ be a set of integers of the same parity, and let $\{b_{j}\}_{j=1}^{P}$ be also a set of integers of the same parity such that $\{a_{j}\}_{j=1}^{Q}\cup \{b_{j}\}_{j=1}^{P}=[n]$. We define $\sigma \triangleq [b_1,a_1,a_2,\ldots ,a_Q,b_2,b_3,\ldots ,b_P]$. Suppose we have an $(Q+1,M_{Q+1},{\mathcal {K}})$-snake in $A_{Q+1}$ with one transition sequence ${\mathcal {T}}_{{\mathcal {K}},Q+1}=(t_{\gamma (1)},t_{\gamma (2)}, \ldots ,t_{\gamma (M_{Q+1})})$ such that $t_{\gamma (M_{Q+1})}=t_{Q+1}$, where Q is an even integer. Then, there exists a noncyclic $(n,M_{Q+1},\ell _{\infty })$-snake starting with $\sigma$ and ending with the permutation $\pi =[a_1,a_2,\ldots ,a_Q,b_1,b_2,\ldots ,b_P]$.

Proof

According to Lemma 5, when Q is an even integer, there exists an $(Q+1,M_{Q+1},{\mathcal {K}})$-snake in $A_{Q+1}$ with one transition sequence ${\mathcal {T}}_{{\mathcal {K}},Q+1}$ such that $t_{\gamma (M_{Q+1})}=t_{Q+1}$. We let $C_{\hat{{\mathcal {T}}}_{Q+1}}^{\sigma ,\pi }$ be the claimed noncyclic $\ell _{\infty }$-snake, where $C_{\hat{{\mathcal {T}}}_{Q+1}}^{\sigma ,\pi }=(\sigma _0,\sigma _1,\ldots , \sigma _{M_{Q+1}-1})$ and $\hat{{\mathcal {T}}}_{Q+1}=(t_{\alpha (1)},t_{\alpha (2)},\ldots ,t_{\alpha (M_{Q+1}-1)})$.

First, we denote by $\sigma _0\triangleq \sigma$. Next, we construct the transition sequence $\hat{{\mathcal {T}}}_{Q+1}$. We let

$$\begin{aligned} t_{\alpha (j)}=t_{\gamma (j)}~\text {for all} j\in [M_{Q+1}-1]. \end{aligned}$$

(23)

By (23) and its first permutation $\sigma _0$, we have that

$$\begin{aligned} \sigma _j=[\sigma _j(1),\ldots ,\sigma _{j}(Q+1),b_2,b_3,\ldots ,b_P] \end{aligned}$$

for all $j\in [M_{Q+1}-1]$. By (23) and Lemma 7, due to the $(Q+1,M_{Q+1},{\mathcal {K}})$-snake in $A_{Q+1}$, we have that $C_{\hat{{\mathcal {T}}}_{Q+1}}^{\sigma ,\pi }$ is a noncyclic Gray code, and all the permutations of $C_{\hat{{\mathcal {T}}}_{Q+1}}^{\sigma ,\pi }$ have the same parity. Since $t_{\gamma (M_{Q+1})}=t_{Q+1}$, we have $\pi =\sigma _{M_{Q+1}-1}=[a_1,a_2,\ldots ,a_Q,b_1,b_2,\ldots ,b_P]$.

Finally, for any two distinct permutations $\sigma _{j_1},\sigma _{j_2}\in C_{\hat{{\mathcal {T}}}_{Q+1}}^{\sigma ,\pi }$, since they have the same parity and $\sigma _{j_i}=[\sigma _{j_i}(1),\ldots ,\sigma _{j_i}(Q+1),b_2,b_3,\ldots ,b_P]$, for $i=1~\text {or}~2$, by Lemma 6, we have that

$$\begin{aligned} d_{\infty }(\sigma _{j_1},\sigma _{j_2})\ge 2. \end{aligned}$$

Hence, we can obtain that $C_{\hat{{\mathcal {T}}}_{Q+1}}^{\sigma ,\pi }$ is a noncyclic $(n,M_{Q+1},\ell _{\infty })$-snake starting with $\sigma$ and ending with the permutation $\pi =[a_1,a_2,\ldots ,a_Q,b_1,b_2,\ldots ,b_P]$. $\square$

Next we present an example to illustrate the construction in Lemma 8.

Example 3

Consider $n=7$, we have $P=4$ and $Q=3$. By Lemma 8, we will construct a noncyclic $\ell _{\infty }$-snakes which is a basic building block for $\ell _{\infty }$-snakes. Now, we will start this example with an initial permutation, denoted by $\sigma _0=[2,1,3,5,7,4,6]$. First, Horovitz and Etzion [8] gave a $(5,57,{\mathcal {K}})$-snake in $A_5$ with one transition sequence, denoted by ${\mathcal {T}}_{{\mathcal {K}},5}=(\hat{{\mathcal {T}}},\hat{{\mathcal {T}}},\hat{{\mathcal {T}}})$, where $\hat{{\mathcal {T}}}$ is a partial transition sequence of ${\mathcal {T}}_{{\mathcal {K}},5}$ and $\hat{{\mathcal {T}}}=(t_3,t_3,t_5,t_3,t_3,t_5,t_3,t_5,t_5,t_3,t_3,t_5,t_3,t_3,t_5,t_3,t_5,t_5,t_5)$.

Next, by Lemma 8 and ${\mathcal {T}}_{{\mathcal {K}},5}$, we can construct one transition sequence, denoted by $\hat{{\mathcal {T}}}_{{\mathcal {K}},5}$, where

$$\begin{aligned} \hat{{\mathcal {T}}}_{{\mathcal {K}},5}=(\hat{{\mathcal {T}}}, \hat{{\mathcal {T}}},t_3,t_3,t_5,t_3,t_3,t_5,t_3, t_5,t_5,t_3,t_3,t_5,t_3,t_3,t_5,t_3,t_5,t_5). \end{aligned}$$

We can construct one noncyclic $(7,57,\ell _{\infty })$-snake by the transition sequence $\hat{{\mathcal {T}}}_{{\mathcal {K}},5}$ and ${\hat{\sigma }}_0$ depicted in Fig. 4.

Here, every column in Fig. 4 represents one permutation over $\{1,2,3,4,5,6,7\}$.

Fig. 4

A noncyclic $(7,57,\ell _{\infty })$-snake constructed by $\hat{{\mathcal {T}}}_{{\mathcal {K}},5}$ and ${\hat{\sigma }}_0$

In the following, by Lemma 8, we will give one construction of an $(n,M,\ell _{\infty })$-snake by using some ${\mathcal {K}}$-snakes.

When $n=4k+1$, $k\ge 1$, then [n] has 2k even elements and $2k+1$ odd ones. For convenience, we let $Q=2k$ and $P=2k+1$. First, we denote by $\sigma _0$ an initial permutation, where

$$\begin{aligned} \sigma _0=[1,2,4,\ldots ,2Q-2,2Q,3,5\ldots ,2P-3,2P-1]. \end{aligned}$$

Next, we will construct a transition sequence, denoted by ${\mathcal {T}}_C=(t_{\gamma (1)},t_{\gamma (2)},\ldots ,t_{\gamma (M)})$. By the transition sequence ${\mathcal {T}}_C$ and the initial permutation $\sigma _0$, we can obtain a permutation sequence, denoted by $C_{{\mathcal {T}}_C}^{\sigma _0}=(\sigma _0,\sigma _1,\ldots ,\sigma _{M-1})$. Given a $(P,M_{P},{\mathcal {K}})$-snake in $A_{P}$ with one transition sequence $(t_{\alpha (1)},t_{\alpha (2)},\ldots ,t_{\alpha (M_{P})})$ and $t_{\alpha (M_{P})}=t_{2k+1}$, by Lemma 8, we take a noncyclic $(n,M_{P},\ell _{\infty })$-snake by using the following transition sequence

$$\begin{aligned} \hat{{\mathcal {T}}}_{P}=(t_{\alpha (1)},t_{\alpha (2)},\ldots ,t_{\alpha (M_{P}-1)}). \end{aligned}$$

(24)

By Lemma 1, we can obtain a cyclic and complete P-RMGC by using the following transition sequence

$$\begin{aligned} {\mathcal {T}}_{P}=(t_{\gamma _{P}(1)},t_{\gamma _{P}(2)},\ldots ,t_{\gamma _{P}(P!)}). \end{aligned}$$

(25)

By (24)–(25), we construct the transition sequence ${\mathcal {T}}_C=(t_{\gamma (1)},t_{\gamma (2)},\ldots ,t_{\gamma (M)})$ such that $M=M_{P}\cdot P!$ as follows.

For all $1\le i\le P!$ and $1\le j\le M_{P}-1$, we let

$$\begin{aligned}&t_{\gamma ((i-1)\cdot M_P+j)}=t_{{\alpha }(j)}, \end{aligned}$$

(26)

$$\begin{aligned}&t_{\gamma (i\cdot M_P)}=t_{\gamma _{P}(i)+Q}. \end{aligned}$$

(27)

By (26)–(27) and the initial permutation $\sigma _0$, we obtain the permutation sequence $\sigma _j=t_{\gamma (j)}(\sigma _{j-1})$ for all $1\le j\le M_{P}(P)!-1$.

Similarly, when $n=4k+3 ~\text {or}~ 4k+4, ~\text {and}~ k\ge 1$, then [n] has Q even elements and P odd ones. Hence, when $n=4k+3 ~\text {or}~4k+4$, we always have $P=2k+2$. Then, according to Lemma 5, there exists a $(P+1,M_{P+1},{\mathcal {K}})$-snake in $A_{P+1}$ with one transition sequence $(t_{\alpha _1(1)},t_{\alpha _1(2)},\ldots ,t_{\alpha _1(M_{P+1})})$ and $t_{\alpha _1(M_{P+1})}=t_{P+1}$. We will give another construction of an $(n,{\hat{M}},\ell _{\infty })$-snake by using some ${\mathcal {K}}$-snakes. First, we denote by ${\hat{\sigma }}_0$ an initial permutation, where

$$\begin{aligned} {\hat{\sigma }}_0=[2,1,3,5,\ldots ,2P-3,2P-1,4,6\ldots ,2Q-2,2Q]. \end{aligned}$$

(28)

Next, we construct another transition sequence, denoted by ${\mathcal {T}}_{{\hat{C}}}=(t_{\beta (1)},t_{\beta (2)},\ldots ,t_{\beta ({\hat{M}})})$. By the transition sequence ${\mathcal {T}}_{{\hat{C}}}$ and the initial permutation ${\hat{\sigma }}_0$, we can get a permutation sequence, denoted by ${\hat{C}}_{{\mathcal {T}}_{{\hat{C}}}}^{{\hat{\sigma }}_0}=({\hat{\sigma }}_0,{\hat{\sigma }}_1,\ldots ,{\hat{\sigma }}_{{\hat{M}}-1})$.

Given a $(P+1,M_{P+1},{\mathcal {K}})$-snake in $A_{P+1}$ with one transition sequence $(t_{\alpha _1(1)},t_{\alpha _1(2)},\ldots ,t_{\alpha _1(M_{P+1})})$ and $t_{\alpha _1(M_{P+1})}=t_{P+1}$, by Lemma 8, we take a noncyclic $(n,M_{P+1},\ell _{\infty })$-snake by using the following transition sequence

$$\begin{aligned} \hat{{\mathcal {T}}}_{P+1}=(t_{\alpha _1(1)},t_{\alpha _1(2)},\ldots , t_{\alpha _1(M_{P+1}-1)}). \end{aligned}$$

(29)

By Lemma 1, we can obtain a cyclic and complete Q-RMGC by using the following transition sequence

$$\begin{aligned} {\mathcal {T}}_{Q}=(t_{\gamma _{Q}(1)},t_{\gamma _{Q}(2)},\ldots ,t_{\gamma _{Q}(Q!)}). \end{aligned}$$

(30)

By (29)–(30), we construct the transition sequence ${\mathcal {T}}_{{\hat{C}}}=(t_{\beta (1)},t_{\beta (2)},\ldots ,t_{\beta ({\hat{M}})})$ such that ${\hat{M}}=M_{P+1}\cdot Q!$ as follows.

For all $1\le i\le Q!$ and $1\le j\le M_{P+1}-1$, we let

$$\begin{aligned}&t_{\beta ((i-1)\cdot M_{P+1}+j)}=t_{{\alpha }(j)}, \end{aligned}$$

(31)

$$\begin{aligned}&t_{\beta (i\cdot M_{P+1})}=t_{\gamma _{Q}(i)+P}. \end{aligned}$$

(32)

By (31)–(32) and its first permutation ${\hat{\sigma }}_0$, we obtain the permutation sequence ${\hat{\sigma }}_j=t_{\beta (j)}({\hat{\sigma }}_{j-1})$ for all $1\le j\le M_{P+1}\cdot Q!-1$.

Finally, in the following theorem, we will prove that ${\hat{C}}_{{\mathcal {T}}_{{\hat{C}}}}^{{\hat{\sigma }}_0}$ and $C_{{\mathcal {T}}_C}^{\sigma _0}$ are $\ell _{\infty }$-snakes.

Theorem 2

When $n=4k+1$ and $k\ge 1$, given a $(2k+1,M_{2k+1},{\mathcal {K}})$-snake in $A_{2k+1}$, there exists an $(n,M,\ell _{\infty })$-snake of size $M=M_{2k+1}\cdot (2k+1)!$. When $n=4k+3~\text {or}~4k+4$, and $k\ge 1$, given a $(2k+3,M_{2k+3},{\mathcal {K}})$-snake in $A_{2k+3}$, there exists an $(n,{\hat{M}},\ell _{\infty })$-snake of size ${\hat{M}}=M_{2k+3}\cdot \lfloor \frac{n}{2}\rfloor !$.

Proof

When $n=4k+1$, then $Q=2k$ and $P=2k+1$. According to Lemma 5, there exists a $(2k+1,M_{2k+1},{\mathcal {K}})$-snake in $A_{2k+1}$ and a $(2k+3,M_{2k+3},{\mathcal {K}})$-snake in $A_{2k+3}$. We will prove that the above $C_{{\mathcal {T}}_C}^{\sigma _0}$ is an $\ell _{\infty }$-snake. Since $\sigma _0=[1,2,4,\ldots ,2Q,3,5,\ldots ,2P-1]$, by the construction of this $\ell _{\infty }$-snake, we have that for all $0\le i\le P!-1$, $\sigma _{i\cdot M_{P}}$ satisfies the condition of Lemma 8. Then, by the construction of $C_{{\mathcal {T}}_C}^{\sigma _0}$ and Lemma 8, for all $0\le i\le P!-1~\text {and}~0\le j_1<j_2\le M_{P}-1$, we have

$$\begin{aligned} d_{\infty }(\sigma _{i\cdot M_{P}+j_1},\sigma _{i\cdot M_{P}+j_2})\ge 2. \end{aligned}$$

Furthermore, for $l,{\tilde{l}}\in [P!]~\text {and}~l<{\tilde{l}}$, since the code generated by the transition sequence ${\mathcal {T}}_{P}=(t_{\gamma _{P}(1)},t_{\gamma _{P}(2)},\ldots , t_{\gamma _{P}(P!)})$ is a cyclic and complete P-RMGC code, we are assured that for all $0\le j,{\tilde{j}}\le M_{P}-1$, the last 2k elements of both $\sigma _{(l-1)M_{P}+j}$ and $\sigma _{({\tilde{l}}-1)M_{P}+{\tilde{j}}}$ are all odd and represent two distinct permutations. Then, we have that

$$\begin{aligned} d_{\infty }(\sigma _{(l-1)M_{P}+j},\sigma _{({\tilde{l}}-1)M_{P}+{\tilde{j}}})\ge 2. \end{aligned}$$

Finally, we note that $t_{\gamma (M_{P}\cdot P!)}(\sigma _{M_{P}\cdot P!-1})=\sigma _0$, since the code generated by the transition sequence ${\mathcal {T}}_{P}$ is cyclic. Hence, $C_{{\mathcal {T}}_C}^{\sigma _0}$ is an $(n,M,\ell _{\infty })$-snake of size $M=M_{P}\cdot P!=M_{2k+1}\cdot (2k+1)!$.

Similarly, when $n=4k+3~\text {or}~4k+4$, by the construction of ${\hat{C}}_{{\mathcal {T}}_{{\hat{C}}}}^{{\hat{\sigma }}_0}$, we can obtain that ${\hat{C}}_{{\mathcal {T}}_{{\hat{C}}}}^{{\hat{\sigma }}_0}$ is an $(n,{\hat{M}},\ell _{\infty })$-snake of size ${\hat{M}}=M_{2k+3}\cdot \lfloor \frac{n}{2}\rfloor !$. $\square$

Fig. 5

A $(7,342,\ell _{\infty })$-snake constructed by using a ${\mathcal {K}}$-snake in $A_5$

Corollary 1

When $n=4k+1$ and $k\ge 3$, there exists an $(n,M,\ell _{\infty })$-snake of size $M=\frac{((2k+1)!)^2}{2}$. When $n=4k+3~\text {or}~4k+4$, and $k\ge 1$, there also exists an $(n,{\hat{M}},\ell _{\infty })$-snake of size ${\hat{M}}=\frac{(2k+3)!\cdot \lfloor \frac{n}{2}\rfloor !}{2}$. Moreover, there exists a $(9,6840,\ell _{\infty })$-snake and a $(7,342,\ell _{\infty })$-snake.

Proof

By Theorem 2 and Lemma 5, we can prove this corollary. $\square$

Next we present an example to illustrate the construction in Theorem 2 and Corollary 1.

Example 4

For this example, consider $n=7$ (i.e., $P=4,Q=3$ ), we need one transition sequence of a cyclic and complete 3-RMGC, i.e, ${\mathcal {T}}_3=(t_2,t_3,t_3,t_2,t_3,t_3)$. We start our cyclic $(7,342,\ell _{\infty })$-snake described in Fig. 5 with the same permutation $\sigma _0$ in Example 12, and use the basic noncyclic $\ell _{\infty }$-snakes presented in Example 12 as a building block.

In Fig. 5, “$\Downarrow$” stands for an omitted transition sequence ${\hat{{\mathcal {T}}}}_{{\mathcal {K}},5}$ denoted in Example 12. When $n=7$, by using ${\mathcal {K}}$-snakes in $A_5$, we can obtain a cyclic $(7,342,\ell _{\infty })$-snake.

4 Comparison

In this section, we compare our results with those of others. Yehezkeally and Schwartz [15] presented one construction of an $(n,M_{n,0},\ell _{\infty })$-snake of size

$$\begin{aligned} M_{n,0}=\lceil \frac{n}{2}\rceil !\left( \lfloor \frac{n}{2}\rfloor +\left( \lfloor \frac{n}{2}\rfloor -1\right) !\right) ~\text {for all }n\ge 4. \end{aligned}$$

(33)

Based on their construction of $\ell _{\infty }$-snakes, we proposed one construction of $\ell _{\infty }$-snakes by using cyclic and complete RMGCs. In this construction, we could obtain an $(n,M_{n,1},\ell _{\infty })$-snake of size

$$\begin{aligned} M_{n,1}=\lceil \frac{n}{2}\rceil !\left( \lfloor \frac{n}{2}\rfloor +\left( \lfloor \frac{n}{2}\rfloor \right) !\right) ~\text { for all }~n\ge 6. \end{aligned}$$

(34)

Hence, these $\ell _{\infty }$-snakes are better than Yehezkeally and Schwartz’s ones for all $n\ge 6$.

We also gave another construction of $\ell _{\infty }$-snakes by using ${\mathcal {K}}$-snakes. By Corollary 1, we can obtain an $(n,M_{n,2},\ell _{\infty })$-snake, where

$$\begin{aligned} M_{n,2}= {\left\{ \begin{array}{ll} \frac{((2k+1)!)^2}{2}~~ \text {if n=4k+1},\\ \frac{(2k+3)!\cdot \lfloor \frac{n}{2}\rfloor !}{2} ~~ \text {if }n=4k+3~\text {or}~4k+4, \end{array}\right. } \end{aligned}$$

(35)

for all $k\ge 2$.

By (34)–(35) and Corollary 1, when $n=4k+1,4k+3,~\text {or}~4k+4$, and $k\ge 2$, we have that $M_{n,2}> M_{n,1}$. Thus, we can obtain that

$$\begin{aligned} M_{n,2}> M_{n,1}>M_{n,0} \end{aligned}$$

(36)

for all $n=4k+1, 4k+3~\text {or}~4k+4$, and $k\ge 2$. Hence, by (36), the second construction is superior to the first one and Yehezkeally and Schwartz’s one in some cases. Moreover, when $n=4k+1, 4k+3~\text {or}~4k+4$, and $k\ge 2$, the second construction improves the size of the $(n,M_{n,0},\ell _{\infty })$-snake by a factor of $O(n^2)$. We note that a similar improvement was made in [16]. Specifically, Yehezkeally and Schwartz [16] constructed an $(n,M_{n,3},\ell _{\infty })$-snake, where

$$\begin{aligned} M_{n,3}= {\left\{ \begin{array}{ll} \frac{2k!\cdot (2k+2)!}{2}~~ \text {if }n=4k+1,\\ \frac{(2k+1)!\cdot (2k+2)!}{2}\cdot \rho _{2k+2}~~ \text {if }n=4k+2,\\ \frac{(2k+1)!\cdot (2k+3)!}{2}~~ \text {if }n=4k+3,\\ \frac{(2k+2)!\cdot (2k+3)!}{2} ~~ \text {if }n=4k+4, \end{array}\right. } \end{aligned}$$

and $\rho _{2k+2}>\frac{2k-1}{2k+3}$, for all $k\ge 3$. Moreover, in the case of $n \equiv 1~ (\text {mod}~ 4)$, the factor $\rho _{2k+2}$ is eliminated. Hence, when $n=4k+1,4k+2,4k+3~\text {or}~4k+4$, and $k\ge 3$, the results in [16] also improve the size of the $(n,M_{n,0},\ell _{\infty })$-snake by a factor of $O(n^2)$.

Finally, we also compare our results (i.e., $M_{n,1}$ and $M_{n,2}$) to error-correcting codes with the $\ell _{\infty }$-metric which are not necessarily Gray codes (LMRM-codes) in [11] and [13]. The authors in [11] and [13] presented $(n,M,\ell _{\infty })$-LMRM codes with sizes

$$\begin{aligned} M=\left( \lceil \frac{n}{2}\rceil !\right) ^{n~\text {mod}~ 2}\left( \lfloor \frac{n}{2}\rfloor !\right) ^{2-(n~\text {mod}~ 2)}. \end{aligned}$$

(37)

When $n=4k+1, 4k+3~\text {or}~4k+4$, and $k\ge 2$, the second construction (i.e., $M_{n,2}$) improves the size of the $(n,M,\ell _{\infty })$-LMRM codes by a factor of O(n / 4). When $n=4k+2$, $M_{n,1}=(2k+1)!\big ((2k+1)!+2k+1\big )$ and $M=((2k+1)!)^2$. Hence, when $n=4k+2$, $M_{n,1}=O(M)$, but $M_{n,1}$ is strictly larger than M.

5 Conclusions

Gray codes in $S_n$ under the $\ell _{\infty }$-metric are very useful in the framework of rank modulation for flash memories. In this paper, we gave two constructions of $\ell _{\infty }$-snakes which improve on Yehezkeally and Schwartz’s construction. On the one hand, we presented one construction of $\ell _{\infty }$-snakes by using cyclic and complete RMGCs. On the other hand, we gave another construction of $\ell _{\infty }$-snakes by using ${\mathcal {K}}$-snakes. By our constructions, we can obtain longer $\ell _{\infty }$-snakes than Yehezkeally and Schwartz’s ones.