What is a compact way to represent a partition of a set?

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)$.

• wondering, how far could $\log_2(B_N)$ be from the naive/natural encoding of just assigning unique integers to each element of the set where the integer represents the partition #? maybe it is "not that much difference"...
– vzn
Apr 16, 2013 at 15:34

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 considering 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}^{n-k-1} \binom{n}{l} B_l + C_1 B_{n-k} + C_2.$$

In the other direction, given a code $$C$$, find the unique $$k$$ such that $$\sum_{l=0}^{n-k-1} \binom{n}{l} B_l \leq C < \sum_{l=0}^{n-k} \binom{n}{l} B_l,$$ and define $$C' = C - \sum_{l=0}^{n-k-1} \binom{n}{l} B_l.$$ Since $$0 \leq C' < \binom{n}{k} B_{n-k}$$, it can be written as $$C_1 B_{n-k} + C_2$$, where $$0 \leq C_2 < B_{n-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'$$.

• Excellent answer; thank you. Minor bug: In the proof sketch for the recurrence formula at the top, I think you mean "there are $n - k$ of those" instead of "there are $k$ of those" -- then the remaining $k$ elements can be partitioned in $B_k$ ways. Apr 17, 2013 at 18:48