# 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? Mar 12, 2012 at 14:15
• Why $2^{2048}$? ($|X|=|Y|=2^8$). Mar 12, 2012 at 14:33
• @Vor: Yeah, 8×256 is surprisingly large. :) Mar 12, 2012 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. Mar 12, 2012 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$. Mar 13, 2012 at 4:24