  We explore various techniques to compress a permutation $\pi$ over n
integers, taking advantage of ordered subsequences in $\pi$, while supporting
its application $\pi$(i) and the application of its inverse $\pi^{-1}(i)$ in
small time. Our compression schemes yield several interesting byproducts, in
many cases matching, improving or extending the best existing results on
applications such as the encoding of a permutation in order to support iterated
applications $\pi^k(i)$ of it, of integer functions, and of inverted lists and
suffix arrays.
