Approximation Algorithms for Sorting λ-Permutations by λ-Operations

Abstract

Understanding how different two organisms are is one question addressed by the comparative genomics field. A well-accepted way to estimate the evolutionary distance between genomes of two organisms is finding the rearrangement distance, which is the smallest number of rearrangements needed to transform one genome into another. By representing genomes as permutations, one of them can be represented as the identity permutation, and, so, we reduce the problem of transforming one permutation into another to the problem of sorting a permutation using the minimum number of rearrangements. This work investigates the problems of sorting permutations using reversals and/or transpositions, with some additional restrictions of biological relevance. Given a value $\lambda$, the problem now is how to sort a $\lambda$-permutation, which is a permutation whose elements are less than $\lambda$ positions away from their correct places (regarding the identity), by applying the minimum number of rearrangements. Each $\lambda$-rearrangement must have size, at most, $\lambda$, and, when applied to a $\lambda$-permutation, the result should also be a $\lambda$-permutation. We present algorithms with approximation factors of $O\left({\lambda }^2\right)$, $O\left(\lambda \right)$, and $O\left(1\right)$ for the problems of Sorting $\lambda$-Permutations by $\lambda$-Reversals, by $\lambda$-Transpositions, and by both operations.

1. Introduction

One challenge in biology is to understand how species evolve, considering that new organisms arise from mutations that occurred in others. Using the principle of parsimony, the minimum number of rearrangements that transform one genome into another, called rearrangement distance, is a widely adopted way to estimate the evolutionary distance between two genomes. A genome rearrangement is a global mutation that alters the order and the orientation of the genes in a genome.

Depending on the genomic information available and the problems considered, a genome can be modeled in different ways. Considering that a genome has no repeated genes, we can model it as a permutation, with each element representing a gene. Each gene has an orientation inside the genome. Gene orientation is represented by a plus or minus sign in each element of the permutation. In this case, we say that the permutation is signed. Due to mapping problems in the genome, orientation information could not be available. In this scenario, we use unsigned permutations to represent the genomes. By representing one of the genomes as the identity permutation, we reduce the problem of transforming one permutation into another to the problem of sorting a permutation with the minimum number of rearrangements, which is called sorting rearrangement distance or simply distance.

A rearrangement model $\mathcal{M}$ is the set of valid rearrangements used to calculate the distance. A reversal rearrangement inverts a segment of the genome, and a transposition rearrangement swaps two adjacent segments of the genome. Genome rearrangements are also sometimes called operations.

The problems of Sorting Permutations by Transpositions and Sorting Unsigned Permutations by Reversals are NP-Hard [1,2]. The best known results for both problems are approximation algorithms with factor 1.375 [3,4]. Despite that, the problem of Sorting Signed Permutations by Reversals is solvable in polynomial time [5]. The variation in which the rearrangement model contains both (signed or unsigned) reversals and transpositions is NP-Hard [6]. For signed permutations, there are 2-approximation algorithms [7,8]. For unsigned permutations, the best approximation factor is $2k$ [7], where k is the approximation factor of an algorithm used for cycle decomposition of the breakpoint graph [9]. Given the best known value for k [9], this algorithm guarantees an approximation factor of $2.8334+ϵ$, where $ϵ>0$.

Extra restrictions can be added to these sorting problems, such as applying operations that only affect specific parts of a genome [10,11]. Other variants of the sorting problems emerged from the assumption that operations which affect large portions of a genome are less likely to occur [12]. Most of these variants add a constraint that limits the size of a valid operation [13,14,15]. The size of an operation is equal to the number of elements affected by it. Considering a size limit of 2, the problems of Sorting Unsigned Permutations by Reversals and/or Transpositions are solvable in polynomial time [13]. Considering a size limit of 3, the best known approximation factors for Sorting Unsigned Permutations by Reversals, by Transpositions, and by Reversals and Transpositions are 2 [13], $5/4$ [14], and 2 [15], respectively. For Sorting Signed Permutations by Reversals and by Reversals and Transpositions, the best known approximation factors are 5 [16] and 3 [16], respectively. Recently, Zhang et al. [17] presented polynomial algorithms to decide if a permutation can be sorted using a number of short operations equal to the lower bound for the distance, which are based on the number of inversions and entropy of the permutation (these concepts are described in Section 3 and Section 4).

The problem of Sorting (Unsigned or Signed) Permutations by $\lambda$-Operations is a generalization of the size limited variants in which an operation is valid if its size is less than or equal to $\lambda$. There are $O\left({\lambda }^2\right)$-approximation algorithms for Sorting Unsigned Permutations by $\lambda$-Reversals, by $\lambda$-Transpositions, and by $\lambda$-Reversals and $\lambda$-Transpositions [18]. The study of $\lambda$-operations is motivated by the observation that the rearrangements occurred in some species do not act on very large segments of the genome [12,19]. Using size limited operations makes more sense when one knows that the elements are not so far away from their original positions, so we introduce the study of Sorting $\lambda$-Permutations by $\lambda$-Operations. A permutation $\pi$ is a λ-permutation if all elements of $\pi$ are at a distance less than $\lambda$ from their correct positions considering the identity permutation.

We consider the problems of sorting (unsigned or signed) $\lambda$-permutations by $\lambda$-reversals, by $\lambda$-transpositions, and by $\lambda$-reversals and $\lambda$-transpositions. Some of the results for the problems of sorting unsigned $\lambda$-permutations were previously presented by us [20], but, to the best of our knowledge, there were no results for the sorting signed $\lambda$-permutations problems.

The paper is organized as follows. In Section 2, we present all concepts used in this paper and an NP-hardness proof for the sorting $\lambda$-permutations by $\lambda$-operations problems, considering four rearrangement models. In Section 3 and Section 4, we present $O\left({\lambda }^2\right)$-approximation algorithms for the sorting unsigned and signed $\lambda$-permutation problems, respectively. In Section 5, we present algorithms with approximation factors of $O\left(\lambda \right)$ and $O\left(1\right)$ for Sorting $\lambda$-Permutations by $\lambda$-Reversals and the other problems addressed, respectively. In Section 6, we show experimental results which compare the algorithms presented in Section 3, Section 4 and Section 5. We conclude the paper in Section 7.

2. Preliminaries and Basic Facts

We denote a signed permutation by $\pi$ = $({\pi }_1$${\pi }_2$ … ${\pi }_n)$, where ${\pi }_i\in \{-n,-(n-1),\dots ,-2,-1,+1,+2,\dots ,+(n-1),+n\}$ and $|{\pi }_i|\ne |{\pi }_j|$, for all $1\le i<j\le n$. We denote an unsigned permutation similarly but neglect the signs of the elements.

We assume that there are two extra elements ${\pi }_0=0$ and ${\pi }_{n+1}=n+1$ in $\pi$, but, for convenience, they are omitted from the permutation’s representation. Given an integer $\lambda \ge 2$ as input, we say that $\pi$ is a λ-permutation if we have $\left|\right|{\pi }_i|-i|<\lambda$ for all $1\le i\le n$. We define the size of a permutation as the number of elements in it, without counting ${\pi }_0$ and ${\pi }_{n+1}$.

Given two permutations $\pi$ and $\sigma$, the composition of $\pi$ and $\sigma$ is equal to $\pi ·\sigma =({\alpha }_1{\alpha }_2\dots {\alpha }_n)$, such that ${\alpha }_i=-{\pi }_{|{\sigma }_i|}$, if ${\sigma }_i<0$, and ${\alpha }_i={\pi }_{|{\sigma }_i|}$, otherwise. The inverse permutation of $\pi$, denoted by ${\pi }^{-1}$, is the permutation such that $\pi ·{\pi }^{-1}=(12\dots n)$. For example, given $\pi =(+2+4-5-1+3)$, we have that ${\pi }^{-1}=(-4+1+5+2-3)$.

An unsigned reversal is denoted by $\rho (i,j)$, with $1\le i<j\le n$, and it transforms an unsigned permutation $\pi =({\pi }_1{\pi }_2\dots {\pi }_n)$ into $\pi ·\rho (i,j)=({\pi }_1\dots {\pi }_{i-1}\underline{{\pi }_j\dots {\pi }_i}{\pi }_{j+1}$$\dots {\pi }_n)$. A signed reversal is denoted by $\overline{\rho }(i,j)$, with $1\le i\le j\le n$, and when applied on a signed permutation $\pi$ = $({\pi }_1$ ${\pi }_2$ … ${\pi }_n)$, the resulting permutation is $\pi ·\overline{\rho }(i,j)=({\pi }_1$$\dots {\pi }_{i-1}\underline{-{\pi }_j\dots -{\pi }_i}$${\pi }_{j+1}\dots {\pi }_{n-1}{\pi }_n)$. The size of a (signed or unsigned) reversal is given by $j-i+1$. For example, given the signed permutation $\pi$ = $(-1$$-4$$+3$$-2$$+5)$, we have $\pi ·\overline{\rho }(2,4)$ = $(-1$$+2$$-3$$+4$$+5)$, and the size of such operation is $4-2+1=3$. We say that $\rho (i,j)$ or $\overline{\rho (i,j)}$ is a λ-reversal if $j-i+1\le \lambda$.

An operation of transposition is denoted by $\tau (i,j,k)$, with 1 ≤ i < j < k ≤ $n+1$, and when applied on a (unsigned or signed) permutation $\pi$ = $({\pi }_1$${\pi }_2$ … ${\pi }_n)$, the result is the permutation $\pi ·\tau (i,j,k)$ = $({\pi }_1$${\pi }_2$ … ${\pi }_{i-1}$ $\underline{{\pi }_j\dots {\pi }_{k-1}}$ $\underline{{\pi }_i\dots {\pi }_{j-1}}$${\pi }_k$ … ${\pi }_n)$. The size of a transposition is given by $k-i$. For example, given the unsigned permutation $\pi$ = $(4$ 5 6 1 2 $3)$, we have $\pi ·\tau (1,4,7)$ = $(1$ 2 3 4 5 $6)$ and the size of such operation is $7-1=6$. We say that $\tau (i,j,k)$ is a λ-transposition if $k-i\le \lambda$.

The goal of these problems is to transform a $\lambda$-permutation $\pi$ into the identity permutation $\iota$ = $(1$ 2 ⋯$n)$ by applying the minimum number of $\lambda$-operations, which defines the sorting distance, such that each permutation generated during the process is also a $\lambda$-permutation.

We denote by $d_r^{\lambda }\left(\pi \right)$, $d_t^{\lambda }\left(\pi \right)$, and $d_{rt}^{\lambda }\left(\pi \right)$ the sorting distance for the sorting unsigned $\lambda$-permutation problems when we only have $\lambda$-reversals, $\lambda$-transpositions, and when we have both operations, respectively. Similarly, we denote by $d_{\overline{r}}^{\lambda }\left(\pi \right)$ and $d_{\overline{r}t}^{\lambda }\left(\pi \right)$ the sorting distance for the sorting signed $\lambda$-permutation problems when we only have $\lambda$-reversals and when we have both operations, respectively.

2.1. Complexity of Sorting $\lambda$-Permutations by $\lambda$-Operations

Next, we show an NP-Hardness proof for the sorting distance problem considering some rearrangement models. For this purpose, we define the following decision problems:

• Sorting $\lambda$-Permutations by $\lambda$-Operations: given a positive integer $\lambda$, a rearrangement model $\mathcal{M}$ containing only $\lambda$-operations, a $\lambda$-permutation $\pi$, and a non-negative integer k, decide if it is possible to sort $\pi$ using, at most, k operations that belong to $\mathcal{M}$.
• Sorting Permutations by Rearrangements: given a rearrangement model $\mathcal{M}$, a permutation $\pi$, and a non-negative integer k, decide if it possible to sort $\pi$ using, at most, k operations that belong to $\mathcal{M}$.

When $\lambda =n$, the problems of Sorting $\lambda$-Permutations by $\lambda$-Operations are NP-Hard (except for signed reversals), since they are equivalent to the sorting problems without restrictions in the size of operations. Next, we show that the problem is NP-Hard for a wide range of $\lambda$ values. When the rearrangement model is clear from the context, it is omitted from the instance.

Theorem 1.

The problem of Sorting λ-Permutations by λ-Operations is NP-Hard when $\lambda =c{n}^d$, for positive constants c and $0<d\le 1$, considering unsigned reversals, transpositions, transpositions and unsigned reversals, and transpositions and signed reversals.

Proof. 

Consider the model containing only unsigned reversals. The problem of Sorting Permutations by Unsigned Reversals is NP-Hard [2]. Now, we show a reduction from this problem to the problem of Sorting $\lambda$-Permutations by Unsigned $\lambda$-Reversals when $\lambda =c{n}^d$, for positive constants c and $0<d\le 1$.

Given an instance $(\pi ,k)$, where $\pi$ has size n, for Sorting Permutations by Unsigned Reversals, we create an instance $(\lambda ,\mathcal{M},{\pi }^{\prime },k)$, where $\lambda =n$, $\mathcal{M}$ is a model with unsigned $\lambda$-reversals, and ${\pi }^{\prime }=({\pi }_1{\pi }_2\dots {\pi }_n(n+1)\dots n^{\prime })$, such that $\lambda =n=c{n}^{\prime d}$, which is a $\lambda$-permutation. We note that, since c and d are constants, this is a polynomial-time reduction.

Now, we show that the instance $(\pi ,k)$ is satisfied for Sorting Permutations by Unsigned Reversals iff $d_r^{\lambda }\left({\pi }^{\prime }\right)\le k$.

(⇒) Suppose that there exists a sorting sequence S of reversals for $\pi$ with k reversals or less. Note that $\pi$ has size n, and all reversals in S are $\lambda$-reversals, since $\lambda =n$. The sequence S can sort the $\lambda$-permutation ${\pi }^{\prime }$; therefore, $d_r^{\lambda }\left({\pi }^{\prime }\right)\le k$.

(⇐) Suppose that there exists a sorting sequence $S^{\prime }$ of $\lambda$-reversals for ${\pi }^{\prime }$ with k operations or less. We now construct a sorting sequence S for $\pi$ with k or less reversals. If all operations of $S^{\prime }$ affect only elements between the positions 1 and n of ${\pi }^{\prime }$, then $S=S^{\prime }$ is also a sorting sequence for $\pi$. Otherwise, there exists operations in $S^{\prime }$ which affect the elements in the interval $[n+1,n^{\prime }]$. Let $S^{\prime }={\rho }_1^{\prime },{\rho }_2^{\prime },\dots ,{\rho }_{\ell }^{\prime }$, where ℓ is the length of $S^{\prime }$. We construct $S={\rho }_1,{\rho }_2,\dots ,{\rho }_{\ell }$, where ${\rho }_i$ starts at the first element of ${\rho }_i^{\prime }$, from left to right, which is in $\pi$, and it ends at the last element of ${\rho }_i^{\prime }$ which is in $\pi$. Since S inverts the elements of $\pi$ in the same order as they are inverted in ${\pi }^{\prime }$ by $S^{\prime }$, this sequence sorts $\pi$. Note that the length of S is less than or equal to ℓ because $S^{\prime }$ may have reversals which do not affect elements that are in $\pi$, which corresponds to an empty reversal in S that can be ignored.

The proof is analogous for the other three models. □

2.2. Inversions

An inversion is defined as a pair of elements $({\pi }_i,{\pi }_j)$ such that $i<j$ and $|{\pi }_i|>|{\pi }_j|$. The number of inversions in $\pi$ is denoted by $\mathrm{Inv}\left(\pi \right)$.

For example, the permutation $\pi =\left(15432\right)$ has 6 inversions. The 3-reversal $\rho (3,5)$ transforms $\pi$ into ${\pi }^{\prime }=\left(15234\right)$ that has 3 inversions.

Lemma 1.

For all λ-permutations $\pi \ne \iota$ and all $\lambda \ge 2$, we have $d_r^{\lambda }\left(\pi \right)\ge \frac{\mathrm{Inv}\left(\pi \right)}{\lambda (\lambda -1)/2}$, $d_t^{\lambda }\left(\pi \right)\ge \frac{\mathrm{Inv}\left(\pi \right)}{{\lambda }^2/4}$, and $d_{rt}^{\lambda }\left(\pi \right)\ge \frac{\mathrm{Inv}\left(\pi \right)}{\lambda (\lambda -1)/2}$.

Proof. 

A $\lambda$-reversal of length k can only change the inversions between elements of the segment affected by it. Therefore, the maximum number of inversions that a reversal of length k can remove is equal to $\left(\genfrac{}{}{0pt}{}{k}{2}\right)$, since this is the maximum number of inversions between the elements of a segment of length k. By definition, the length of a $\lambda$-reversal is less than or equal to $\lambda$, so a $\lambda$-reversal can remove, at most, $\left(\genfrac{}{}{0pt}{}{\lambda }{2}\right)$ inversions. Since the identity permutation is the only one with $\mathrm{Inv}\left(\pi \right)=0$, any sorting sequence has to remove all inversions of the permutation, which results in the lower bound $d_r^{\lambda }\left(\pi \right)\ge \frac{\mathrm{Inv}\left(\pi \right)}{\lambda (\lambda -1)/2}$.

A $\lambda$-transposition $\tau (i,j,k)$ of length $k^{\prime }$ also affects only the inversions between elements affected by it. Moreover, the inversions between elements on the segment ${\pi }_i,\dots ,{\pi }_{j-1}$ are not changed. The same is valid for inversions between elements of the segment ${\pi }_j,\dots ,{\pi }_{k-1}$. So, if an inversion $({\pi }_x,{\pi }_y)$, with $x<y$, is removed, then ${\pi }_x$ is in ${\pi }_i,\dots ,{\pi }_{j-1}$ and ${\pi }_y$ is in ${\pi }_j,\dots ,{\pi }_{k-1}$. Therefore, the maximum number of inversions that a transposition can remove is equal to $(j-i)(k-j)\le {(k^{\prime }/2)}^2$, since $(j-i)+(k-j)=k^{\prime }$. This bound is maximum when $k^{\prime }=\lambda$, which results in ${\lambda }^2/4$. As before, this results in the lower bound $d_t^{\lambda }\left(\pi \right)\ge \frac{\mathrm{Inv}\left(\pi \right)}{{\lambda }^2/4}$.

Using a similar argument, we have $d_{rt}^{\lambda }\left(\pi \right)\ge \frac{\mathrm{Inv}\left(\pi \right)}{\lambda (\lambda -1)/2}$. □

2.3. Breakpoints

An unsigned reversal breakpoint is defined as a pair of elements $({\pi }_i,{\pi }_{i+1})$ such that $|{\pi }_{i+1}-{\pi }_i|\ne 1$, for all $0\le i\le n$, in the problems of Sorting Unsigned $\lambda$-Permutations by $\lambda$-Reversals and Sorting Unsigned $\lambda$-Permutations by $\lambda$-Reversals and $\lambda$-Transpositions. A transposition breakpoint or signed reversal breakpoint is defined as a pair of elements $({\pi }_i,{\pi }_{i+1})$ such that ${\pi }_{i+1}-{\pi }_i\ne 1$, for all $0\le i\le n$, in the problems of Sorting Unsigned $\lambda$-Permutations by Transpositions, Sorting Signed $\lambda$-Permutations by $\lambda$-Reversals, and Sorting Signed $\lambda$-Permutations by $\lambda$-Reversals and $\lambda$-Transpositions. Considering a specific type of breakpoint, the number of breakpoints in $\pi$ is denoted by $b\left(\pi \right)$.

Fact 1.

[21,22] For all λ-permutations $\pi \ne \iota$ and all $\lambda \ge 2$, we have $d_r^{\lambda }\left(\pi \right)\ge \frac{b\left(\pi \right)}{2}$, $d_t^{\lambda }\left(\pi \right)\ge \frac{b\left(\pi \right)}{3}$, $d_{rt}^{\lambda }\left(\pi \right)\ge \frac{b\left(\pi \right)}{3}$, $d_{\overline{r}}^{\lambda }\left(\pi \right)\ge \frac{b\left(\pi \right)}{2}$, and $d_{\overline{r}t}^{\lambda }\left(\pi \right)\ge \frac{b\left(\pi \right)}{3}$.

2.4. Strips

A maximal subsequence $({\pi }_i{\pi }_{i+1}\dots {\pi }_j)$ without any breakpoints $({\pi }_k,{\pi }_{k+1})$, for all $i\le k<j$, is called a strip.

For the problems of sorting unsigned $\lambda$-permutations, if the strip’s elements are in ascending (resp. descending) order, then we call it an increasing (resp. decreasing) strip. Strips containing only one element are considered to be increasing ones. For example, considering sorting unsigned $\lambda$-permutations by both operations and $\pi =\left(645321\right)$, we have two increasing strips $\left(6\right)$ and $\left(45\right)$, and a decreasing strip $\left(321\right)$. Note, however, that segment $\left(321\right)$ is not a decreasing strip for the problem of Sorting $\lambda$-Permutations by $\lambda$-Transpositions. This is because, direct from the definition of strips and breakpoints, there are no decreasing strips when this problem is being considered.

For the problems of sorting signed $\lambda$-permutations, if the strip’s elements are positive, then we call it an increasing strip. Otherwise, the strip is called a decreasing strip. Strips containing only one element are considered to be increasing ones if such an element is positive. Otherwise, they are considered to be decreasing strips. For example, considering sorting signed $\lambda$-permutations and $\pi =(+6-5-4+1+2-3)$, we have two increasing strips, $(+6)$ and $(+1+2)$, and two decreasing strips, $(-5-4)$ and $(-3)$. Note that, despite the elements of strip $(-5-4)$ are in ascending order, it still is a decreasing strip, according to our definition.

The number of elements in a strip S of a $\lambda$-permutation $\pi$ is denoted by $\left|S\right|$. We say that an element ${\pi }_i$ is out-of-place if $|{\pi }_i|\ne i$.

Lemma 2.

Let π be a λ-permutation, and let $|{\pi }_j|=i$ be the smallest element out-of-place in π (i.e., $|{\pi }_j|$ is minimum and ${\pi }_j\ne j$). The strip S that contains ${\pi }_j$ is such that $\left|S\right|\le \lambda -1$.

Proof. 

First, suppose we have the increasing strip $S=({\pi }_j\dots {\pi }_k)$. Let $R=({\pi }_i\dots {\pi }_{j-1})$ be the segment of elements to the left of S. Note that the absolute value of any element in R is greater than any element in S. Therefore, $|{\pi }_i|\ge |{\pi }_k|+1=|{\pi }_j|+k-j+1=i+|S|$, and then $\left|S\right|\le |{\pi }_i|-i<\lambda$.

When we have ${\pi }_j$ in a decreasing strip, the proof is analogous. □

3. Inversions-Based Approximation Algorithms for Unsigned Permutations

In this section, we present approximation algorithms based on the concept of inversions for the sorting unsigned $\lambda$-permutations problems we are addressing.

The next lemma shows that it is always possible to remove at least one inversion from a $\lambda$-permutation by applying one $\lambda$-operation which results in a $\lambda$-permutation.

Lemma 3.

For any λ-permutation $\pi \ne \iota$, we can apply a 2-reversal or a 2-transposition to obtain a λ-permutation with $\mathrm{Inv}\left(\pi \right)-1$ inversions.

Proof. 

Let ${\pi }_j=i$ be the smallest element out-of-place in $\pi$. Initially, note we have inversion $({\pi }_{j-1},{\pi }_j)$, since ${\pi }_{j-1}>{\pi }_j$ and $j-1<j$. Let $\sigma$ be a 2-operation that swaps elements ${\pi }_{j-1}$ and ${\pi }_j$, and let ${\pi }^{\prime }=\pi ·\sigma$. It is easy to see that $\mathrm{Inv}\left({\pi }^{\prime }\right)=\mathrm{Inv}\left(\pi \right)-1$, since such inversion was removed, and note that there always exists a $\lambda$-reversal or a $\lambda$-transposition equivalent to $\sigma$, because the elements are adjacent, and, so, both only swap two elements.

Observe that, in ${\pi }^{\prime }$, element ${\pi }_j$ is closer to its correct position, since it was moved to the left. Hence, we follow by showing that ${\pi }^{\prime }$ is a $\lambda$-permutation by considering two cases according to the values of ${\pi }_{j-1}={\pi }_j^{\prime }$.

If ${\pi }_{j-1}\ge j$, then ${\pi }_{j-1}$ is also closer to its correct position, in ${\pi }^{\prime }$. Otherwise, ${\pi }_{j-1}<j$. Thus, element ${\pi }_{j-1}$ will be, in ${\pi }^{\prime }$, one position away from its correct position. Then, note that $|j-{\pi }_j|+1=(j-i)+1\le \lambda$ because $\pi$ is a $\lambda$-permutation. In addition, observe that we have $|j-{\pi }_j^{\prime }|=j-{\pi }_j^{\prime }$ because ${\pi }_j^{\prime }={\pi }_{j-1}<j$, and $j-{\pi }_j^{\prime }<j-i$ because ${\pi }_j^{\prime }>i$, and, so, $j-i\le \lambda -1$. Therefore, ${\pi }^{\prime }$ is a $\lambda$-permutation, and the result follows. □

A generic greedy approximation algorithm for the three problems we are addressing in this section is presented in the next theorem. It receives an integer $\lambda \ge 2$ and a $\lambda$-permutation $\pi \ne \iota$ as input. It is greedy because it always tries to decrease the largest amount of inversions in $\pi$. Since an unsorted permutation always contains inversions, the algorithm will finally sort $\pi$.

Theorem 2.

There exist $O\left({\lambda }^2\right)$-approximation algorithms for the problems of Sorting Unsigned λ-Permutations by λ-Reversals, by λ-Transpositions, and by λ-Reversals and λ-Transpositions.

Proof. 

Let $\lambda \ge 2$ be an integer, and let $\pi \ne \iota$ be a $\lambda$-permutation. Consider an algorithm which chooses a $\lambda$-operation $\sigma$, such that $\pi ·\sigma$ is a $\lambda$-permutation and $\mathrm{Inv}(\pi ·\sigma )$ is as small as possible, and then it applies such operation over $\pi$. The algorithm repeats the same process over the resulting permutation until it reaches the identity permutation.

In the worst case, we always have one $\lambda$-operation reducing the number of inversions by one unit, as shown in Lemma 3. Therefore, the number of operations of such greedy algorithm is, at most, $\mathrm{Inv}\left(\pi \right)$, and the approximation factor follows immediately from Lemma 1. □

Note that the distance is $O\left(n^2\right)$ because any unsigned permutation can be sorted with $O\left(n^2\right)$ $\lambda$-reversals or $\lambda$-transpositions. For Sorting Unsigned Permutations by $\lambda$-Reversals, at each step the algorithm considers $O\left({\lambda }^2\right)$ possible reversals that can be chosen. Since the variation in the number of inversions caused by an operation can be calculated in $O\left(\lambda \sqrt{log\lambda }\right)$ time [23], the algorithm has total time complexity $O\left(n^2{\lambda }^3\sqrt{log\lambda }\right)$. Using the same analysis, we conclude that the algorithms involving transpositions have total time complexity $O\left(n^2{\lambda }^4\sqrt{log\lambda }\right)$.

4. Algorithms Based on Inversions and Entropy for Signed $\lambda$-Permutations

The entropy of an element ${\pi }_i$ from a permutation $\pi$ is given by $\mathrm{ent}\left({\pi }_i\right)=\left|\right|{\pi }_i|-i|$, that is, the distance between ${\pi }_i$ and its position in $\iota$. We denote by $E_{\pi }^{eve{n}^{-}}$ the set of negative elements in $\pi$ such that $\mathrm{ent}\left({\pi }_i\right)$ is even, for all $1\le i\le n$. Similarly, we denote by $E_{\pi }^{od{d}^{+}}$ the set of positive elements in $\pi$ such that $\mathrm{ent}\left({\pi }_i\right)$ is odd. For example, given $\pi =(-4+3-1-2+5)$, we have $E_{\pi }^{eve{n}^{-}}=\{-1,-2\}$ and $E_{\pi }^{od{d}^{+}}=\{+3\}$, since $-1$ and $-2$ are negative elements with even entropy $\left(\mathrm{ent}\right(-1)=\mathrm{ent}(-2)=2)$, and $+3$ is a positive element with odd entropy $\left(\mathrm{ent}\right(+3)=1)$, respectively.

Fact 2.

[16] Let π be a signed permutation, and let σ be a 2-reversal. We have $|E_{\pi }^{eve{n}^{-}}|+|E_{\pi }^{od{d}^{+}}|=|E_{\pi ·\sigma }^{eve{n}^{-}}|+|E_{\pi ·\sigma }^{od{d}^{+}}|$.

Fact 3.

[24] Let π be a signed permutation, and let σ be a λ-operation. We have $\left(\right|E_{\pi }^{eve{n}^{-}}|$$+|E_{\pi }^{od{d}^{+}}\left|\right)-\left(\right|E_{\pi ·\sigma }^{eve{n}^{-}}|+|E_{\pi ·\sigma }^{od{d}^{+}}\left|\right)\le \lambda$.

The score of a $\lambda$-operation $\sigma$ over a signed permutation $\pi$ is given by $\mathrm{score}(\pi ,\sigma )=(\mathrm{Inv}\left(\pi \right)+|E_{\pi }^{eve{n}^{-}}|+|E_{\pi }^{od{d}^{+}}\left|\right)-\left(\right|\mathrm{Inv}(\pi ·\sigma )|+|E_{\pi ·\sigma }^{eve{n}^{-}}|+|E_{\pi ·\sigma }^{od{d}^{+}}\left|\right)$.

Combining Fact 3 with the fact that a $\lambda$-reversal and a $\lambda$-transposition can remove, at most, $\frac{\lambda (\lambda -1)}{2}$ inversions, we have an upper bound for the score of a permutation in Lemma 4. This upper bound implies Corollary 1.

Lemma 4.

Let π be a signed permutation. We have $\mathrm{score}(\pi ,\sigma )\le \lambda (\lambda -1)/2+\lambda$.

Corollary 1.

For any signed λ-permutation $\pi \ne \iota$, $\lambda \ge 2$, and $\beta \in \{\overline{r},\overline{r}t\}$, we have $d_{\beta }^{\lambda }\left(\pi \right)\ge \frac{\mathrm{Inv}\left(\pi \right)+|E_{\pi }^{eve{n}^{-}}|+|E_{\pi }^{od{d}^{+}}|}{\lambda (\lambda -1)/2+\lambda }$.

We follow by showing in Lemma 5 that there always exists a $\lambda$-operation with score at least 1. Having this in mind, a generic greedy approximation algorithm for the two sorting signed permutations problems we are addressing is presented in next theorem. It receives an integer $\lambda \ge 2$ and a $\lambda$-permutation $\pi \ne \iota$ as input. It is greedy because it always chooses a $\lambda$-operation with the largest score. Since the only permutation with $\mathrm{Inv}\left(\pi \right)=|E_{\pi }^{eve{n}^{-}}|=|E_{\pi }^{od{d}^{+}}|=0$ is the identity, it will, eventually, sort $\pi$.

Lemma 5.

For any signed permutation $\pi \ne \iota$ and $\lambda \ge 2$, there always exists a λ-operation σ such that $\pi ·\sigma$ is a λ-permutation and $\mathrm{score}(\pi ,\sigma )\ge 1$.

Proof. 

The proof is divided into two cases, according to $\mathrm{Inv}\left(\pi \right)$.

First, consider $\mathrm{Inv}\left(\pi \right)=0$. Note that, in this case, we only have zero entropy elements in $\pi$, implying that $|E_{\pi }^{od{d}^{+}}|=0$. So, by applying an unitary $\lambda$-reversal $\sigma$ over a negative element, we get a $\lambda$-permutation $\pi ·\sigma$ such that $|E_{\pi ·\sigma }^{eve{n}^{-}}|=|E_{\pi }^{eve{n}^{-}}|-1$. Since such an operation holds $\mathrm{Inv}(\pi ·\sigma )=|E_{\pi ·\sigma }^{od{d}^{+}}|=0$, we have $\mathrm{score}(\pi ,\sigma )=1$.

For $\mathrm{Inv}\left(\pi \right)>0$, Lemma 3 shows how to decrease the amount of inversions by applying one 2-reversal $\sigma$ and, since Fact 2 shows that $\left(\right|E_{\pi }^{eve{n}^{-}}|+|E_{\pi }^{od{d}^{+}}\left|\right)=\left(\right|E_{\pi ·\sigma }^{eve{n}^{-}}|+|E_{\pi ·\sigma }^{od{d}^{+}}\left|\right)$, we have $\mathrm{score}(\pi ,\sigma )=1$.

Note that, in both cases, the resulting permutation is also a $\lambda$-permutation. □

Theorem 3.

There exist $(\frac{\lambda (\lambda -1)}{2}+\lambda )$-approximation algorithms for the problems of Sorting Signed λ-Permutations by λ-Reversals and Sorting Signed λ-Permutations by λ-Reversals and λ-Transpositions.

Proof. 

Let $\lambda \ge 2$ be an integer, and let $\pi \ne \iota$ be a $\lambda$-permutation. Consider an algorithm which chooses the $\lambda$-operation $\sigma$ such that $\pi ·\sigma$ is a $\lambda$-permutation and $\mathrm{score}(\pi ·\sigma )$ is as great as possible and then it applies such operation over $\pi$. The algorithm repeats the same process in the resulting permutation until it reaches the identity permutation.

In the worst case, as shown in Lemma 5, we always have one $\lambda$-reversal with score 1. Therefore, the number of operations of such greedy algorithm is, at most, $\mathrm{Inv}\left(\pi \right)+|E_{\pi }^{eve{n}^{-}}|+|E_{\pi }^{od{d}^{+}}|$, and the approximation factor follows immediately from Corollary 1. □

Since $\mathrm{Inv}\left(\pi \right)+|E_{\pi }^{eve{n}^{-}}|+|E_{\pi }^{od{d}^{+}}|$ is $O\left(n^2\right)$ and the time to calculate the variation in the number of $|E_{\pi }^{eve{n}^{-}}|+|E_{\pi }^{od{d}^{+}}|$ is $O\left(\lambda \right)$, the analysis of time complexity is analogous to the algorithms previously presented for the sorting unsigned permutation problems.

5. Breakpoints-Based Approximation Algorithms

In this section, we present approximation algorithms based on the concept of breakpoints for the five problems we are addressing.

In the next lemma, we suppose that the smallest element out-of-place is in an increasing strip of a $\lambda$-permutation $\pi \ne \iota$. We show how to reduce the number of breakpoints of $\pi$ by moving this strip to its correct position using an operation that may not be a $\lambda$-operation, but assuring that the resulting permutation is also a $\lambda$-permutation.

Lemma 6.

Let π be a λ-permutation. Let $|{\pi }_j|=i$ be the smallest element out-of-place in π. Suppose that ${\pi }_j$ is in an increasing strip $S=({\pi }_j\dots {\pi }_k)$. Then, $\pi ·\tau (i,j,k+1)$ is a λ-permutation, $b(\pi ·\tau (i,j,k+1\left)\right)\le b\left(\pi \right)-1$, and $(k+1-i)\le 2(\lambda -1)$.

Proof. 

Let $R=({\pi }_i\dots {\pi }_{j-1})$ be the segment of elements in $\pi$ that will be transposed with S. Observe that the absolute value of any element in R is greater than any element in S, so $\pi ·\tau (i,j,k+1)$ is a $\lambda$-permutation, since greater elements (in their absolute values) are moved to the right and smaller elements to the left. In addition, observe that, in $\pi$, we have the three breakpoints $({\pi }_{i-1},{\pi }_i)$, $({\pi }_j,{\pi }_{j+1})$, and $({\pi }_{k-1},{\pi }_k)$, where the first one is because ${\pi }_{i-1}={\pi }_j-1=i-1$ and $|{\pi }_i|>i={\pi }_j$, and the second and third ones are because the strip’s start and strip’s end are at positions j and k, respectively. Transposition $\tau (i,j,k+1)$ moves the elements of S to their correct positions by transposing them with elements of R, thus removing at least breakpoint $({\pi }_{i-1},{\pi }_i)$. Since a transposition can add, at most, three breakpoints, but we already had all of them and we removed at least $({\pi }_{i-1},{\pi }_i)$, we have $b(\pi ·\tau (i,j,k+1\left)\right)\le b\left(\pi \right)-1$.

By Lemma 2, we have $\left|S\right|\le \lambda -1$; thus, $k+1-j\le \lambda -1$. Since $\pi$ is a $\lambda$-permutation, we have $\left|\right|{\pi }_j|-j|\le \lambda -1$, and, by construction, ${\pi }_j=i$; thus, $|i-j|+1=j-i+1\le \lambda -1$. Therefore, $k+1-i\le 2(\lambda -1)$. □

For a $\lambda$-permutation $\pi$ with only increasing strips, the next lemma shows that it is possible to find a sequence with, at most, 4 transpositions that decreases the number of breakpoints in $\pi$, assuring that all permutations generated in the process are $\lambda$-permutations. Using these operations, we can create an algorithm that sorts $\pi$ using, at most, $4b\left(\pi \right)$$\lambda$-transpositions.

Lemma 7.

Let π be a λ-permutation. Let $|{\pi }_j|=i$ be the smallest element out-of-place in π. Suppose that ${\pi }_j$ is in an increasing strip $S=({\pi }_j\dots {\pi }_k)$. It is always possible to obtain a λ-permutation $\pi ·\tau (i,j,k+1)$ with, at most, $b\left(\pi \right)-1$ breakpoints by applying, at most, 4 λ-transpositions such that all intermediary permutations are λ-permutations.

Proof. 

Let $R=({\pi }_i\dots {\pi }_{j-1})$ be the segment that will be moved to the right in $\tau (i,j,k+1)$. Note that $\left|S\right|\le \lambda -1$, by Lemma 2, and $\left|R\right|\le \lambda -1$, because $\pi$ is a $\lambda$-permutation.

The idea is to apply a sequence with, at most, four $\lambda$-transpositions that divide both segments $R=({\pi }_i\dots {\pi }_{j-1})$ and $S=({\pi }_j\dots {\pi }_k)$ into, at most, two parts each, where each part has, at most, $\lambda /2$ elements, and then exchange each part of S, at most, twice (and at least once), with the (possible) two parts of R. If we had exactly $\lambda -1$ elements in each of S and R, such sequence would be $\tau (i+\lambda /2,j,j+\lambda /2),\tau (i,i+\lambda /2,j),\tau (j,j+\lambda /2,k+1),\tau (i+\lambda /2,j,j+\lambda /2)$.

Now, we have to show that, after each of the, at most, four operations is applied, we have a $\lambda$-permutation as result.

Observe that the absolute value of any element in R is greater than any element in S. Since each $\lambda$-transposition puts elements of S closer to their correct positions by transposing them with greater elements (in their absolute values) of R, we have a $\lambda$-permutation after each $\lambda$-operation applied. After all $\lambda$-transpositions are applied, the elements of S are at positions from i to $i+k-j$, and the elements of R are at positions from $i+k-j+1$ to k, resulting in $\pi ·\tau (i,j,k+1)$, which is a $\lambda$-permutation with at least $b\left(\pi \right)-1$ breakpoints, as shown in Lemma 6. □

For a $\lambda$-permutation $\pi$ with only increasing strips, the next lemma shows how to decrease the number of breakpoints in $\pi$ using only $\lambda$-reversals, also assuring that all permutations generated in the process are $\lambda$-permutations.

Lemma 8.

Let π be a λ-permutation. Let $|{\pi }_j|=i$ be the smallest element out-of-place in π. Suppose that π only has increasing strips and that ${\pi }_j$ is in a strip $S=({\pi }_j\dots {\pi }_k)$. It is always possible to obtain a λ-permutation $\pi ·\tau (i,j,k+1)$ with, at most, $b\left(\pi \right)-1$ breakpoints by applying, at most, $5+\lambda -1$λ-reversals such that all intermediary permutations are λ-permutations.

Proof. 

Let $R=({\pi }_i\dots {\pi }_{j-1})$ be the segment that will be moved to the right in $\tau (i,j,k+1)$. Note that $\left|S\right|\le \lambda -1$, by Lemma 2, and $\left|R\right|\le \lambda -1$, because $\pi$ is a $\lambda$-permutation.

The idea is to move elements from S to their correct positions by applying, at most, two sequences of pairs of $\lambda$-reversals, where each one puts, at most, $\lambda /2$ elements of S in their correct positions at a time.

In the first sequence of $\lambda$-reversals, there are two possibilities. If $\left|S\right|\le \lambda /2$, then the first operation of each pair reverses $\left|S\right|$ elements contained in both S and R. If $\left|S\right|>\lambda /2$, then it reverses $\lambda /2$ elements contained in both S and R. In any case, the second operation of each pair reverses back the elements of R affected by the first one, in order to leave $\pi$ with only increasing strips again (except for the elements of S which were affected by the first operation).

After the sequence is applied, we have, at most, $\lambda /2$ elements of S from positions i to $i+min(\lambda /2,|S\left|\right)$, and, maybe, they are in a decreasing strip. If this is the case, then one more $\lambda$-reversal has to be applied to put these elements in their correct places, by reversing such decreasing strip.

The second sequence of $\lambda$-reversals puts the (at most) $\lambda /2$ remaining elements of S in their correct positions, following the same idea, and, also, maybe one extra $\lambda$-reversal will be necessary after it is applied. Note that, if there are no remaining elements (in case of $\left|S\right|\le \lambda /2$), this sequence is not necessary.

The largest amount of operations needed in the process described above happens when we have $\lambda /2+1$ elements in S. Since $\left|S\right|>\lambda /2$, our process starts by moving the first $\lambda /2$ elements of S to their correct positions. Observe that, for each pair of reversals applied in the first sequence, one of them moves $\lambda /2$ elements $\lambda /2$ positions to the left (except, maybe, by the last pair), and then the other one reverses again the elements of R affected by the first reversal. Besides that, by the definition of $\lambda$-permutations, the elements of S are, at most, $\lambda -1$ positions away from their correct positions, and, so, at most, 2 pairs of reversals are needed to put them at position i. As we have told before, maybe such elements of S ended up in reversed order and, in order to fix it, one more reversal is needed. Hence, we already have a total of, at most, 5 reversals applied.

To move the remaining element of S to its correct position, all the $\lambda$-reversals of the second sequence will have size 2 (note that, in this case, we do not need the second operation of each pair), which means such element will be moved only 1 position to the left per operation, giving an extra amount of $\lambda -1$$\lambda$-reversals. Therefore, the number of $\lambda$-reversals to move S to its correct position is, at most, $5+\lambda -1$.

Now, we have to show that, after applying each operation, we have a $\lambda$-permutation as result and, after the last operation is applied, we have $\pi ·\tau (i,j,k+1)$.

Observe that any element in R is greater than any element in S. Then, since the first operation of each pair moves elements of R to the right and elements of S to the left, all elements affected will be closer to their correct positions, resulting in a $\lambda$-permutation. The second operation of each pair reverses elements of R to ascending order again, so it also results in a $\lambda$-permutation. After both sequences of $\lambda$-reversals are applied, all elements of S are at positions from i to $i+k-j$ and all elements of R are at positions from $i+k-1$ to k, resulting in $\pi ·\tau (i,j,k+1)$, which is a $\lambda$-permutation with at least one less breakpoint than $\pi$, as shown in Lemma 6. □

Lemma 9 shows how to decrease the number of breakpoints of a $\lambda$-permutation $\pi$, considering that the smallest element out-of-place of $\pi$ is in a decreasing strip. Since Lemma 8 deals with the case where $\pi$ has no decreasing strips, we can use these two lemmas together to develop an algorithm to sort a $\lambda$-permutation $\pi$ using only $\lambda$-reversals.

Lemma 9.

Let $|{\pi }_k|=i$ be the smallest element out-of-place in a λ-permutation π. Suppose that ${\pi }_k$ is in a decreasing strip $S=({\pi }_j\dots {\pi }_k)$. It is always possible to obtain a λ-permutation with, at most, $b\left(\pi \right)-1$ breakpoints by applying, at most, one λ-transposition and one λ-reversal.

Proof. 

When $j=i$, one reversal $\rho (j,k)$ put elements of S in their correct positions. It is easy to see that $\pi ·\rho (j,k)$ is a $\lambda$-permutation and, since $\left|S\right|=k-j+1\le \lambda -1$ by Lemma 2, we have that $\rho (j,k)$ is a $\lambda$-reversal.

Now, assume $j>i$. Note that, in this case, we have the three breakpoints $({\pi }_{i-1},{\pi }_i)$, $({\pi }_j,{\pi }_{j+1})$, and $({\pi }_{k-1},{\pi }_k)$, where the first one is because ${\pi }_{i-1}=\left|{\pi }_k\right|-1=i-1$ and $|{\pi }_i|>i=|{\pi }_k|$, and the second and third ones are because the strip’s start and strip’s end are at positions k and j, respectively. Thus, we can apply the $\lambda$-transposition $\tau (i,j,k+1)$ followed by the $\lambda$-reversal $\rho (i,i+(k-j\left)\right)$ to obtain $b(\pi ·\tau (i,j,k+1)·\rho (i,i+(k-j)\left)\right)\le b\left(\pi \right)-1$, since a $\lambda$-transposition can add, at most, three breakpoints but we already had $({\pi }_{i-1},{\pi }_i)$, $({\pi }_{j-1},{\pi }_j)$, and $({\pi }_k,{\pi }_{k+1})$, and the second $\lambda$-reversal can add, at most, two breakpoints, but we already had $({\pi }_{i-1},{\pi }_j)$ and $({\pi }_k,{\pi }_i)$ and we removed the first one, since all elements of S will be in their correct positions in $\pi ·\tau (i,j,k+1)·\rho (i,i+(k-j\left)\right)$.

Now, we have to show that, after each operation is applied, we have a $\lambda$-permutation as result.

Let $R=({\pi }_i\dots {\pi }_{j-1})$ be the segment of elements that should be moved in order to put S in its correct position. Observe that the absolute value of any element in R is greater than any element in S. The first operation, a $\lambda$-transposition, transposes S only with greater elements (in their absolute values); thus, the result is a $\lambda$-permutation. The second operation, a $\lambda$-reversal, just reverses a decreasing strip to put the elements of S in their correct positions; thus, it also results in a $\lambda$-permutation. Hence, we have as result a $\lambda$-permutation with at least one less breakpoint. □

The next theorems describe approximation algorithms for the problems we are addressing. Lemma 10 is auxiliary to Theorem 4. The algorithms receive an integer $\lambda \ge 2$ and a $\lambda$-permutation $\pi \ne \iota$ as input. The goal is to decrease at least one unit on the number of breakpoints in $\pi$ by moving elements to their correct positions (applying Lemmas 7 and 9). Since the only permutation with no breakpoints is the identity, they will, eventually, sort $\pi$.

Lemma 10.

Let π be a λ-permutation. Let $S=(j\dots i)$ be a decreasing strip in π (thus, $i<j$). Let ${\pi }^{\prime }=\pi ·\rho ({\pi }_{\left|j\right|}^{-1},{\pi }_{\left|i\right|}^{-1})$ be the resulting permutation after reversing S in π. Then, ${\pi }^{\prime }$ is a λ-permutation.

Proof. 

First, note that element ${\pi }_j$ is to the right of element ${\pi }_i$. We show that the lemma follows by considering four cases, according to the positions of elements i and j in relation with the elements ${\pi }_{\left|i\right|}$ and ${\pi }_{\left|j\right|}$.

Case (i), $\left|i\right|<\left|j\right|<{\pi }_{\left|j\right|}^{-1}<{\pi }_{\left|i\right|}^{-1}$: note that both ${\pi }_{\left|i\right|}$ and ${\pi }_{\left|j\right|}$ are to the left of S. Then, after reversing S, element i is closer to its correct position, while element j is moved away from its correct position. Despite this, the distance between ${\pi }_{\left|j\right|}$ and j in ${\pi }^{\prime }$ is smaller than the distance between ${\pi }_{\left|i\right|}$ and i in $\pi$, and, so, if $\pi$ is a $\lambda$-permutation, ${\pi }^{\prime }$ is also a $\lambda$-permutation.

Case (ii), $\left|i\right|<{\pi }_{\left|j\right|}^{-1}\le \left|j\right|<{\pi }_{\left|i\right|}^{-1}$: note that ${\pi }_{\left|i\right|}$ is to the left of S, and ${\pi }_{\left|j\right|}$ is in S. Then, after reversing S, the element i is closer to its correct position and the distance of j to its correct position will still be less than $\lambda$, since the size of S is, at most, $\lambda$, as Lemma 2 shows.

Case (iii), ${\pi }_{\left|j\right|}^{-1}\le \left|i\right|<{\pi }_{\left|i\right|}^{-1}\le \left|j\right|$: similar to (ii).

Case (iv), ${\pi }_{\left|j\right|}^{-1}<{\pi }_{\left|i\right|}^{-1}\le \left|i\right|<\left|j\right|$: similar to (i). □

Theorem 4.

The problems of Sorting (Unsigned or Signed) λ-Permutations by λ-Reversals have $(10+2\lambda )$-approximation algorithms.

Proof. 

Let $\lambda \ge 2$ be an integer and $\pi \ne \iota$ be a $\lambda$-permutation. Consider an algorithm which first applies one $\lambda$-reversal over each decreasing strip of $\pi$ in order to get a $\lambda$-permutation with only increasing strips. By Lemma 10, we guarantee that all intermediary permutations generated by these $\lambda$-reversals are $\lambda$-permutations.

Then, the algorithm will repeatedly take the smallest element out-of-place and move the increasing strip that contains it to its correct position, obtaining a $\lambda$-permutation with at least one less breakpoint, until it reaches the identity permutation.

As shown in Lemma 8, at most $5+\lambda -1$ $\lambda$-reversals are needed to move each strip to its correct position. Since, maybe, one extra $\lambda$-reversal could have been applied in the beginning of the algorithm to transform such strip into an increasing one, we have that, at most, $6+\lambda -1$$\lambda$-reversals can be applied to remove at least one breakpoint. Therefore, the number of operations of our algorithm is, at most,

$$(6+\lambda -1)b\left(\pi \right)\le 2(6+\lambda -1)d_{\beta }^{\lambda }\left(\pi \right)=(10+2\lambda )d_{\beta }^{\lambda }\left(\pi \right),$$

for $\beta \in \{r,\overline{r}\}$, and the inequality follows from Fact 1. □

Theorem 5.

The problem of Sorting λ-Permutations by λ-Transpositions has a 12-approximation algorithm.

Proof. 

Let $\lambda \ge 2$ be an integer, and let $\pi \ne \iota$ be a $\lambda$-permutation. The algorithm will repeatedly take the smallest element out-of-place and move the increasing strip that contains such element to its correct position, obtaining a $\lambda$-permutation with at least one less breakpoint, until it reaches the identity permutation.

As shown in Lemma 7, at most, 4 $\lambda$-transpositions are needed to move each strip to its correct position. Then, in the worst case, we remove 1 breakpoint every 4 $\lambda$-transpositions applied. With this and Fact 1, the number of operations of our algorithm is, at most, $4b\left(\pi \right)\le 12d_t^{\lambda }\left(\pi \right)$. □

Theorem 6.

The problems of Sorting (Unsigned or Signed) λ-Permutations by λ-Reversals and λ-Transpositions have 12-approximation algorithms.

Proof. 

Let $\lambda \ge 2$ be an integer, and let $\pi \ne \iota$ be a $\lambda$-permutation. Let ${\pi }_j=i$ be the smallest element out-of-place in $\pi$.

We have two cases to consider: when the strip which contains ${\pi }_j$ is decreasing or not. In both cases, we can at least remove breakpoint $({\pi }_{i-1},{\pi }_i)$ from $\pi$ without adding other ones by applying, at most, 4 $\lambda$-transpositions (if the strip is increasing) or, at most, 2 $\lambda$-operations (if the strip is decreasing), as shown in Lemmas 7 and 9, respectively.

Then, considering both cases described, the algorithm will repeatedly take the smallest element out-of-place and move the strip that contains it to its correct position, decreasing at least one breakpoint at a time, until it reaches the identity permutation.

Note that, in the worst case, we remove 1 breakpoint every 4 $\lambda$-transpositions, and, so, the result is analogous to Theorem 5. □

Note that $b\left(\pi \right)$ is $O\left(n\right)$ and the time complexity to find the strip with the smallest element out-of-place in $\pi$ is $O\left(n\right)$. So, we conclude that the time complexity for the $O\left(1\right)$-approximation algorithms and the $O\left(\lambda \right)$-approximation algorithm are $O\left(n\right(n+\lambda \left)\right)$ and $O\left(n(n+{\lambda }^2)\right)$, respectively.

6. Experimental Results

In order to analyze how the proposed algorithms work from a practical perspective, we have implemented the inversions-based (Theorems 2 and 3) and the breakpoints-based (Theorems 4–6) greedy algorithms.

We can also achieve an approximation factor of $O\left({\lambda }^2\right)$ with algorithms that always apply an operation of size 2 according to Lemma 3, for unsigned permutations, or Lemma 5, for signed permutations. There exists a way to implement such algorithms so that they have time complexity of $O(nlogn)$ [25]. We also implemented these algorithms, which we named super short algorithms, for comparison purposes. The difference between the super short algorithms and the inversions-based algorithms from Theorems 2 and 3 is that the super short algorithms only use operations of size 2, while the algorithms from Theorems 2 and 3 use, at each iteration, the operation that most decrease the number of inversions, which can have size, at most, $\lambda$.

We performed experiments considering a total of 1000 signed and unsigned $\lambda$-permutations, with size equal to 100 and values of $\lambda \in \{5,10,15,\dots ,100\}$, as input for the algorithms. The considered $\lambda$-permutations were generated in two different ways: (i) totally random, and (ii) by applying 20 random $\lambda$-operations (according to the rearrangement model of each problem) over the identity. We reinforce that all generated permutations in both cases, including the intermediary ones of case (ii), are $\lambda$-permutations. For (i), the $\lambda$-permutations tend to have a high amount of breakpoints, and for (ii) they tend to have a high amount of strips and, moreover, we know the distance is, at most, 20. Then, we compared the results according to the average and maximum approximation factors obtained for all permutations. For each permutation, we calculated the approximation factor by dividing the size of the sorting sequence by the maximum value of lower bound between the ones shown in Lemma 1 and Fact 1.

We show the results for totally random $\lambda$-permutations in Figure 1 and Figure 2, and for $\lambda$-permutations generated from the identity in Figure 3 and Figure 4.

Even though the inversions-based and the super short algorithms have the same theoretical approximation factor, the experiments show that the inversions-based algorithms are much better in practice. Hence, for the rest of this analysis, we only compare the results of the inversions-based and breakpoints-based algorithms. Considering the results for totally random $\lambda$-permutations, we observed that the maximum approximation factors for sorting unsigned $\lambda$-permutations problems were $5.38$ and $7.04$ for $\lambda$-reversals, $2.91$ and $3.06$ for $\lambda$-transpositions, and $3.00$ and $3.15$ for when both $\lambda$-operations are allowed, considering the breakpoints-based and the inversions-based algorithms, respectively. For the sorting signed $\lambda$-permutations problems, the maximum approximation factors were $7.78$ and $7.54$ for $\lambda$-reversals and $4.74$ and $5.21$ for when both $\lambda$-operations are allowed, considering the breakpoints-based and the inversions-based algorithms, respectively.

Another observation is that, for totally random $\lambda$-permutations, the average approximation factor of the inversions-based algorithm and the breakpoints-based algorithm were similar (except for Sorting Signed $\lambda$-Permutations by $\lambda$-Reversals), even with the relevant difference among their theoretical approximation factors.

Regarding the results for random $\lambda$-permutations generated from the identity, the maximum approximation factors for sorting unsigned $\lambda$-permutations problems were $6.08$ and $18.5$ for $\lambda$-reversals, $2.83$ and $2.64$ for $\lambda$-transpositions, and $4.33$ and $3.58$ for when both $\lambda$-operations are allowed, considering the breakpoints-based and the inversions-based algorithm, respectively. For the sorting signed $\lambda$-permutations problems, the maximum approximation factors were $7.13$ and $22.85$ for $\lambda$-reversals and $5.00$ and $11.56$ for when both $\lambda$-operations are allowed, considering the breakpoints-based and the inversions-based algorithm, respectively.

Furthermore, for this second type of $\lambda$-permutations, the maximum approximation factors of the inversions-based algorithm for the sorting signed $\lambda$-permutations problems and for the Sorting Unsigned $\lambda$-Permutations by $\lambda$-Reversals were considerably greater when compared with their average approximation factors. Despite that, the average and maximum factors given by the inversions-based algorithm were better for the two sorting unsigned $\lambda$-permutations problems which allow $\lambda$-transpositions. For both problems which allow only $\lambda$-reversals, the breakpoints-based algorithm had better average and maximum approximation factors. For Sorting Signed $\lambda$-Permutations by $\lambda$-Reversals and $\lambda$-Transpositions, both algorithms had similar average approximation factor, but the breakpoints-based algorithm had a better and more constant maximum approximation factor.

Our experiments reveal that the average approximation factor for the breakpoint-based algorithms slight increases for the interval $\lambda \in [30..100]$, while the average approximation for the inversion-based algorithms has a greater increase in the same interval. This occurred because there are more $\lambda$-reversals that decreases a breakpoint, when using bigger values of $\lambda$, since the strips tend to get smaller compared to the value of $\lambda$, which is a crucial point in Lemmas 8 and 9. A similar relation is not so common for inversions, since extending the segment to be inverted may lead to inversions being added.

7. Conclusions

In this work, we introduced the problems of Sorting $\lambda$-Permutations by $\lambda$-Operations, considering reversals and transpositions on signed and unsigned permutations.

We presented an NP-hardness proof for the models containing unsigned reversals, transpositions, and the combination of (signed or unsigned) reversals and transpositions, when $\lambda =c{n}^d$ for positive constants c and $0<d\le 1$. We developed algorithms with approximation factors of $O\left({\lambda }^2\right)$, $O\left(\lambda \right)$, and $O\left(1\right)$ for all problems studied. Besides that, experiments were also performed in order to see their performance on simulated data.

Table 1. Summary of the approximation results for the problems considering signed permutations. The columns “Approx.” and “Time” refer to the theoretical approximation factor and the worst-case complexity time, respectively.

	Reversals		Reversals and Transpositions
	Approx.	Time	Approx.	Time
Breakpoints-based	$10+2\lambda$	$O\left(n(n+{\lambda }^2)\right)$	12	$O\left(n\right(n+\lambda \left)\right)$
Inversions-based	$\frac{\lambda (\lambda -1)}{2}+\lambda$	$O\left(n^2{\lambda }^3\sqrt{log\lambda }\right)$	$\frac{\lambda (\lambda -1)}{2}+\lambda$	$O\left(n^2{\lambda }^4\sqrt{log\lambda }\right)$

and

Table 2. Summary of the approximation results for the problems considering unsigned permutations. The columns “Approx.” and “Time” refer to the theoretical approximation factor and the worst-case complexity time, respectively.

	Reversals		Transpositions		Reversals and Transpositions
	Approx.	Time	Approx.	Time	Approx.	Time
Breakpoints-based	$10+2\lambda$	$O\left(n(n+{\lambda }^2)\right)$	12	$O\left(n\right(n+\lambda \left)\right)$	12	$O\left(n\right(n+\lambda \left)\right)$
Inversions-based	$O\left({\lambda }^2\right)$	$O\left(n^2{\lambda }^3\sqrt{log\lambda }\right)$	$O\left({\lambda }^2\right)$	$O\left(n^2{\lambda }^4\sqrt{log\lambda }\right)$	$O\left({\lambda }^2\right)$	$O\left(n^2{\lambda }^4\sqrt{log\lambda }\right)$

summarize these results.

For future work, we intend to develop approximation algorithms with better approximation factors for the problems of Sorting $\lambda$-Permutations by $\lambda$-Operations. Another direction of future work is to study the complexity for the model containing only signed reversals and other values of $\lambda$.