# Efficient representation of a given surjective function $\{1 \ldots N\} \rightarrow \{1 \ldots M\}$ when $N \gg M$

More precisely: The input is set of $M$ sets (most likely stored sequentially on disk) that contain partitions of the set $\{1..N\}$. I want to efficiently (as far as memory and time complexity goes) represent this structure. Let's call this hypothetical structure $S$. I need the structure to support just a single function $p : S \times \{1 \ldots N\} \rightarrow \{1 \ldots M\}$.

It's also safe to assume that I will call this function in order, meaning I will be interested first in $p(S, 1)$, then in $p(S,2)$, etc.

I can represent this structure as an array of $N \times \lceil log_2(M)\rceil$ bits, but that seems too memory inefficient when $M$ is small and $N$ is in billions. I have a hunch that perfect-hashing might be of use here.

• Perfect hashing won't help you here; if the distribution of values in the codomain is flat and random (i.e. there are no correlations higher than zero-order), any perfect hash function which represents the function exactly must itself require at least $N \log M$ bits for its representation. – Pseudonym Sep 27 '14 at 14:42
• Just to clarify, are the partitions of 1..N sequential or arbitrary? Eg is a partition {{1,3},{2}} of {1,2,3} allowed? – jkff Sep 29 '14 at 6:17
• Sadly arbitrary, otherwise I could represent the data in O(M), which would have been ideal. – TheCuriousOne Sep 29 '14 at 6:24

You can reduce your $N \lceil \log_2 M \rceil$ bits to $\lceil N \log_2 M\rceil$ by using Dodis et al's "Changing Base without Losing Space".
I don't think you're going to get much smaller than $N \log_2 M$ bits. For $N \gg M$, many functions will be surjective. In particular, there are $\{{N \atop M}\}$ surjective functions, which is at least $M^{N-M}$. Thus, at least $\log_2 \left(M^{N-M}\right) = N \log_2 M - M \log_2 M \in \Omega(N \log_2 M)$ bits must be used to represent one, on average.