Compressed Representations of Permutations, and Applications

Abstract

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.