11
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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"... $\endgroup$
    – vzn
    Apr 16, 2013 at 15:34

1 Answer 1

7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – cberzan
    Apr 17, 2013 at 18:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.