# Approximation Algorithms for Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations
## 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 \(\operatorname{ent}(\pi_{i})=||\pi_{i}|-i|\), that is, the distance between \(\pi_{i}\) and its position in \(\iota\). We denote by \(E^{\text{even}^{-}}_{\pi}\) the set of negative elements in \(\pi\) such that \(\operatorname{ent}(\pi_{i})\) is even, for all \(1\leq i\leq n\). Similarly, we denote by \(E^{\text{odd}^{+}}_{\pi}\) the set of positive elements in \(\pi\) such that \(\operatorname{ent}(\pi_{i})\) is odd. For example, given \(\pi=(-4\,+3\,-1\,-2\,+5)\), we have \(E^{\text{even}^{-}}_{\pi}=\{-1,-2\}\) and \(E^{\text{odd}^{+}}_{\pi}=\{+3\}\), since \(-1\) and \(-2\) are negative elements with even entropy \((\operatorname{ent}(-1)=\operatorname{ent}(-2)=2)\), and \(+3\) is a positive element with odd entropy \((\operatorname{ent}(+3)=1)\), respectively. **Fact 2**. : _[_16_]_ _Let \(\pi\) be a signed permutation, and let \(\sigma\) be a 2-reversal. We have \(|E^{\text{even}^{-}}_{\pi}|+|E^{\text{odd}^{+}}_{\pi}|=|E^{\text{even}^{-}}_{\pi,\sigma}|+|E^{\text{odd}^{+}}_{\pi,\sigma}|\)._  
**Fact 3**. : _[_24_]_ _Let \(\pi\) be a signed permutation, and let \(\sigma\) be a \(\lambda\)-operation. We have \((|E_{\pi}^{\mathit{even}}|\)\(+|E_{\pi}^{\mathit{odd}^{+}}|)-(|E_{\pi\cdot\sigma}^{\mathit{even}}|+|E_{\pi \cdot\sigma}^{\mathit{odd}^{+}}|)\leq\lambda\)._  
The score of a \(\lambda\)-operation \(\sigma\) over a signed permutation \(\pi\) is given by \(\mathrm{score}(\pi,\sigma)=(\mathrm{Inv}(\pi)+|E_{\pi}^{\mathit{even}}|+|E_{ \pi}^{\mathit{odd}^{+}}|)-(|\mathrm{Inv}(\pi\cdot\sigma)|+|E_{\pi\cdot\sigma}^ {\mathit{even}}|+|E_{\pi\cdot\sigma}^{\mathit{odd}^{+}}|)\). 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 \(\pi\) be a signed permutation. We have \(\mathrm{score}(\pi,\sigma)\leq\lambda(\lambda-1)/2+\lambda\)._  
Corollary 1: _For any signed \(\lambda\)-permutation \(\pi\
eq\iota\), \(\lambda\geq 2\), and \(\beta\in\{\tau,\mathit{pt}\}\), we have \(d_{\beta}^{\lambda}(\pi)\geq\frac{\mathrm{Inv}(\pi)+|E_{\pi}^{\mathit{even}}| +|E_{\pi}^{\mathit{odd}^{+}}|}{\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\geq 2\) and a \(\lambda\)-permutation \(\pi\
eq\iota\) as input. It is greedy because it always chooses a \(\lambda\)-operation with the largest score. Since the only permutation with \(\mathrm{Inv}(\pi)=|E_{\pi}^{\mathit{even}}|=|E_{\pi}^{\mathit{odd}^{+}}|=0\) is the identity, it will, eventually, sort \(\pi\). Lemma 5: _For any signed permutation \(\pi\
eq\iota\) and \(\lambda\geq 2\), there always exists a \(\lambda\)-operation \(\sigma\) such that \(\pi\cdot\sigma\) is a \(\lambda\)-permutation and \(\mathrm{score}(\pi,\sigma)\geq 1\)._  
Proof: The proof is divided into two cases, according to \(\mathrm{Inv}(\pi)\). First, consider \(\mathrm{Inv}(\pi)=0\). Note that, in this case, we only have zero entropy elements in \(\pi\), implying that \(|E_{\pi}^{\mathit{odd}^{+}}|=0\). So, by applying an unitary \(\lambda\)-reversal \(\sigma\) over a negative element, we get a \(\lambda\)-permutation \(\pi\cdot\sigma\) such that \(|E_{\pi\cdot\sigma}^{\mathit{even}}|=|E_{\pi}^{\mathit{even}}|-1\). Since such an operation holds \(\mathrm{Inv}(\pi\cdot\sigma)=|E_{\pi\cdot\sigma}^{\mathit{odd}^{+}}|=0\), we have \(\mathrm{score}(\pi,\sigma)=1\).