An Upper Bound for Sorting $R_n$ with LE

Abstract

A permutation on a given alphabet $\varSigma = (1, 2, 3,\ldots , n)$ is a sequence of elements in the alphabet where every element occurs precisely once. $S_n$ denotes the set of all such permutations on a given alphabet. $I_n \in S_n$ be the Identity permutation where elements are in ascending order i.e. $(1, 2, 3,\ldots , n)$. $R_n \in S_n$ is the reverse permutation where elements are in descending order, i.e. $R_n =(n, n-1, n-2,\ldots , 2, 1)$. An operation has been defined in OEIS which consists of exactly two moves: set-rotate that we call Rotate and pair-exchange that we call Exchange. Rotate is a left rotate of all elements (moves leftmost element to the right end) and Exchange is the pair-wise exchange of the two leftmost elements. We call this operation as LE. The optimum number of moves for transforming $R_n$ into $I_n$ with LE operation are known for $n \le 10$; as listed in OEIS with identity A048200. The contributions of this article are: (a) a novel upper bound for the number of moves required to sort $R_n$ with LE has been derived; (b) the optimum number of moves to sort the next larger $R_n$ i.e. $R_{11}$ has been computed. Sorting permutations with various operations has applications in genomics and computer interconnection networks.

1 Introduction

Sorting a permutation can be either in an increasing or a decreasing order. In this article, increasing order is employed. The alphabet for the permutations is $\varSigma = (1, 2, 3, \ldots , n)$. LE operation consists of two generators: (i) Rotate that cyclically left shifts the entire permutation and (ii) Exchange that swaps the elements at the two left most positions. The application of (i) and (ii) yields the corresponding moves L and E respectively. 1-based indexing is employed, thus, the two leftmost indices are one and two. $S_n$ is the set of all permutations over $\varSigma$. $R_n$ is the reverse permutation of $\varSigma$, i.e. $R_n= (n, n-1,\ldots ,3, 2, 1)$. The identity permutation $I_n= (1, 2, 3,\ldots ,n-1, n)$. The problem of transforming $R_n$ into $I_n$ (i.e. sorting $R_n$) with LE operation is of theoretical interest and has been studied. The problem appears in OEIS [1] as follows “A048200 Minimal length pair-exchange/set-rotate sequence to reverse n distinct ordered elements”.

The optimum number of moves to sort $R_n$ with LE appears with a sequence number of A048200, OEIS [1] where the values are known only for $n\le 11$ [1] ($n=11$ is our contribution). We establish the first upper bound on the number of moves required to sort $R_n$ with LE.

A Cayley graph $\varGamma$ corresponding to an operation O with a generator set G consists of n! vertices each corresponding to a unique permutation that denotes it. An edge from a vertex u to another vertex v indicates that when a generator $g \in G$ acts upon permutation u yields v. Applying a generator is commonly known as making a move. An upper bound k to sort any $\pi \in S_n$ indicates that the distance between any two permutations in $\varGamma$ is at most k. An exact upper bound equals the diameter of $\varGamma$ [3]. Cayley graphs are shown to posses various desirable properties in the design of computer interconnection networks [3, 8]. Various operations to sort permutations have been posed [8]. A permutation models a genome where a gene is presumed to be unique and an operation like transposition, reversal etc. models the corresponding mutation. Thus, transforming permutations with various operations has applications in genomic studies.

Jerrum showed that when the number of generators is greater than one, the minimum sequence of generators (also called as distance) to sort a permutation is hard to compute [2]. LE operation has two generators and the complexity of transforming one permutation in to another with LE operation is not known. Exchange move is a reversal of length two, in fact it is a prefix reversal of length two. Chen and Skiena studied sorting permutations of length n with reversals of size p [5]. For both permutations and circular permutations for all n and p, they characterized the number of equivalence classes of permutations. For sorting all circular permutations of length n that can be sorted by reversals of length p an upper bound of $O(n^2/p+pn)$ and a lower bound of $\varOmega (n^2/p^2+n)$ were shown. For sorting permutations with (unrestricted) prefix reversals the operation that has $n-1$ generators, the best known upper bound is $18n/11+O(1)$ [4]. In LE operation, Rotate cyclically shifts the entire permutation whereas in [6] a modified bubblesort is considered, where, in addition to the regular moves, a swap is allowed between elements at positions 1 and n. Given an operation O, all the moves of O constitute its generator set. Jerrum showed that when the number of generators is greater than one, the minimum sequence of generators to sort a permutation is hard to compute [2]. LE operation has two generators and the complexity of transforming one permutation into another with LE operation is not known. We call O symmetric if for any move of O its inverse also belongs to O. Exchange is inverse of itself whereas Rotate does not have an inverse. Thus, LE is not symmetric. Further, LE is very restrictive due to the presence of Rotate move compared to the other operations that are frequently applied in genetic studies e.g. [7]. The methodology of this article might be helpful for problems whose generator set does not have a Rotate generator. Research in the area of Cayley graphs pertaining to their efficacy in modelling a computer interconnection network, their properties in terms of diameter, presence of greedy cycles in them etc. has been active [11,12,13,14,15].

Two permutations are equivalent if one can be transformed into another by applying a finite number of Rotate moves. In order to show that LE operation generates the entire symmetric group $S_n$, we need only show that any two elements can be swapped.

Transformation of strings also has been extensively studied [16, 17]. Several string transformation problems including the burnt pancake distance problem are shown to be NP-hard [17]. An operation called as short reversal on strings has been defined [7] that has exactly two types of generators. The computation of short reversal distance has been reduced to the computation of a Maximum Independent Set on the corresponding graph that is computed from the two given input strings [9] an efficient algorithm for it has been designed in [10].

Observation 1

Any two elements can be swapped with LE operation.

Proof

Consider two arbitrary elements a and b in a permutation $\pi$. WLOG assume that a is to the left of b. So $\pi = (\ldots , u, a, v,\ldots , x, b, y,\ldots )$. First we perform a sequence of Rotate moves to yield $(a, v,\ldots , x, b, y,\ldots , u)$. Here we perform a sequence of (Exchange followed by Rotate) to yield $(a, b, y,\ldots , u, v,\ldots , x,)$. After Rotate, Exchange, Rotate this yields $(b,\ldots , u, v,\ldots , x, a, y)$ where a is between x, y. We follow the same procedure to place b between u and v. Then we will get a permutation that is equivalent to the permutation in which a and b are swapped. Rotate moves accomplish the rest of the task.

Let $\pi$ be the one based index array containing the input permutation. The element at an index i of $\pi$ is denoted by $\pi [i]$. Initially for all i, $\pi [i]= R_n[i]$. A block is a sublist (continuous elements of a permutation) that is sorted. Let EL denote Exchange move followed by a Rotate move. Further, let $(EL)^p$ be p consecutive executions of EL. Let $L^p$ be p consecutive executions of L. We define a permutation $P_{r,n} \in S_n$ as follows. The elements $1, 2, 3,\ldots , r$ are in sorted order. However, $(n, n-1,\ldots , r+1)$ that we call $U(P_{r,n})$ is inserted in between. Thus, $(1, 2, 3,\ldots , r)$ is split into two blocks with $U(P_{r,n})$ in between. Further, the starting position of $U(P_{r,n})$ in $P_{r,n}$ is $x+2$ where $r=2^k-x$ and $2^{k-1}< r \le 2^{k}$. Let M(n) be the number of moves required to sort $R_n$ with LE. Let f(x) denote the number of additional moves required to sort $R_n$ with LE when compared to $R_{n-1}$. Therefore, number of moves required to sort $R_n$ with LE is sum of all f(x) where x ranges from 1 to n.

2 Algorithm

The algorithm that we design is called Algorithm LE. The algorithm first transforms $R_n$ into $P_{3,n}$ by executing $n-2~$ L moves and an E move. Subsequently, $P_{i+1,n}$ is obtained from $P_{i,n}$ by executing the moves specified by Lemma 2. Thus, eventually we obtain $P_{n,n}$ which is $I_n$. Pseudo Code for the Algorithm LE is shown below.

Algorithm LE

Input: $R_n$. Output: $I_n$. Initialization: $\forall {i} \pi [i]=R_n[i]$. All moves are executed on $\pi$.

Lemma 1

The starting position of $U(P_{r,n})$ in $P_{r,n}$ is $x+2$ where $r=2^k-x$ and $2^{k-1}< r \le 2^{k}$.

Proof

Executing $n-2$ L moves and an E moves on $R_n$ yields $(1,2,n,n-1,\ldots ,3)$ which is $P_{3,n}$. Since, $3=2^2-1$, $x=1$. Thus, $x+2=1+2=3$. If we observe the starting position of $U(P_{3,n})$ in $P_{3,n}$ is $x+2=3$. Hence, lemma is true for $r=3$. Assume, that lemma is true for $r=2^k-x$. So, $P_{r,n}$ is $(1,2,\ldots ,x+1,n,n-1,\ldots ,r+1,x+2,x+3,\ldots ,r)$ where starting position of $U(P_{r,n})$ in $P_{r,n}$ is $x+2$ where $r=2^k-x$ and $2^{k-1}< r \le 2^{k}$. Executing $L^x$ yields $(x+1,n,n-1.\ldots ,r+1,x+2,x+3,\ldots ,r,1,2,\ldots ,x)$. Then executing $(EL)^{n-r-1}$ yields $(x+1,r+1,x+2,x+3,\ldots ,r,1,2,\ldots ,x,n,n-1,\ldots ,r+2)$. Then executing R yields $(r+1,x+2,\ldots ,r,1,2,\ldots ,x,n,n-1,\dots ,r+2,x+1)$. Then executing $(EL)^{r-x-1}$ yields $(r+1,1,2,\ldots ,x,n,n-1,\dots ,r+2,x+1,x+2,\ldots ,r)$. Then executing L yields $(1,2,\ldots ,x,n,n-1,\dots ,r+2,x+1,x+2,\ldots ,r,r+1)$ which is $P_{r+1,n}$. Since $r=2^k-x$, $r+1=2^k-(x-1)$. Therefore, the starting position of $U(P_{r+1,n})$ in $P_{r+1,n}$ should be $(x-1)+2=x+1$. In $P_{r+1,n}$ the starting position of $U(P_{r+1,n})$ is in fact $x+1$. Hence by mathematical induction Lemma 1 holds for all values of r.

Lemma 2

The number of moves required to obtain $P_{r+1,n}$ from $P_{r,n}$ is (a) $2n-2r$ if r= $2^k$ for some k. (b) $r-2^k+2n-2$ otherwise.

Proof

Case (a): $r=2^k$ for some k.

According to Lemma 1 the starting position of $U(P_{r,n})$ in $P_{r,n}$ is 2. Therefore, $P_{r,n}$ is $(1,n,n-1,\ldots ,r+1,2,3,\ldots ,r)$. Executing $(EL)^{n-r}$ yields $P_{r+1,n}$. Therefore, number of moves to obtain $P_{r+1,n}$ from $P_{r,n}$ when r is in the form of $2^k$ is $2*(n-r)=2n-2r$.

Case (b): $2^{k-1}< r < 2^k$.

Let us suppose $r=2^k-x$ where $2^{k-1}< r< 2^{k}$. According to Lemma 1 the starting position of $U(P_{r,n})$ in $P_{r,n}$ is $x+2$. Therefore, $P_{r,n}$ is $(1,2,\ldots ,x+1,n,n-1,\ldots ,r+1,x+2,x+3,\ldots ,r)$. Executing $L^{2^k-r}$ i.e. $L^x$ yields $(x+1,n,n-1,\ldots ,r+1,x+2,x+3,\ldots ,r,1,2,\ldots ,x)$. Then executing $(EL)^{n-r-1}$ yields $(x+1,r+1,x+2,\ldots ,r,1,2,\ldots ,x,n,n-1,\ldots ,r+2)$. Then executing R yields $(r+1,x+2,\ldots ,r,1,2,\ldots ,x,n,n-1,\dots ,r+2,x+1)$. Then executing $(EL)^{2r-2^k-1}$ i.e. $(EL)^{r-x-1}$ yields $(r+1,1,2,\ldots ,x,n,n-1,\dots ,r+2,x+1,x+2,\ldots ,r)$. Then executing L yields $P_{r+1,n}$. Therefore, number of moves to obtain $P_{r+1,n}$ from $P_{r,n}$ when r is not in the form of $2^k$ is $2^k-r+(2*(n-r-1))+1+(2*(2r-2^k-1))+1 =r-2^k+2n-2$.

3 Analysis

Lemma 3

The number of moves required to obtain $P_{3,n}$ from $R_n$ is 1 more than the number of moves required to obtain $P_{3,n-1}$ from $R_{n-1}$.

Proof

$P_{3,n}$ is obtained from $R_{n}$ by executing $n-2$ L moves and an E move, i.e. a total of $n-1$ moves. $P_{3,n-1}$ is obtained from $R_{n-1}$ by executing $n-3$ L moves and an E move, in a total of $n-2$ moves. Therefore, the number of moves required to obtain $P_{3,n}$ from $R_{n}$ is 1 more than the number of moves required to obtain $P_{3,n-1}$ from $R_{n-1}$.

Lemma 4

The number of moves required to obtain $P_{r+1,n}$ from $P_{r,n}$ is 2 more than the number of moves required to obtain $P_{r+1,n-1}$ from $P_{r,n-1}$ $\forall {r}\in (3,\ldots , n-2)$.

Proof

(a) According to Lemma 2, if $r=2^k$ for some k, the number of moves required to obtain $P_{r+1,n}$ from $P_{r,n}$ is $2n-2r$ where as the number of moves required to obtain $P_{r+1,n-1}$ from $P_{r,n-1}$ is $2(n-1)-2r=2n-2r-2$. Therefore, the number of moves required to obtain $P_{r+1,n}$ from $P_{r,n}$ is 2 more than number of moves required to obtain $P_{r+1,n-1}$ from $P_{r,n-1}$.

(b) According to Lemma 2, if $2^{k-1}< r <2^k$ for some k, the number of moves required to obtain $P_{r+1,n}$ from $P_{r,n}$ is $r-2^k+2n-2$ where as the number of moves required to obtain $P_{r+1,n-1}$ from $P_{r,n-1}$ is $r-2^k+2(n-1)-2=r-2^k+2(n)-4$. Therefore, the number of moves required to obtain $P_{r+1,n}$ from $P_{r,n}$ is 2 more than number of moves required to obtain $P_{r+1,n-1}$ from $P_{r,n-1}$.

From (a) and (b) it follows that Lemma 4 holds for all $r \in (3,4,\ldots ,n-2)$.

Lemma 5

If $x=2^k+1$ for some k then $f(x)= 2x-5$.

Proof

Sorting of $R_{x-1}$ involves $(P_{3,x-1}, P_{4,x-1},\ldots , P_{x-1,x-1})$ as intermediate permutations. According to Lemma 3, the number of moves required to obtain $P_{3,x}$ from $R_x$ is 1 more than the number of moves required to obtain $P_{3,x-1}$ from $R_{x-1}$. According to Lemma 4, the number of moves required to obtain $P_{r+1,x}$ from $P_{r,x}$ is 2 more than number of moves require to obtain $P_{r+1,x-1}$ from $P_{r,x-1}$ $\forall {r}\in (3, 4,\ldots , x-2)$. Since, $x=2^k+1, x-1=2^k$. According to Lemma 2 the number of steps required to obtain $P_{x,x}$ i.e. $I_x$ from $P_{x-1,x}$ is $2x-2(x-1)=2$. Therefore, number of additional moves required for sorting $R_x$ when compared to $R_{x-1}$ when $x=2^k+1$ for some k is $f(x) = 1+2(x-4)+2 = 2x-5$.

Lemma 6

If $x=2^k+2$ for some k, $f(x)=3x-6$.

Proof

Sorting of $R_{x-1}$ involves $(P_{3,x-1}, P_{4,x-1},\ldots , P_{x-1,x-1})$ as intermediate permutations. According to Lemma 3, the number of moves required to obtain $P_{3,x}$ from $R_x$ is 1 more than the number of moves required to obtain $P_{3,x-1}$ from $R_{x-1}$. According to Lemma 4, the number of moves required to obtain $P_{r+1,x}$ from $P_{r,x}$ is 2 more than number of moves require to obtain $P_{r+1,x-1}$ from $P_{r,x-1}$ $\forall {r}\in (3, 4,\ldots , x-2)$. Since, $x=2^k+2, x-1=2^k+1 = 2^{k+1}-(2^k-1)=2^{k+1}-(x-3)$. According to Lemma 2, the number of steps required to obtain $P_{x,x}$ i.e. $I_x$ from $P_{x-1,x}$ is $(x-1)-2^{k+1}+2x-2=(x-1)-2x+4+2x-2=x+1$. Therefore, number of additional moves required for sorting $R_x$ when compared to $R_{x-1}$ when $x=2^k+2$ for some k is $f(x)= 1+2(x-4)+(x+1)=3x-6$.

Lemma 7

If x not in the form $2^k+1$ or $2^k+2$ then $f(x)= f(x-1)+5$.

Proof

Recall, f(x) gives us number of additional moves required to sort $R_{x}$ with LE when compared to $R_{x-1}$. From Lemmas 3 and 4, we can say that difference between number of moves required to obtain $P_{x-2,x-1}$ from $R_{x-1}$ and the number of moves required to obtain $P_{x-2,x-2}$ i.e. $I_{x-2}$ from $R_{x-2}$ is same as the difference between number of moves required to obtain $P_{x-2,x}$ from $R_x$ and the number of moves required to obtain $P_{x-2,x-1}$ from $R_{x-1}$

(a) According to Lemma 4, the number of moves required to obtain $P_{x-1,x}$ from $P_{x-2,x}$ is 2 more than number of moves require to obtain $I_{x-1}$ from $P_{x-2,x-1}$.

(b) Let z be the number of moves require to obtain $I_{x-1}$ from $P_{x-2,x-1}$. Since $x-1$ cannot be of the form $2^k$ for some k, according to Lemma 2 $z=(x-2)-2^k+2(x-1)-2=x-2^k+2x-6$. Similarly, the number of moves require to obtain $I_{x}$ from $P_{x-1,x}$ is $(x-1)-2^k+2(x)-2=x-2^k+2x-3=z+3$. The number of moves require to obtain $I_x$ from $P_{x-1,x}$ is 3 more than the number of moves require to obtain $I_{x-1}$ from $P_{x-2,x-1}$.

Therefore, from (a) and (b), $f(x)=f(x-1)+2+3=f(x-1)+5$.

Theorem 1

An upper bound for number of moves required to sort $R_n$ with LE is $\frac{11}{6}n^2$.

Proof

According to Lemma 5, the value of f(x) when $x=2^k+1$ for some k is $2x-5$.

Therefore, for some k,

$f(2^k+1)= (2*(2^k+1))-5= 2^{k+1}-3$

According to Lemma 6, the value of f(x) when $x=2^k+2$ for some k is $3x-6$.

$f(2^k+2)= (3*(2^k+2))-6= 3*2^k$

According to the Lemma 7,

From Lemmas 5 and 6,

Therefore, for M(n) the total number of moves to sort $R_n$ we obtain the following recurrence relation.

Therefore, an upper bound for number of moves required for $R_n$ with LE is $\frac{11n^2}{6}$.

4 Exhaustive Search Results

An exhaustive search algorithm based on BFS, i.e. Algorithm Search, has been implemented to identify the optimum number of moves to sort $R_n$ for a given n. It yielded a novel value i.e. 67 for $n=11$. The known values for $n=1 \ldots 11$ are (0, 1, 2, 4, 10, 15, 23, 32, 42, 55, 67). We maintain a list of already visited permutations and we terminate upon reaching $I_n$. Each intermediate permutation is acted upon by the moves E and R yielding the corresponding permutations. BFS gives us the minimum number of moves to reach $I_n$ from $R_n$. We avoid two consecutive E move (that nullify each other). Notation: Node contains a permutation $\in S_n$ and its distance from $R_n$ corresponds to the optimal moves. Employing this algorithm, with a better processor and larger RAM one should be able to obtain optimum number of moves for higher values of n.

Algorithm Search

Initialization: The source vertex $\delta$ contains the permutation $R_n$ and its path is initialized to null. It is enqueued into BFS queue Q.

Input: $R_n$. Output: Optimum number of moves to reach $I_n$.

5 Conclusions and Future Work

The first known upper bound for sorting $R_n$ with LE operation is shown. The future work consists of identifying a tighter upper bound and obtaining optimum number of moves for sorting $R_n$ for larger values of n. An upper bound for sorting any permutation in $S_n$ with LE operation is open. Let $I_n^*$ be the set of all permutations that are equivalent to $I_n$. An upper bound for transforming $R_n$ into a $\pi \in I_n^*$ with LE operation is open where any convenient $\pi$ can be chosen.