Succinct representations of permutations. (English) Zbl 1039.68546
Baeten, Jos C. M. (ed.) et al., Automata, languages and programming. 30th international colloquium, ICALP 2003, Eindhoven, The Netherland, June 30 – July 4, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40493-7/pbk). Lect. Notes Comput. Sci. 2719, 345-356 (2003).
Summary: We investigate the problem of succinctly representing an arbitrary permutation, \(\pi\), on \(\{0,\ldots,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. A representation taking the optimal \(\lceil{\lg n!}\rceil + o(n)\) bits can be used to compute arbitrary powers in \(O(\lg n / \lg\lg n)\) time, or indeed in a minimal \(O(\lg n)\) bit probes.
For the entire collection see [Zbl 1029.00041].
For the entire collection see [Zbl 1029.00041].
MSC:
| 68P05 | Data structures |
