We investigate the problem of succinctly representing an arbitrary unlabeled permutation π, so that π~k(i) can be computed quickly for any i and any integer power k. We consider the problem in several scenarios: 1. Labeling schemes where we assign labels to elements and the query is to be answered by just examining the labels of the queried elements: we show that a label space of Σ_(i=1)~n [n/i] · i is necessary and sufficient. In other words, 2 lg n bits of space are necessary and sufficient for representing each of the labels. 2. Succinct data structures for the problem where we assign labels to the n elements from the label set {1,...,cn} where c ≥ 1: we show that Θ({the square root of}n) bits are necessary and sufficient to represent the permutation. Moreover, we support queries in such a structure in O(1) time in the standard word-RAM model. 3. Succinct data structures for the problem where we assign labels to the n elements from the label set {1,...,cn~(1+ε)} where c is a constant and 0 < ∈ < 1: we show that Θ(n~((1-∈)/2)) bits are necessary and sufficient to represent the permutation. We can also support queries in such a structure in O(1) time in the standard word-RAM model.
展开▼
