# Approximation Algorithms for Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations
## 2 Preliminaries and Basic Facts  
We denote a signed permutation by \(\pi=(\pi_{1}\ \pi_{2}\ \ldots\ \pi_{n})\), where \(\pi_{i}\in\{-n,-(n-1),\ldots,-2,-1,+1,+2,\ldots,+(n-1),+n\}\) and \(|\pi_{i}|\
eq|\pi_{j}|\), for all \(1\leq i<j\leq 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\geq 2\) as input, we say that \(\pi\) is a _\(\lambda\)-permutation_ if we have \(||\pi_{i}|-i|<\lambda\) for all \(1\leq i\leq 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\cdot\sigma=(\alpha_{1}\ \alpha_{2}\ \ldots\ \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\cdot\pi^{-1}=(1\ 2\ \ldots\ 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\leq i<j\leq n\), and it transforms an unsigned permutation \(\pi=(\pi_{1}\ \pi_{2}\ \ldots\ \pi_{n})\) into \(\pi\cdot\rho(i,j)=(\pi_{1}\ \ldots\ \pi_{i-1}\ \pi_{j}\ \ldots\ \pi_{i}\ \pi_{j+1}\ \ldots\ \pi_{n})\). A _signed reversal_ is denoted by \(\bar{\rho}(i,j)\), with \(1\leq i\leq j\leq n\), and when applied on a signed permutation \(\pi=(\pi_{1}\ \pi_{2}\ \ldots\ \pi_{n})\), the resulting permutation is \(\pi\cdot\bar{\rho}(i,j)=(\pi_{1}\ \ldots\ \pi_{i-1}-\pi_{j}\ \ldots\ -\pi_{i}\ \pi_{j+1}\ \ldots\ \pi_{n-1}\ \pi_{n})\). The size of a (signed or unsigned) reversal is given by \(\overline{j-i+1}\). For example, given the signed permutation \(\pi=(-1\ -4\ +3\ -2\ +5)\), we have \(\pi\cdot\bar{\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 \(\rho(\overline{i},j)\) is a _\(\lambda\)-reversal_ if \(j-i+1\leq\lambda\).  
An operation of _transposition_ is denoted by \(\tau(i,j,k)\), with \(1\leq i<j<k\leq n+1\), and when applied on a (unsigned or signed) permutation \(\pi=(\pi_{1}\ \pi_{2}\ \ldots\ \pi_{n})\), the result is the permutation \(\pi\cdot\tau(i,j,k)=(\pi_{1}\ \pi_{2}\ \ldots\ \pi_{i-1}\ \pi_{j}\ \ldots\ \pi_{k-1}\ \pi_{i}\ \ldots\ \pi_{j-1}\ \pi_{k}\ \ldots\ \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\cdot\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 _\(\lambda\)-transposition_ if \(k-i\leq\lambda\).  
The goal of these problems is to transform a \(\lambda\)-permutation \(\pi\) into the _identity permutation_\(\iota=(1\ 2\ \ldots\ \ 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}(\pi)\), \(d_{t}^{\lambda}(\pi)\), and \(d_{rt}^{\lambda}(\pi)\) 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_{r}^{\lambda}(\pi)\) and \(d_{rt}^{\lambda}(\pi)\) the sorting distance for the sorting signed \(\lambda\)-permutation problems when we only have \(\lambda\)-reversals and when we have both operations, respectively.