###
Compressed Representations of Permutations, and Applications

####
Jérémy Barbay and Gonzalo Navarro

We explore various techniques to compress a permutation *p* over
*n* integers, taking advantage of ordered subsequences in *p*,
while supporting its application *p(i)* and the application of its
inverse *p^(-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 *p^k(i)* of
it, of integer functions, and of inverted lists and suffix arrays.