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

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

StackExchange Computer Science Q#11345, answer score: 7