\right)}}$.

For this particular locating time we are sampling one out of $\log_\sigma n \lg\lg n$ text positions.

Compressing permutations {#sec:permutations}
========================

We now show how to use [$\mathsf{access}$]{}/[$\mathsf{rank}$]{}/[$\mathsf{select}$]{} data structures to store a compressed permutation. We follow Barbay and Navarro’s notation [@BN09] and improve their space and, especially, their time performance. They measure the compressibility of a permutation $\pi$ in terms of the entropy of the distribution of the lengths of [*runs*]{} of different kinds. Let $\pi$ be covered by $\rho$ runs (using any of the previous definitions of runs [@sortingShuffledMonotoneSequences; @BN09; @sortingPresortedFiles]) of lengths ${\ensuremath{\mathsf{runs}}}(\pi) = \langle n_1, \ldots, n_\rho\rangle$. Then $H({\ensuremath{\mathsf{runs}}}(\pi)) = \sum \frac{n_i}{n}\lg\frac{n}{n_i} \le
\lg\rho$ is called the [*entropy*]{} of the runs (and, because $n_i
\ge 1$, it also holds $nH({\ensuremath{\mathsf{runs}}}(\pi)) \ge (\rho-1)\lg n$). We first consider permutations which are interleaved sequences of increasing or decreasing values as first defined by Levcopoulos [[*et al.*]{}]{} [@sortingShuffledMonotoneSequences] for adaptive sorting, and later on for compression [@BN09], and then give improved results for more specific classes of runs. In both cases we consider first the application of the permutation $\pi()$ and its inverse, ${\ensuremath{\pi^{-1}}}()$, to show later how to extend the support to the iterated applications of the permutation, 