3
$\begingroup$

I am reading Skiena but do not have a formal background in Computer Science. On page 457 he discusses generating set partitions via restricted growth functions. Here's specifically what he says:

Set partitions can be generated using techniques akin to integer partitions. Each set partition is encoded as a restricted growth function a1,...,an where a1 = 0 and ai <= 1 + max(a1, ..., ai). Each distinct digit identifies a subset, or block, of the partition, while the growth condition ensures that the blocks are sorted into canonical order based on the smallest element in each block. For example, the restricted growth function 0, 1, 1, 2, 0, 3, 1 defines the set partition {{1, 5}, {2, 3, 7}, {4}, {6}}.

Can someone walk me through how this mapping works? It seems to me that a2 should be less than 1 + max(0, a2). But how does that determine a2? How do I get from 0, 1, 1, 2, 0, 3, 1 to that set of partitions? I don't see it at all and would appreciate any explanation or hints.

$\endgroup$
2
$\begingroup$

We want to define a sequence of nonnegative integers $[a_1, a_2,\dotsc, a_n]$ with $a_1=0$ such that for each $1\le i\le n$ we'll have $a_i\le 1+\max\{a_1,\dotsc, a_{i-1}\}$ (Note the last index; the definition you gave would allow $a_i$ to be anything). This condition doesn't uniquely determine $a_i$, rather it gives several possibilities in general.

Let's generate some of these sequences.

  • The shortest is just $[0]$
  • To set $a_2$ we must have $a_2\le1+\max\{0\}=1$ so $a_2$ could be either $0$ or $1$, giving us the length-2 sequences $[0,0]$ and $[0,1]$
  • To set $a_3$ we either start from $[0,0]$ or $[0,1]$. From $[0,0]$ we see that $a_3$ could be either $0$ or $1$, giving us $[0,0,0]$ and $[0,0,1]$. From $[0,1]$ we could have $a_3=0,1,2$, giving us $[0,1,0], [0,1,1],[0,1,2]$.

Let's look at the length-3 sequences, $[0,0,0],[0,0,1],[0,1,0],[0,1,1],[0,1,2]$, and see how they give rise to partitions of the 3-element set $\{a,b,c\}$.

  1. $[0,0,0]$ tells us that each element lives in set 0, giving us the partition $\{a,b,c\}$.
  2. $[0,0,1]$ tells us that elements $a,b$ live in set 0 and $c$ lives in set 1, giving us the partition $\{a,b\},\{c\}$.
  3. Similarly, $[0,1,0]$ gives rise to the partition $\{a,c\},\{b\}$.
  4. Similarly, $[0,1,1]$ gives us $\{a\},\{b,c\}$.
  5. Finally, $[0,1,2]$ gives us $\{a\},\{b\},\{c\}$.

By inspection, these five growth functions give rise to all the five possible partitions of the set $\{a,b,c\}$.

$\endgroup$
1
$\begingroup$

The restricted growth function encodes which part a given integer belongs to: $$ \begin{array}{|c|c|c|c|c|c|c|} \hline 1&2&3&4&5&6&7\\\hline 0&1&1&2&0&3&1\\\hline \end{array} $$

Part 0 contains $\{1,5\}$. Part 1 contains $\{2,3,7\}$. Part 2 contains $\{4\}$. Part 3 contains $\{6\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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