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)?

  • 4
    $\begingroup$ What do you mean by returning a function? How do you represent a function? $\endgroup$ Mar 12, 2012 at 14:15
  • $\begingroup$ Why $2^{2048}$? ($|X|=|Y|=2^8$). $\endgroup$ Mar 12, 2012 at 14:33
  • 2
    $\begingroup$ @Vor: Yeah, 8×256 is surprisingly large. :) $\endgroup$ Mar 12, 2012 at 15:47
  • 2
    $\begingroup$ 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. $\endgroup$
    – Chao Xu
    Mar 12, 2012 at 23:44
  • 5
    $\begingroup$ 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$. $\endgroup$
    – mjqxxxx
    Mar 13, 2012 at 4:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.