Skip to main content
1 of 3
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

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 consider how many other elements are in the part containing the element $n+1$. If there are $k$ of these, then we have $\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}^{k-1} \binom{n}{l} B_l + C_1 B_k + C_2. $$

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

Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512