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

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