On the snake-in-the-box codes for rank modulation under Kendall’s $\tau$-metric

Abstract

For exactly and efficiently representing and storing data in flash memories, the rank modulation scheme has been presented. In this scheme, Gray codes over the permutations are important, which are used to represent information in flash memories. For a Gray code, two consecutive codewords are obtained using one “push-to-the-top” operation. Specially, a snake-in-the-box code under the Kendall’s $\tau$-metric is a Gray code, which is capable of detecting one Kendall’s $\tau$-error. In this paper, we consider only the Kendall’s $\tau$-metric on the permutations. And we answer one open problem proposed by Horovitz and Etzion. That is, we prove that the length of the longest snake in $S_{2n+2}$ is longer than the length of the longest snake in $S_{2n+1}$.

1 Introduction

Flash memory is a kind of non-volatile storage medium that is both electrically programmable and electrically erasable. Its reliability, high storage density, and relatively low cost have made it widely used. And it has a set of cells maintained at a set of charge levels to encode messages. The most conspicuous property of flash memories is its inherent asymmetry between cell programming (injecting cells with charge) and cell erasure (removing charge from cells). While injecting a singe cell with charge is an easy operation, removing the charge from a single cell is a very difficult operation. In fact, in the current architecture of flash memories, a single-cell erasure operation requires copying a large whole block to a temporary location, erasing it, and then reprogramming the whole cells in the block. When some cells may be injected with extra charge in the programming operation, this will result in overshooting. Thus, the overshooting (increasing a cell’s charge level above the desired amount) is a severe problem. For this reason, in a programming cycle, charge is injected over several iterations, gradually approaching the desirable level. This process is time-consuming. Moreover, there are other common errors in flash memory cells because of charge leakage or reading disturbance.

In order to overcome these problems, the rank modulation scheme has been recently proposed in [10]. In this scheme, one permutation suggested by the relative rankings of the charge levels on a group of cells represents data instead of using absolute values of charge levels. Thus, in this model codes are subsets of all the permutations on n elements, denoted by $S_n$, which will represent information in flash memories. To avoid the overshooting, the programming operation is restricted to the “push-to-the-top” operation [10]. In this framework, a group of cells are programmed by raising the charge level of a single cell above those of all others (“push-to-the-top” operations). Hence, in this encoding scheme, the overshooting is no longer an issue. When errors caused by injection of extra charge or leakage are very small, they may not affect the relative rankings, i.e., the permutation will not be changed. However, it may happen that errors in the cells are large enough to change the relative rankings. To detect and/or correct such errors we need an appropriate distance measure in the permutations. There are several metrics on the permutations such as the $\ell _{\infty }$-metric [12, 15], the Ulam metric [5] and the Kendall’s $\tau$-metric [2, 11]. In this paper, we will consider only the Kendall’s $\tau$-metric.

Gray codes using only “push-to-the-top” operations have been presented in [10]. Moreover, the Gray code was firstly proposed in [8] as a sequence of distinct binary vectors of fixed length, where every adjacent pair differs in a single coordinate. In practice, they are useful in many applications [13]. In order to understand the Gray codes, an excellent survey on the Gray codes is given in [14]. In the flash memory, Gray codes for the rank modulation scheme have been discussed in [6, 7, 10, 11, 16]. In fact, a Gray code is a simple cycle in a graph, in which the edges are defined between vertices with distance one in a given metric. Moreover, a snake-in-the-box code is a Gray code in which the distance of any two distinct elements in the code is at least 2. Hence, this code can detect a single error in a codeword. In general, the snake-in-the-box codes are usually considered in the context of binary codes in the Hamming scheme, e.g., [1]. When we consider the Kendall’s $\tau$-metric, a snake-in-the-box code for rank modulation under the Kendall’s $\tau$-metric is a Gray code in which the Kendall’s $\tau$-distance between any two distinct permutations is at least 2.

In [16], Yehezkeally and Schwartz constructed a snake-in-the-box code of length $M_{2n+1}=(2n+1)(2n-1)M_{2n-1}$ for permutations of $S_{2n+1}$, from a snake of length $M_{2n-1}$ for permutations of $S_{2n-1}$. Later Horovitz and Etzion [9] improved on this result by constructing a snake of length $M_{2n+1}=((2n+1)2n-1)M_{2n-1}$ for permutations of $S_{2n+1}$, from a snake of length $M_{2n-1}$ for permutations of $S_{2n-1}$. They also presented a direct construction aiming at obtaining a snake in $S_{2n+1}$ of size $\frac{(2n+1)!}{2}-2n+1$. These researches on this topic restrict the “push-to-the-top” operations only on odd indices, so a snake with this restriction in $S_{2n+2}$ is equivalent to a snake in $S_{2n+1}$. Thus Horovitz and Etzion [9] proposed the open problem to prove or disprove that the length of the longest snake in $S_{2n+2}$ is not longer than the length of the longest snake in $S_{2n+1}$. Recently, Zhang and Ge [17] gave a rigorous proof for the Horovitz-Etzion construction of a snake in $S_{2n+1}$ of size $\frac{(2n+1)!}{2}-2n+1$. In this paper, we prove that the length of the longest snake in $S_{2n+2}$ is longer than the length of the longest snake in $S_{2n+1}$. Moreover, we also give a construction of a snake in $S_{2n+2}$ of size $M_{2n+1}+1$ from a snake in $S_{2n+1}$ of size $M_{2n+1}$. Therefore, we answer the problem proposed by Horovitz and Etzion.

The rest of this paper is organized as follows. In Sect. 2 we define the basic concepts of the Gray codes in the rank modulation scheme, such as the Kendall’s $\tau$-metric, the “push-to-the-top” operation and some useful notations required in this paper. In Sect. 3 we review some properties of the Kendall’s $\tau$-metric, and present some properties of ${\mathcal {K}}$-snakes. In Sect. 4 we propose a construction of a snake in $S_{2n+2}$ from a snake in $S_{2n+1}$. In Sect. 5 we give a rigorous proof of the problem posed by Horovitz and Etzion. In Sect. 6 we present two examples of a snake in $S_{2n+2}$ from one of the longest snakes in $S_{2n+1}$. Section 7 concludes this paper.

2 Preliminaries

In this section we will use some notations and definitions mentioned in [3, 9], and we also give some new notations.

Let [n] be the set $\{1,2,\ldots ,n\}$, and let $\pi =[\pi (1),\pi (2),\ldots ,\pi (n)]$ be a permutation over [n]. Denote $S_n$ the set of all the permutations over [n]. For $\sigma ,\pi \in S_n$, their multiplication $\pi \circ \sigma$ is defined as 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 $\epsilon _{n}\triangleq [1,2,\ldots ,n]$, i.e., $\epsilon _{n}$ is the identity permutation of $S_n$. And let $\pi ^{-1}$ be the inverse element of $\pi \in S_n$. Moreover, we define an inversion as a pair $(\pi (i),\pi (j))$ such that $\pi (i)>\pi (j)$ and $i<j$, where $\pi \in S_n$.

Given a set ${\mathcal {S}}$ and a subset of transformations $T\subset \{f|f:{\mathcal {S}}\rightarrow {\mathcal {S}}\}$, a Gray code over ${\mathcal {S}}$ of size M, using transformations from T, is a sequence $C=(c_0,c_1,\ldots ,c_{M-1})$ of M distinct elements from ${\mathcal {S}}$, called codewords. In this sequence, for each $i\in [M-1]$ there exists one $\tilde{t}_i\in T$ such that $c_i=\tilde{t}_i(c_{i-1})$. We define a transformation sequence of the Gray code C by ${\mathcal {T}}_C$, where ${\mathcal {T}}_C=(\tilde{t}_1,\tilde{t}_2,\ldots ,\tilde{t}_{M-1})$. Moreover, the Gray code is called cyclic if there exists $\tilde{t}_{M}\in T$ such that $c_0=\tilde{t}_{M}(c_{M-1})$. Then the transformation sequence ${\mathcal {T}}_C$ of the cyclic Gray code C is $(\tilde{t}_1,\tilde{t}_2,\ldots ,\tilde{t}_{M-1},\tilde{t}_{M})$.

In the rank modulation scheme for flash memories, ${\mathcal {S}}=S_n$ and the set of transformations $T_n$ consists of the “push-to-the-top” operations in $S_n$. Next, We define $t_i:S_n\rightarrow S_n$ by 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}$$

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

A sequence of p-transitions will be called a transition sequence. Then, an initial permutation $\pi _0$ in $S_n$ and a transition sequence $t_{x_1},t_{x_2},\ldots ,t_{x_l}$ can determine a sequence of permutations $\pi _0,\pi _1,\ldots ,\pi _l$ in $S_n$, where $\pi _i=t_{x_i}(\pi _{i-1}),t_{x_i}\in T_n$, for all $i\in [l]$. If $\pi _l=\pi _0$ and for each $0\le i<j<l$, $\pi _i\ne \pi _j$, then the sequence is a cyclic Gray code using the “push-to-the-top” operations, denoted by $C_n$. Thus, the transition sequence ${\mathcal {T}}_{C_n}$ of the Gray code $C_n$ is $(t_{x_1},t_{x_2},\ldots ,t_{x_l})$.

Given a permutation $\pi =[\pi (1),\pi (2),\ldots ,\pi (n)]\in S_n$, an adjacent transposition is an exchange of two distinct adjacent elements $\pi (i),\pi (i+1)$ in $\pi$, for every $1\le i\le n-1$. Then, we obtain the transformed permutation $[\pi (1),\pi (2),\ldots ,\pi (i-1),\pi (i+1),\pi (i),\pi (i+2),\ldots ,\pi (n)]$. The Kendall’s $\tau$-distance between two permutations $\pi ,\sigma \in S_n$ , denoted by $d_{K}(\pi ,\sigma )$, is the minimal number of adjacent transpositions required to obtain the permutation $\sigma$ from the permutation $\pi$. Therefore, a snake-in-the-box code under the Kendall’s metric is a cyclic Gray code C in which for each two distinct permutations $\pi ,\sigma \in C$, we have $d_{K}(\pi ,\sigma )\ge 2$. Consequently, a snake-in-the-box code C can detect one Kendall’s error. We will call the snake-in-the-box code a ${\mathcal {K}}$-snake or a snake.

For convenience, we denote by an $(n,M,{\mathcal {K}})$-snake a ${\mathcal {K}}$-snake in $S_n$ of size M. We let $C_{{\mathcal {T}}_{C}}^{\pi _0}$ be an $(n,M,{\mathcal {K}})$-snake, where ${\mathcal {T}}_C$ is its transition sequence, and $\pi _0$ is its first permutation. For simplicity, we let $C_{{\mathcal {T}}_{C}}^{\pi _0}\triangleq (\pi _0,\pi _1,\pi _2,\ldots ,\pi _{M-1})$ and ${\mathcal {T}}_{C}\triangleq (t_{x_1},t_{x_2},\ldots ,t_{x_M})$ such that $\pi _i=t_{x_i}(\pi _{i-1})$ for all $i\in [M-1]$ and $t_{x_M}(\pi _{M-1})=\pi _0$. And we denote by $|C_{{\mathcal {T}}_{C}}^{\pi _0}|$ the number of permutations in this permutation sequence, i.e., $|C_{{\mathcal {T}}_{C}}^{\pi _0}|=M$. For a transition sequence $s=(t_{k_1},t_{k_2},\ldots ,t_{k_l})$ and a permutation $\pi \in S_n$, we denote by $s(\pi )$ one permutation obtained by applying the sequence of p-transitions s on $\pi$, that is, $t_{k_1}$ is applied on $\pi$, $t_{k_2}$ is applied on $t_{k_1}(\pi )$, and so on. Then we have $s(\pi )=t_{k_l}\big (t_{k_{l-1}}(\cdot \cdot \cdot (t_2(t_1(\pi )))\cdot \cdot \cdot )\big )$.

Yehezkeally and Schwartz [16] proved that if C is an $(n,M,{\mathcal {K}})$-snake, then $M\le \frac{n!}{2}$. In particular, when $n=3$, they constructed the longest $(3,3,{\mathcal {K}})$-snake. Moreover, when $n=5$, Horovitz and Etzion [9] obtained the longest $(5,57,{\mathcal {K}})$-snake. These two results will be ready for constructing some examples.

Based on the above definitions and notations, we will prove that the length of the longest ${\mathcal {K}}$-snake in $S_{2n+2}$ is longer than the length of the longest ${\mathcal {K}}$-snake in $S_{2n+1}$, for all $n\ge 1$. For convenience, we let $Z_n$ be the length of the longest ${\mathcal {K}}$-snake in $S_n$. Hence, we just need to prove that $Z_{2n+2}>Z_{2n+1}$, for all $n\ge 1$.

3 Kendall’s $\tau$-metric and ${\mathcal {K}}$-snake

In this section, we will give some properties of the Kendall’s $\tau$-metric and the ${\mathcal {K}}$-snake. And we will also present some lemmas, which will be used for proving the main result.

According to the definition of the Kendall’s $\tau$-distance, for any two permutations $\sigma ,\pi \in S_n$, we have the following expression for $d_{K}(\sigma ,\pi )$ [11],

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

(1)

Moreover, the Kendall’s $\tau$-metric is right invariant [4], 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 )$. Due to (1), we can obtain the following lemma.

Lemma 1

For any two permutations $\sigma ,\pi \in S_n$, suppose $\sigma (l)=n,\pi (k)=n$, and let $\sigma _1=[\sigma (1),\sigma (2),\ldots \sigma (l-1),\sigma (l+1),\ldots ,\sigma (n)],\pi _1=[\pi (1),\pi (2),\ldots ,\pi (k-1), \pi (k+1),\ldots ,\pi (n)]$, then we have that $\sigma _1,\pi _1\in S_{n-1}$ and $d_{K}(\sigma _1,\pi _1)\le d_{K}(\sigma ,\pi )$.

Proof

According to the definition of $\sigma _1,\pi _1$, then $\sigma _1,\pi _1\in S_{n-1}$. Due to (1), we obtain that

$$\begin{aligned} d_{K}(\sigma ,\pi )=&|\{(i,j):\sigma ^{-1}(i)<\sigma ^{-1}(j)\wedge \pi ^{-1}(i)>\pi ^{-1}(j)\}|\\ =&|\{(i,j):\sigma ^{-1}(i)<\sigma ^{-1}(j)\wedge \pi ^{-1}(i)>\pi ^{-1}(j),\quad 1\le i, \quad j\le n-1\}|\\&+|\{(i,j):\sigma ^{-1}(i)<\sigma ^{-1}(j)\wedge \pi ^{-1}(i)>\pi ^{-1}(j),\quad \text {i=n \quad or \quad j=n}\}|\\ \end{aligned}$$

and

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

Hence, we have $d_{K}(\sigma _1,\pi _1)\le d_{K}(\sigma ,\pi )$. $\square$

A ${\mathcal {K}}$-snake is obtained by applying its transition sequence on its first permutation. Suppose $C_{{\mathcal {T}}_C}^{\pi _0}$ is an $(n,M,{\mathcal {K}})$-snake with its first permutation $\pi _0$, where ${\mathcal {T}}_{C}=(t_{x_1},t_{x_2},\ldots ,t_{x_M})$. If we change its first permutation with the identity permutation $\epsilon _n$, we can get a permutation sequence ${\hat{C}}$ by applying ${\mathcal {T}}_C$ on $\epsilon _n$. Then ${\hat{C}}$ is an $(n,M,{\mathcal {K}})$-snake, denoted by $C_{{\mathcal {T}}_C}^{\epsilon _n}$ as stated in the next two lemmas.

Lemma 2

For any $t_i\in T_n$ and $\pi ,\sigma \in S_n$,we have $t_i(\pi )\circ \sigma =t_i(\pi \circ \sigma )$. Moreover, for a transition sequence $s=(t_{x_1},t_{x_2},\ldots ,t_{x_l})$ for all the $t_{x_i}\in T_n, i\in [l]$, we also have $s(\pi )\circ \sigma =s(\pi \circ \sigma )$.

Proof

Note in [9] that $t_i(\pi )\circ \sigma =t_i(\pi \circ \sigma )$. According to the definition of $s(\pi )$ and $t_i(\pi )\circ \sigma =t_i(\pi \circ \sigma )$, we have that $s(\pi )\circ \sigma =s(\pi \circ \sigma )$. $\square$

Lemma 3

Suppose $C_{{\mathcal {T}}_C}^{\pi _0}$ and ${\hat{C}}$ are defined as above, then ${\hat{C}}$ is an $(n,M,{\mathcal {K}})$-snake, denoted by $C_{{\mathcal {T}}_C}^{\epsilon _n}$. Moreover, if $C_{{\mathcal {T}}_C}^{\pi _0}$ is one of the longest snakes in $S_n$ of size $Z_n$, then $C_{{\mathcal {T}}_C}^{\epsilon _n}$ is also one of the longest snakes in $S_n$ of size $Z_n$.

Proof

For convenience, we let $C_{{\mathcal {T}}_C}^{\pi _0}=(\pi _0,\pi _1,\ldots ,\pi _{M-1})$ and ${\hat{C}}=({\hat{\pi }}_0,{\hat{\pi }}_1,\ldots ,{\hat{\pi }}_{M-1})$. By Lemma 2, we have that $\pi _i={\hat{\pi }}_i\circ \pi _0$ for all $0\le i\le M-1$. Since the Kendall’s $\tau$-metric is right invariant [4] and $C_{{\mathcal {T}}_C}^{\pi _0}$ is a snake, then ${\hat{C}}$ is an $(n,M,{\mathcal {K}})$-snake. Consequently, if $C_{{\mathcal {T}}_C}^{\pi _0}$ is one of the longest snakes in $S_n$ of size $Z_n$, then $C_{{\mathcal {T}}_C}^{\epsilon _n}$ is also one of the longest snakes in $S_n$ of size $Z_n$. $\square$

Since $S_n$ is a finite set of size n! and $T_n$ is also a finite set of size $n-1$, then the set of all ${\mathcal {K}}$-snakes in $S_n$ is a finite set. Hence, there must be some of the longest ${\mathcal {K}}$-snakes. By Lemma 3, there must be a ${\mathcal {K}}$-snake in which its first permutation is the identity permutation $\epsilon _n$. Consider one of the longest ${\mathcal {K}}$-snakes in $S_{2n+1}$ with its first permutation $\epsilon _{2n+1}$, denoted by $C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}$. Then its transition sequence ${\mathcal {T}}_C$ must contain one p-transition $t_{2n+1}$ as stated in the next theorem.

Theorem 1

Suppose $C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}$ is one of the longest snakes in $S_{2n+1}$ of size $Z_{2n+1}$, then its transition sequence ${\mathcal {T}}_C$ must contain one p-transition $t_{2n+1}$, for all $n\ge 1$.

To prove Theorem 1, we need the following lemma.

Lemma 4

For all $n\ge 1$, $Z_{2n+1}>Z_{2n}$.

Proof

Firstly, consider that when $n=1$, we will obtain that $Z_{2n+1}>Z_{2n}$. When $n=1$, we have that $Z_3=3$ and $Z_2=0$, then $Z_3>Z_2$.

Since Zhang and Ge [17] gave a rigorous proof for Horovitz-Etzion construction of a snake in $S_{2n+1}$ of size $\frac{(2n+1)!}{2}-2n+1$ for all $n\ge 2$, we have that $Z_{2n+1}\ge \frac{(2n+1)!}{2}-2n+1$ for all $n\ge 2$. On the other hand, Yehezkeally and Schwartz [16] showed that $Z_{2n}\le \frac{(2n)!}{2}$ for all $n\ge 2$. Therefore, $Z_{2n+1}\ge \frac{(2n+1)!}{2}-2n+1>\frac{(2n)!}{2}\ge Z_{2n}$ for all $n\ge 2$. So, we have that $Z_{2n+1}>Z_{2n}$ for all $n\ge 1$. $\square$

Next, we will prove Theorem 1 by using Lemma 4.

Proof

Suppose the transition sequence ${\mathcal {T}}_C$ has no transition $t_{2n+1}$, and we let $C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}\triangleq (\pi _0,\pi _1,\ldots ,\pi _{Z_{2n+1}-1})$ and ${\mathcal {T}}_C\triangleq (t_{x_{1}},\ldots ,t_{x_{Z_{2n+1}}})$. Since $\pi _0=\epsilon _{2n+1}$, then $\pi _0(2n+1)=2n+1$. Furthermore, since $\pi _i=t_{x_{i}}(\pi _{i-1})$ for all $i\in [Z_{2n+1}-1]$ and ${\mathcal {T}}_C$ has no transition $t_{2n+1}$, then $\pi _i(2n+1)=2n+1$, for all $i\in [Z_{2n+1}-1]$. If we delete the last same element $2n+1$, we can obtain a new snake ${\hat{C}}_{{\mathcal {T}}_C}^{\epsilon _{2n}}$ in $S_{2n}$. Then we have that $Z_{2n}\ge |{\hat{C}}_{{\mathcal {T}}_C}^{\epsilon _{2n}}|=|C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}|=Z_{2n+1}$, by Lemma 4, which causes a contradiction. Hence, ${\mathcal {T}}_C$ must contain at least one p-transition $t_{2n+1}$. $\square$

Consider one of the longest ${\mathcal {K}}$-snakes in $S_{2n+1}$ with its first permutation $\epsilon _{2n+1}$, whose transition sequence contains $t_{2n+1}$. By Theorem 1, we will obtain that every element of $[2n+1]$ must be transited to the top using one p-transition operation in this snake. This result is stated in the next theorem.

Theorem 2

Suppose $C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}$ is one of the longest snakes in $S_{2n+1}$ of size $Z_{2n+1}$, where ${\mathcal {T}}_C=(t_{x_{1}},\ldots ,t_{x_{Z_{2n+1}}})$, $C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}=(\pi _0,\pi _1,\ldots ,\pi _{Z_{2n+1}-1})$, and $\pi _0=\epsilon _{2n+1}$. And we denote $T_{e}(C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}})\triangleq \{\pi _{i}(x_{i+1}):0\le i\le Z_{2n+1}-1\}$. Then, we have that $T_e(C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}})=[2n+1]$.

To prove Theorem 2, we first introduce some notations and establish some lemmas. Let $C_{{\mathcal {T}}_C}^{\sigma ,\pi }$ be a noncyclic Gray code in $S_n$, where $\sigma$ is its first permutation, $\pi$ is its last permutation and ${\mathcal {T}}_C$ is its transition sequence. For convenience, we let $|C_{{\mathcal {T}}_C}^{\sigma ,\pi }|=M$, $C_{{\mathcal {T}}_C}^{\sigma ,\pi }=(\pi _0,\pi _1,\ldots ,\pi _{M-1})$ and ${\mathcal {T}}_C=(t_{x_{1}},\ldots ,t_{x_{M-1}})$. Moreover, let $T_{e}(C_{{\mathcal {T}}_C}^{\sigma ,\pi })$ be a set of elements which are transited to the top by using the p-transitions, defined by $T_{e}(C_{{\mathcal {T}}_C}^{\sigma ,\pi })=\{\pi _{i}(x_{i+1}):0\le i\le M-2\}$.

Lemma 5

Suppose $C_{{\mathcal {T}}_C}^{\sigma ,\epsilon _n}$ is defined as above, where $\epsilon _n$ is the identity permutation in $S_n$. If $\sigma (1)=n$, then $T_{e}(C_{{\mathcal {T}}_C}^{\sigma ,\epsilon _n})\supseteq [n-1]$.

Proof

Since its first permutation is $\sigma$ with $\sigma (1)=n$, then $\sigma$ has an inversion (n, i) for all $i\in [n-1]$. While its last permutation is $\epsilon _n$ with $\epsilon (n)=n$, then $\epsilon _n$ has no inversion (n, i) for any $i\in [n-1]$. Only applying one p-transition on some element $i\in [n-1]$, the permutation induced by the operation will has no inversion (n, i). Hence, $T_{e}(C_{{\mathcal {T}}_C}^{\sigma ,\epsilon _n})\supseteq [n-1]$. $\square$

In order to prove Theorem 2, we still need the following property of the noncyclic Gray codes.

Lemma 6

Suppose $C_{{\mathcal {T}}_C}^{\sigma ,\pi }$ is defined as above, where $\sigma (1)=n$. If $n\notin T_{e}(C_{{\mathcal {T}}_C}^{\sigma ,\pi })$, then ${\pi }^{-1}(n)=|T_{e}(C_{{\mathcal {T}}_C}^{\sigma ,\pi })|+1$. Furthermore, when $T_{e}(C_{{\mathcal {T}}_C}^{\sigma ,\pi })=[n-1]$, we have ${\pi }^{-1}(n)=n$.

Proof

Since $n\notin T_{e}(C_{{\mathcal {T}}_C}^{\sigma ,\pi })$, then the element n isn’t transited to the top all the time. For any two permutations $\pi _{k},\pi _{k-1},$ where $k\in [M-1]$, then we have that $\pi _{k}=t_{x_k}(\pi _{k-1})$ and $\pi _{k-1}(x_{k})\ne n$. Thus, $\pi _{k}$ has no inversion $(n,\pi _{k-1}(x_k))$ whether $\pi _{k-1}$ has an inversion $(n,\pi _{k-1}(x_k))$ or not. Hence, $\pi$ has no inversion (n, i) for some $i\in [n-1]$ if only if the element i is transited to the top in one p-transition operation. Since $\sigma$ has an inversion (n, i) for every $i\in [n-1]$ and $T_{e}(C_{{\mathcal {T}}_C}^{\sigma ,\pi })$ is a set of elements which are transited to the top, then $\pi$ has no inversion (n, i) for any $i\in T_{e}(C_{{\mathcal {T}}_C}^{\sigma ,\pi })$. Hence, $\pi ^{-1}(n)=|T_{e}(C_{{\mathcal {T}}_C}^{\sigma ,\pi })|+1$. Specially, if $T_{e}(C_{{\mathcal {T}}_C}^{\sigma ,\pi })=[n-1]$, then $\pi ^{-1}(n)=n$. $\square$

Next, we will prove Theorem 2 by using the above lemmas.

Proof

By Theorem 1, ${\mathcal {T}}_C$ must have one p-transition $t_{2n+1}$. We let $t_{x_{j}}$ be the first $t_{2n+1}$. Since $t_{x_{j}}$ is the first $t_{2n+1}$ and $\pi _0=\epsilon _{2n+1}$, then $\pi _{k}(2n+1)=2n+1$ for all $0\le k\le j-1$. Hence, $\pi _{j}(1)=t_{x_j}(\pi _{j-1})(1)=\pi _{j-1}(x_j)=\pi _{j-1}(2n+1)=2n+1$. If $t_{x_j}$ is the last transition, then $j=Z_{2n+1}$ and $\pi _{0}(1)=t_{x_{j}}(\pi _{j-1})(1)=2n+1$, since $\pi _0=\epsilon _{2n+1}$, which causes a contradiction. Therefore, $1\le j\le Z_{2n+1}-1$.

Since $C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}$ is a snake in $S_{2n+1}$ with its first permutation $\epsilon _{2n+1}$, then there is a noncyclic snake ${\hat{C}}_{{\mathcal {T}}_{{\hat{C}}}}^{\pi _j,\epsilon _{2n+1}}$, i.e., it is one part of this snake from the $(j+1)$-th permutation to the first permutation. Hence, it is a noncyclic Gray code, where ${\mathcal {T}}_{{\hat{C}}}=(t_{x_{j+1}},\ldots ,t_{x_{Z_{2n+1}}})$. By Lemma 5, since $\pi _j(1)=2n+1$ and $\epsilon _{2n+1}$ is the last permutation of ${\hat{C}}_{{\mathcal {T}}_{{\hat{C}}}}^{\pi _j,\epsilon _{2n+1}}$, we have that

$$\begin{aligned} T_{e}\Big ({\hat{C}}_{{\mathcal {T}}_{{\hat{C}}}}^{\pi _j,\epsilon _{2n+1}}\Big )\supseteq [2n]. \end{aligned}$$

(2)

By (2) and $\pi _{j-1}(x_{j})=2n+1$, we have that $T_e(C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}})=[2n+1]$. $\square$

4 Construction of a snake in $S_{2n+2}$ from a snake in $S_{2n+1}$

In this section, we will give a construction of a ${\mathcal {K}}$-snake in $S_{2n+2}$ from one of the longest ${\mathcal {K}}$-snakes in $S_{2n+1}$ for all $n\ge 1$. According to some properties of the ${\mathcal {K}}$-snakes, we can prove that this construction is feasible.

Suppose $C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}$ is one of the longest snakes in $S_{2n+1}$, where $|C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}|=Z_{2n+1}$, ${\mathcal {T}}_{C}=(t_{x_1},t_{x_2},\ldots ,t_{x_{Z_{2n+1}}})$ and $C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}=(\pi _0,\pi _1,\ldots ,\pi _{Z_{2n+1}-1})$. Next, we will construct a permutation sequence ${\hat{C}}$ in $S_{2n+2}$ from $C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}$, where $|{\hat{C}}|=Z_{2n+1}+2$.

In order to construct ${{\hat{C}}}$, we need some definitions and notations. Next, we define $p_k:S_n\rightarrow S_n$ by one “push-to-the-top” on element k, for $1\le k\le n$, that is

$$\begin{aligned} p_k([a_1,a_2,\ldots .,a_{i-1},k,a_{i+1},\ldots ,a_n])=[k,a_1,a_2,\ldots ,a_{i-1},a_{i+1},\ldots ,a_n], \end{aligned}$$

for any $[a_1,a_2,\ldots .,a_{i-1},k,a_{i+1},\ldots ,a_n]\in S_n$. In particular, when k is the top element, then $p_k([k,a_2,\ldots ,a_n])=[k,a_2,\ldots ,a_n]$. Hence, an initial permutation $\sigma _0$ in $S_n$ and a sequence $p_{y_1},\ldots ,p_{y_l}$ can determine a sequence of permutations $\sigma _0,\sigma _1,\ldots ,\sigma _l$ in $S_n$, where $\sigma _i=p_{y_i}(\sigma _{i-1})$, $y_i\in [n]$ for all $i\in [l]$.

Consider $C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}$, we can obtain a sequence $(p_{y_1},\ldots ,p_{y_{Z_{2n+1}}})$, denoted by $P_{C}$, where $y_i=\pi _{i-1}(x_i)$ for all $i\in [Z_{2n+1}]$. Hence, $P_C$ and $\pi _0$ can generate $C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}$, where $\pi _{i}=p_{y_i}(\pi _{i-1})$ for all $i\in [Z_{2n+1}]$ and $\pi _{Z_{2n+1}}=\pi _0$. Here, we call $P_C$ a generating sequence of $C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}$.

In order to give one construction of ${\hat{C}}$, firstly, we choose $\epsilon _{2n+2}$ to be the first permutation of ${\hat{C}}$. Let $P_{{\hat{C}}}$ be a generating sequence of ${\hat{C}}$, and let ${\hat{{\mathcal {T}}}}$ be a transition sequence of ${\hat{C}}$. For convenience, we let ${\hat{C}}\triangleq ({{\hat{\pi }}}_0,{{\hat{\pi }}}_1,\ldots ,{{\hat{\pi }}}_{Z_{2n+1}+1})$, ${\hat{{\mathcal {T}}}}\triangleq (t_{\hat{x}_1},t_{\hat{x}_2},\ldots ,t_{\hat{x}_{Z_{2n+1}+1}})$, and $P_{{\hat{C}}}\triangleq (p_{{\hat{y}}_1},p_{{\hat{y}}_2},\ldots ,p_{{\hat{y}}_{Z_{2n+1}+1}})$, where ${{\hat{\pi }}}_0=\epsilon _{2n+2}$. Secondly, we propose one construction of $P_{{\hat{C}}}$ in the following.

When $i=1$, we let ${\hat{y}}_1=2n+2$. Moreover, for $2\le i\le Z_{2n+1}+1$, we let ${\hat{y}}_{i}=y_{i-1}$.

According to the construction of $P_{{\hat{C}}}$ and ${\hat{\pi }}_0$, we obtain ${\hat{\pi }}_k=p_{{\hat{y}}_{k}}({\hat{\pi }}_{k-1})$ for all $k\in [Z_{2n+1}+1]$. Hence, we get a permutation sequence ${\hat{C}}$ with its first permutation $\epsilon _{2n+2}$ in $S_{2n+2}$, where ${\hat{C}}=({\hat{\pi }}_0,{\hat{\pi }}_1,\ldots ,{\hat{\pi }}_{Z_{2n+1}},{\hat{\pi }}_{Z_{2n+1}+1})$. In the next section, we will prove that ${\hat{\pi }}_{0}={\hat{\pi }}_{Z_{2n+1}+1}=\epsilon _{2n+2}$. For simplicity, we let ${\hat{C}}^{\epsilon _{2n+2}}\triangleq ({\hat{\pi }}_0,{\hat{\pi }}_1,\ldots ,{\hat{\pi }}_{Z_{2n+1}})$. Next, we will prove that ${\hat{C}}^{\epsilon _{2n+2}}$ is a ${\mathcal {K}}$-snake in $S_{2n+2}$.

Remark 1

When ${\hat{C}}^{\epsilon _{2n+2}}$ is a Gray code, then ${\hat{y}}_i\ne {\hat{\pi }}_{i-1}(1)$ for all $i\in [Z_{2n+1}+1]$. Hence, in this case, we can use ${\hat{C}}^{\epsilon _{2n+2}}$ and $P_{{\hat{C}}}$ to obtain the transition sequence $\hat{{\mathcal {T}}}=(t_{\hat{x}_1},t_{\hat{x}_2},\ldots ,t_{\hat{x}_{Z_{2n+1}+1}})$, where ${\hat{y}}_i={\hat{\pi }}_{i-1}(\hat{x}_i)$ for all $i\in [Z_{2n+1}+1]$.

5 A rigorous proof of $Z_{2n+2}>Z_{2n+1}$

In this section we will prove that the length of the longest snake in $S_{2n+2}$ is longer than the length of the longest snake in $S_{2n+1}$ for all $n\ge 1$. That is, we need to prove that $Z_{2n+2}>Z_{2n+1}$ for all $n\ge 1$. Specially, assume that ${\hat{C}}^{\epsilon _{2n+2}}$ is a ${\mathcal {K}}$-snake in $S_{2n+2}$, we will obtain that $Z_{2n+2}\ge |{{\hat{C}}^{\epsilon _{2n+2}}}|=Z_{2n+1}+1>Z_{2n+1}$. In order to prove that $Z_{2n+2}>Z_{2n+1}$, we only need to prove that ${\hat{C}}^{\epsilon _{2n+2}}$ is a ${\mathcal {K}}$-snake in $S_{2n+2}$. To prove this result, we need the following theorem.

Theorem 3

Let ${\hat{C}}^{\epsilon _{2n+2}}$ and $C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}$ be defined as above. Suppose $l_k={{\hat{\pi }}_{k}}^{-1}(2n+2)$, for all $k\in [Z_{2n+1}+1]$. And let ${\hat{\pi }}_{k}^{<2n+2>}\triangleq [{\hat{\pi }}_{k}(1),\ldots ,{\hat{\pi }}_{k}(l_k-1),{\hat{\pi }}_{k}(l_k+1),\ldots , {\hat{\pi }}_{k}(2n+2)]$ for all $k\in [Z_{2n+1}+1]$. Then, we have that ${\hat{\pi }}_{k}^{<2n+2>}=\pi _{k-1}$ for all $k\in [Z_{2n+1}+1]$, where $\pi _{Z_{2n+1}}=\pi _0$. Moreover, we can obtain that ${\hat{\pi }}_{0}={\hat{\pi }}_{Z_{2n+1}+1}=\epsilon _{2n+2}$ and ${\hat{C}}^{\epsilon _{2n+2}}$ is a Gray code with $P_{{\hat{C}}}$.

Proof

From $P_{{\hat{C}}}$ and ${\hat{\pi }}_0$, we have ${\hat{\pi }}_1=p_{{\hat{y}}_1}({\hat{\pi }}_0)=[2n+2,1,2,\ldots ,2n+1]$. Since $\pi _0=\epsilon _{2n+1}$, then

$$\begin{aligned} {\hat{\pi }}_{1}^{<2n+2>}=\pi _0. \end{aligned}$$

(3)

Firstly, we can obtain a fact that for any $\sigma \in S_{2n+2}$ and $y\in [2n+1]$, then

$$\begin{aligned} p_y(\sigma )^{<2n+2>}=p_y(\sigma ^{<2n+2>}). \end{aligned}$$

(4)

For all $1\le i\le Z_{2n+1}$, since ${\hat{y}}_{i+1}=y_i$, then ${\hat{y}}_{i+1}\in [2n+1]$. By (3) and (4), we have

$$\begin{aligned} {\hat{\pi }}_{2}^{<2n+2>}=p_{{\hat{y}}_2}({\hat{\pi }}_1)^{<2n+2>}=p_{{\hat{y}}_2}({\hat{\pi }}_{1}^{<2n+2>})=p_{y_1}(\pi _0)=\pi _1. \end{aligned}$$

(5)

Similarly, we can obtain that ${\hat{\pi }}_{k}^{<2n+2>}=\pi _{k-1}$ for all $k\in [Z_{2n+1}+1]$.

By Theorem 2, we have that $T_e(C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}})=[2n+1]$. According to the construction of $P_{{\hat{C}}}$, we obtain that

$$\begin{aligned} T_e({\hat{C}}^{{\hat{\pi }}_1,{\hat{\pi }}_{Z_{2n+1}+1}})=T_e(C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}})=[2n+1]. \end{aligned}$$

(6)

Since ${\hat{\pi }}_1(1)=2n+2$, by Lemma 6 and (6), we have that ${\hat{\pi }}_{Z_{2n+1}+1}(2n+2)=2n+2$. Moreover, ${\hat{\pi }}_{Z_{2n+1}+1}^{<2n+2>}=\pi _{Z_{2n+1}}=\pi _{0}=\epsilon _{2n+1}$. Hence, we obtain ${\hat{\pi }}_{Z_{2n+1}+1}={\hat{\pi }}_0=\epsilon _{2n+2}$.

Since $C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}$ is a snake and ${\hat{\pi }}_{k}^{<2n+2>}=\pi _{k-1}$ for all $k\in [Z_{2n+1}]$, we have that ${\hat{\pi }}_i\ne {\hat{\pi }}_j$ for two distinct $i,j\in [Z_{2n+1}]$. Moreover, we have ${\hat{\pi }}_{0}^{<2n+2>}={\hat{\pi }}_{1}^{<2n+2>}$ and ${\hat{\pi }}_{0}\ne {\hat{\pi }}_1$, then ${\hat{\pi }}_i\ne {\hat{\pi }}_j$ for two distinct $i,j\in [Z_{2n+1}]\cup {\{0\}}$. Hence, we obtain that ${\hat{C}}^{\epsilon _{2n+2}}$ is a Gray code with $P_{{\hat{C}}}$. $\square$

According to Remark 1 and Theorem 3, we know that ${\hat{C}}^{\epsilon _{2n+2}}$ is a Gray code with $\hat{{\mathcal {T}}}$. Next, we prove the main result using Theorem 3.

Theorem 4

The length of the longest snake in $S_{2n+2}$ is longer than the length of the longest snake in $S_{2n+1}$, for all $n\ge 1$, i.e., $Z_{2n+2}>Z_{2n+1}$.

Proof

By Lemma 3, there must be a snake $C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}$ of size $Z_{2n+1}$, where $C_{{\mathcal {T}}_C}^{\epsilon _{2n+1}}=(\pi _0,\pi _1,\ldots ,\pi _{Z_{2n+1}-1})$ and $\pi _0=\epsilon _{2n+1}$. By the construction of ${{\hat{C}}^{\epsilon _{2n+2}}}$ and Theorem 3, we know that ${{\hat{C}}^{\epsilon _{2n+2}}}$ is a Gray code, where ${{\hat{C}}^{\epsilon _{2n+2}}}=({\hat{\pi }}_0,{\hat{\pi }}_1,\ldots ,{\hat{\pi }}_{Z_{2n+1}})$. Next, we will prove that ${{\hat{C}}^{\epsilon _{2n+2}}}$ is a snake in $S_{2n+2}$.

By Theorem (3), we have that

$$\begin{aligned} {\hat{\pi }}_{k}^{<2n+2>}=\pi _{k-1} \end{aligned}$$

(7)

for all $k\in [Z_{2n+1}]$. According to Lemma 1 and (7), for any two distinct permutations ${\hat{\pi }}_i,{\hat{\pi }}_j\in {{\hat{C}}^{\epsilon _{2n+2}}},1\le i,j\le Z_{2n+1}$, we can obtain that

$$\begin{aligned} d_{K}\big ({\hat{\pi }}_i,{\hat{\pi }}_j\big )\ge \,&d_{K}\Big ({\hat{\pi }}_{i}^{<2n+2>},{\hat{\pi }}_{j}^{<2n+2>}\Big )\nonumber \\ =\,&d_{K}(\pi _{i-1},\pi _{j-1})\nonumber \\ \ge \,&2. \end{aligned}$$

(8)

For $i=0,2\le j\le Z_{2n+1}$, we have that

$$\begin{aligned} d_{K}\big ({\hat{\pi }}_0,{\hat{\pi }}_j\big )=d_{K}\big (\epsilon _{2n+2},{\hat{\pi }}_j\big )\ge \,&d_{K}\Big (\epsilon _{2n+2}^{<2n+2>},{\hat{\pi }}_{j}^{<2n+2>}\Big )\nonumber \\ =\,&d_{K}(\epsilon _{2n+1},\pi _{j-1})\nonumber \\ =\,&d_{K}(\pi _0,\pi _{j-1})\nonumber \\ \ge \,&2. \end{aligned}$$

(9)

When $i=0,j=1$, since $n\ge 1$, we have that

$$\begin{aligned} d_{K}({\hat{\pi }}_0,{\hat{\pi }}_1)=2n+1\ge 2. \end{aligned}$$

(10)

By (8), (9) and (10), since ${{\hat{C}}^{\epsilon _{2n+2}}}$ is a Gray code in $S_{2n+2}$, then ${{\hat{C}}^{\epsilon _{2n+2}}}$ is a ${\mathcal {K}}$-snake in $S_{2n+2}$. Hence, we have that

$$\begin{aligned} Z_{2n+2}\ge \,&|{\hat{C}}^{\epsilon _{2n+2}}|\\ =\,&Z_{2n+1}+1\\ >\,&Z_{2n+1}. \end{aligned}$$

So, the length of the longest snake in $S_{2n+2}$ is longer than the length of the longest snake in $S_{2n+1}$ for all $n\ge 1$. $\square$

6 Examples of a snake in $S_{2n+2}$ from one of the longest snakes in $S_{2n+1}$

6.1 A snake in $S_4$ from one of the longest snakes in $S_3$

Yehezkeally and Schwartz [16] proposed one of the longest snakes in $S_3$ of size 3, denoted by $C_{{\mathcal {T}}_C}^{\epsilon _3}$, where $C_{{\mathcal {T}}_C}^{\epsilon _3}=([1,2,3],[3,1,2],[2,3,1])$ and ${\mathcal {T}}_C=(t_3,t_3,t_3)$. Next, we construct a snake ${\hat{C}}^{\epsilon _4}$ in $S_4$ from $C_{{\mathcal {T}}_C}^{\epsilon _3}$ in $S_3$ using the above construction, where ${\hat{C}}^{\epsilon _4}=({\hat{\pi }}_0,{\hat{\pi }}_1,{\hat{\pi }}_2,{\hat{\pi }}_3)$. Let $P_{{\hat{C}}^{\epsilon _4}}$ be a generating sequence of ${\hat{C}}^{\epsilon _4}$, where $P_{{\hat{C}}^{\epsilon _4}}=(p_{{\hat{y}}_1},p_{{\hat{y}}_2},p_{{\hat{y}}_3},p_{{\hat{y}}_4})$. By $C_{{\mathcal {T}}_C}^{\epsilon _3}$, we have that $P_{C_{{\mathcal {T}}_C}^{\epsilon _3}}=(p_3,p_2,p_1)$. According to the construction of $P_{{\hat{C}}^{\epsilon _4}}$ and ${\hat{\pi }}_0$, we have that $P_{{\hat{C}}^{\epsilon _4}}=(p_4,p_3,p_2,p_1)$ and ${\hat{\pi }}_0=\epsilon _4$. Then we obtain that ${\hat{\pi }}_k=p_{{\hat{y}}_{k}}({\hat{\pi }}_{k-1})$ for all $k\in [3]$.

Therefore, we have ${\hat{C}}^{\epsilon _4}=([1,2,3,4],[4,1,2,3],[3,4,1,2],[2,3,4,1])$.

6.2 A snake in $S_6$ from one of the longest snakes in $S_5$

Horovitz and Etzion [9] gave one of the longest snakes in $S_5$ of size 57, denoted by $C_{{\mathcal {T}}_C}^{\epsilon _5}$, where $C_{{\mathcal {T}}_C}^{\epsilon _5}=(\pi _0,\pi _1,\ldots ,\pi _{56})$. For convenience, we will give the permutation sequence in Fig. 1, and its transition sequence ${\mathcal {T}}_C=(s,s,s)$ with a partial transition sequence $s=(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, we can construct a snake ${\hat{C}}^{\epsilon _6}$ in $S_6$ from $C_{{\mathcal {T}}_C}^{\epsilon _5}$ in $S_5$ using the above construction, where ${\hat{C}}^{\epsilon _6}=({\hat{\pi }}_0,{\hat{\pi }}_1,\ldots ,{\hat{\pi }}_{57})$. Let $P_{{\hat{C}}^{\epsilon _6}}$ be a generating sequence of ${\hat{C}}^{\epsilon _6}$, where $P_{{\hat{C}}^{\epsilon _6}}=(p_{{\hat{y}}_1},p_{{\hat{y}}_2},\ldots ,p_{{\hat{y}}_{58}})$.

Fig. 1

The $(5,57,\mathcal {K})$-snake $C_{\mathcal {T}_C}^{\epsilon _5}$

By $C_{{\mathcal {T}}_C}^{\epsilon _5}$, we can obtain that $P_{C_{{\mathcal {T}}_C}^{\epsilon _5}}=(p_3,p_2,p_5,p_3,p_2,p_4,p_3,p_1,p_5,p_3,p_1,p_2,p_3$, $p_1,p_4,p_3,p_5,p_2,p_1,p_5,p_2,p_4,p_5,p_2,p_3,p_5,p_1,p_4,p_5,p_1,p_2,p_5,p_1,p_3,p_5,p_4,p_2,p_1$, $p_4,p_2,p_3,p_4,p_2,p_5,p_4,p_1,p_3,p_4,p_1,p_2,p_4,p_1,p_5,p_4,p_3,p_2,p_1)$.

According to the construction of $P_{{\hat{C}}^{\epsilon _6}}$ and ${\hat{\pi }}_0$, we have that ${\hat{\pi }}_0=\epsilon _6$ and $P_{{\hat{C}}^{\epsilon _6}}=(p_6,P_{C_{{\mathcal {T}}_C}^{\epsilon _5}})$.

Then by $P_{{\hat{C}}^{\epsilon _6}}$ and ${\hat{\pi }}_0$, we can obtain ${\hat{C}}^{\epsilon _6}=({\hat{\pi }}_0,{\hat{\pi }}_1,\ldots ,{\hat{\pi }}_{57})$ in Fig. 2, where ${\hat{\pi }}_{k}=p_{{\hat{y}}_k}({\hat{\pi }}_{k-1})$ for all $k\in [57]$.

Fig. 2

The $(6,58,\mathcal {K})$-snake $\hat{C}^{\epsilon _6}$

7 Conclusions

Gray codes in $S_n$ under the Kendall’s $\tau$-metric using only “push-to-the-top” operations play an important role in the framework of rank modulation scheme for flash memories. In this paper, we proved the conjecture of Horovitz and Etzion that the length of the longest snake in $S_{2n+2}$ is longer than the length of the longest snake in $S_{2n}$. We also gave a construction of a snake with size $Z_{2n+1}+1$ in $S_{2n+2}$ from one of the longest snakes of $Z_{2n+1}$ in $S_{2n+1}$.