Problem Detail: There exist efficient data structures for representing set partitions. These data structures have good time complexities for operations like Union and Find, but they are not particularly space-efficient. What is a space-efficient way to represent a partition of a set? Here is one possible starting point: I know that the number of partitions of a set with $N$ elements is $B_N$, the $N$-th Bell number. So the optimal space complexity for representing a partition of a set with $N$ elements is $log_2(B_N)$ bits. To find such a representation, we could look for a one-to-one mapping between (the set of partitions of a set of $N$ elements) and (the set of integers from $1$ to $B_N$). Is there such a mapping that is efficient to compute? What I mean by “efficient” is that I want to convert this compact representation to / from an easy-to-manipulate representation (such as a list of lists) in time polynomial in $N$ or $log_2(B_N)$.
Asked By : cberzan
Answered By : Yuval Filmus
You can use the way that the recurrence formula below is derived to find your encoding: $$ B_{n+1} = sum_{k=0}^n binom{n}{k} B_k. $$ This is proved by consider how many other elements are in the part containing the element $n+1$. If there are $n-k$ of these, then we have $binom{n}{n-k} = binom{n}{k}$ choices for them, and $B_k$ choices for partitioning the rest. Using this, we can give a recursive algorithm to convert any partition of $n+1$ to a number in the range $0,ldots,B_{n+1}-1$. I assume you already have a way of converting a subset of size $k$ of ${1,ldots,n}$ to a number in the range $0,ldots,binom{n}{k}-1$ (such an algorithm can be devised in the same way using Pascal’s recurrence $binom{n}{k} = binom{n-1}{k} + binom{n-1}{k-1}$). Suppose that the part containing $n+1$ contains $k$ other elements. Find their code $C_1$. Compute a partition of ${1,ldots,n-k}$ by “compressing” all the remaining elements to that range. Recursively compute its code $C_2$. The new code is $$C = sum_{l=0}^{k-1} binom{n}{l} B_l + C_1 B_k + C_2. $$ In the other direction, given a code $C$, find the unique $k$ such that $$ sum_{l=0}^{k-1} binom{n}{l} B_l leq C < sum_{l=0}^k binom{n}{l} B_l, $$ and define $$ C’ = C – sum_{l=0}^{k-1} binom{n}{l} B_l. $$ Since $0 leq C’ < binom{n}{k} B_k$, it can be written as $C_1 B_k + C_2$, where $0 leq C_2 < B_k$. Now $C_1$ codes the elements in the part containing $n+1$, and $C_2$ codes a partition of ${1,ldots,n-k}$, which can be decoded recursively. To complete the decoding, you have to “uncompress” the latter partition so that it contains all the element not appearing in the part containing $n+1$. Here is how to use the same technique to encode a subset $S$ of ${1,ldots,n}$ of size $k$, recursively. If $k=0$ then the code is $0$, so suppose $k>0$. If $n in S$ then let $C_1$ be a code of $S setminus {n}$, as a subset of size $k-1$ of ${1,ldots,n-1}$; the code of $S$ is $C_1$. If $n notin S$ then let $C_1$ be a code of $S$, as a subset of size $k$ of ${1,ldots,n-1}$; the code of $S$ is $C_1 + binom{n-1}{k-1}$. To decode a code $C$, there are two cases. If $C < binom{n-1}{k-1}$ then decode a subset $S’$ of ${1,ldots,n-1}$ of size $k-1$ whose code is $C$, and output $S’ cup {n}$. Otherwise, decode a subset $S’$ of ${1,ldots,n-1}$ of size $k$ whose code is $C – binom{n-1}{k-1}$, and output $S’$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11345
