[Solved]: What is a compact way to represent a partition of a set?

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