# Indexing over all possible functions in better than linear time

Given two sets X and Y, the number of functions mapping X to Y is $\vert Y\vert^{\vert X \vert}$.

In particular I am interested in binary strings of relatively small length, e.g. 8. There are $2^8$ (comprising set $B$) possible bit strings and $2^{2048}$ functions that map onto the same set (let's call the set of these $F$ ). So I need 2048 bits to represent these functions uniquely.

My goal is to find a function, that given an arbitrary an arbitrary 2048 length bit string, will return the appropriate function from the $F$. I can imagine doing this with space on order $2^8$, and average time linear in $|F|$, using a hash table mapping $B\rightarrow B$ and some enumeration over mappings.

The question is, can I do better than this, especially with regard to the linear time (without of course just storing all functions)?

• What do you mean by returning a function? How do you represent a function? – Tsuyoshi Ito Mar 12 '12 at 14:15
• Why $2^{2048}$? ($|X|=|Y|=2^8$). – Marzio De Biasi Mar 12 '12 at 14:33
• @Vor: Yeah, 8×256 is surprisingly large. :) – Tsuyoshi Ito Mar 12 '12 at 15:47
• It is easier to just think about the natural numbers instead of the binary strings. Every function is just a ordered k tuple of integers from 0 to n-1. Now you can consider it as integers in base n. All you need is to implement all the simple bijections, which is nothing more than base conversion. – Chao Xu Mar 12 '12 at 23:44
• Just interpret the 2048-bit string as the 8-bit values of the function, listed in order (i.e., $f(0) \oplus f(1) \oplus \dots \oplus f(255)$, where $\oplus$ is concatenation). To find $f(x)$, read off the 8 bits beginning at bit $8x$. – mjqxxxx Mar 13 '12 at 4:24