Succinct Representations of Permutations and Functions

Details Succinct Representations of Permutations and Functions Succinct Representations of Permutations and Functions

2011-08-09

arxiv.org/abs/1108.1983v1

Computer Science

Data Structures and Algorithms

Preliminary versions of these results have appeared in the Proceedings of ICALP 2003 and 2004. However, all results in this ve

Scientific paper

We investigate the problem of succinctly representing an arbitrary permutation, \pi, on {0,...,n-1} so that \pi^k(i) can be computed quickly for any i and any (positive or negative) integer power k. A representation taking (1+\epsilon) n lg n + O(1) bits suffices to compute arbitrary powers in constant time, for any positive constant \epsilon <= 1. A representation taking the optimal \ceil{\lg n!} + o(n) bits can be used to compute arbitrary powers in O(lg n / lg lg n) time. We then consider the more general problem of succinctly representing an arbitrary function, f: [n] \rightarrow [n] so that f^k(i) can be computed quickly for any i and any integer power k. We give a representation that takes (1+\epsilon) n lg n + O(1) bits, for any positive constant \epsilon <= 1, and computes arbitrary positive powers in constant time. It can also be used to compute f^k(i), for any negative integer k, in optimal O(1+|f^k(i)|) time. We place emphasis on the redundancy, or the space beyond the information-theoretic lower bound that the data structure uses in order to support operations efficiently. A number of lower bounds have recently been shown on the redundancy of data structures. These lower bounds confirm the space-time optimality of some of our solutions. Furthermore, the redundancy of one of our structures "surpasses" a recent lower bound by Golynski [Golynski, SODA 2009], thus demonstrating the limitations of this lower bound.

Affiliated with

Also associated with

No associations

Rating

Succinct Representations of Permutations and Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Succinct Representations of Permutations and Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Succinct Representations of Permutations and Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-70600