Compressed Representations of Permutations, and Applications
(Citations: 13)
We explore various techniques to compress a permutation overn integers, taking advantage of ordered subsequences in , while supporting its application (i) and the application of its inverse 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 k(i) of it, of integer functions, and of inverted lists and sux arrays.