# Memory-efficient list of N unique integers from 0..N-1 with fast lookup

We want to represent a list of $$n$$ unique integers between $$0$$ and $$n-1$$ in a memory-efficient way. The only operation we need to support is looking up the $$n\text{-th}$$ element.

What are some of the most compact data structures that can do the lookup in $$O(1)$$ or $$O(\log n)$$?

Naive example: an array of $$\log n$$-bit integers. ($$n \log{n}$$ bits)

Intuitively it seems that we can do better. If we didn't have the fast lookup requirement, the data structure could simply be a permutation index ($$⌈\log{n!}⌉ ≈ n \log{n} − 1.44n$$ bits).

• Well, having a search engine provide results for something like space efficient $\or$ saving storage $\or$ representation of permutations brings up results like J Ian Munro; Rajeev Raman; Venkatesh Raman; Srinivasa Rao Satti: Succinct Representations of Permutations and Functions in Theoretical Computer Science, 2011/08: $(1+\epsilon) n \lg n + O(1), 0 < \epsilon \le 1$ bits suffices to compute arbitrary powers in constant time, $\lceil{\lg n!}\rceil + o(n)$ bits allow $O(\lg n / \lg \lg n)$ time ($\log_2$ outside $O$?). Nov 9 '21 at 6:55
• (Venkatesh Raman is one of the authors of Brodnik, Andrej& al.: Space-Efficient Data Structures, Streams, and Algorithms, Springer 2013.)(arxiv.org seems to host a preprint of above paper: Succinct Representations of Permutations and Functions) Nov 9 '21 at 7:01
• Thanks greybeard! I'll read the paper to see if any of the representations described there improves over $n \log{n}$ (the theoretical lower bound being $⌈\log{n!}⌉ ≈ n \log{n} − 1.44n$ bits). Nov 9 '21 at 20:54

## 2 Answers

This is equivalent to storing a permutation of $$n$$ items in memory. There are in general, $$n!$$ ($$n$$ factorial) such permutations, and it is well known that $$\log(n!)=\Theta(n\log(n))$$. Hence, you will need at least $$\Omega(n\log(n))$$ bits to represent the permutations (which is what you get from the naive solution).

So without even the requirement about the lookup time, you are bound to have at least this much memory consumed - and sadly you cannot compress it further.

• The naive solution is exactly n log n bits. The information theoretic lower bound is ⌈log n!⌉ ≈ n log n − 1.44n. Nov 9 '21 at 20:51

The naive solution may be n log n bits. But for the first number you have n choices; you have n-1 choices for the second number, n-2 choices for the third number etc. So log(n!) bits, rounded up to the next integer, would be a possibility.

In practice, if you want the lookup to be fast, looking up number k should locate a range of bits that represent some numbers around k, like numbers k-3 to k+5, and then there should be some fixed number of operations to extract number k.

For example: Given n, pick t depending on n, so that $$n^t$$ is only slightly less than a power of two, say $$n^t < 2^m$$. We then arrange the numbers $$x_0$$ to $$x_{n-1}$$ in groups of t numbers, $$x_{k \cdot t}$$ to $$x_{k \cdot t + (t-1)}$$. Interpret these t numbers as digits of a t-digit base-n number with a value less than $$2^m$$. Store the bits for each of these numbers consecutively.

Given j, we let $$j = t \cdot k + r$$. We take bits number j to j+m-1, interpret them as an integer, write that integer in base n, and take the j-th base n digit as the result.