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

<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2012-03-12T14:15:56.230Z
What do you mean by returning a function?  How do you represent a function?
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-12T14:33:41.060Z
Why $2^{2048}$? ($|X|=|Y|=2^8$).
Marzio De Biasi
CC BY-SA 3.0
2012-03-12T14:44:20.737Z
@Vor: Calculate $|Y|^{|X|}$. :)
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-12T15:29:46.793Z
@Tsuyoshi: thanks for convincing my mind that 8*256 is not 1024!!! :-)
Marzio De Biasi
CC BY-SA 3.0
2012-03-12T15:47:14.917Z
@Vor: Yeah, 8×256 is surprisingly large. :)
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-12T21:21:42.970Z
A function could be represented by any computable means.  E.g. as a simple table, or a function in any programming language.  By return a function I mean I want to find a function that maps bit strings (of 2048 length) to functions in F.
zenna
CC BY-SA 3.0
2012-03-12T23:44:55.430Z
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
CC BY-SA 3.0
2012-03-13T04:24:07.263Z
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
<ds.algorithms><co.combinatorics><time-complexity>
Indexing over all possible functions in better than linear time
zenna
# Indexing over all possible functions in better than linear time

(Asked by: username_0 on 2012-03-12)

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

**Tags:** ds.algorithms, co.combinatorics, time-complexity
> **Comments:**
> **username_1**: What do you mean by returning a function?  How do you represent a function?  
> **username_2**: Why $2^{2048}$? ($|X|=|Y|=2^8$).  
> **username_1**: @Vor: Calculate $|Y|^{|X|}$. :)  
> **username_2**: @Tsuyoshi: thanks for convincing my mind that 8*256 is not 1024!!! :-)  
> **username_1**: @Vor: Yeah, 8×256 is surprisingly large. :)  
> **username_0**: A function could be represented by any computable means.  E.g. as a simple table, or a function in any programming language.  By return a function I mean I want to find a function that maps bit strings (of 2048 length) to functions in F.  
> **username_3**: 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.  
> **username_4**: 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$.  

---

## 0 answers

