What is a compact way to represent a partition of a set?
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 &lt; \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' &lt; \binom{n}{k} B_{n-k}$, it can be written as $C_1 B_{n-k} + C_2$, where $0 \leq C_2 &lt; 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&gt;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 &lt; \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'$.