Meetup summary

2026-01-30 - Set partition generation - part 3

Agenda:

Last time we covered partition generation through the Stirling set number recurrence as well as generating partitions lexicographically “top-down” using recursion. I wasn’t happy with the latter since the conditions weren’t easy to sum up simply and intuitively to somebody who hasn’t worked through the problem directly. Today, I want to revisit lexicographical generation using a “stateless” generation technique1 before moving on to the other methods.

  • Develop 5 different techniques to generate all (unrestricted) set partitions:
    • Using strict canonicalization and generating in lexcigographical order with a stateless “increment” function2.
    • Using the Bell triangle recurrence
    • Using the Stirling set number recurrence and summing over all part counts
    • Using lexicographically ordered “restricted growth” strings. (This is equivalent to Knuth’s Algorithm H above.)
    • Using a pseudo-Gray code over the same restricted growth strings noted above. Surprisingly, this was the last technique I found and possibly the hardest to derive, yet in my opinion the easiest to understand (if you’re familiar with Gray codes). We’ll briefly discuss Gray codes before drilling into this one. While this is not strictly a Gray code in RGS space, it does generate partitions where each one differs from its predecessor by a single partition edit operation (i.e., moving a single element to a different block or into its own (new) block).
    • Using a true Gray code over restricted growth strings (using cyclig wrapping and some special properties of RGSs). This one follows the Ehrlich code as mentioned in TAOCP.
  • Motivation for the above is to see different ways to approach the regular set partitioning problem and try to extend it to multisets in a similar way. I’ve started work on this, but would like input from you on some different approaches we could take for multiset partitions. I highly recommend reading the referenced TAOCP section for inspiration.

Footnotes

  1. It’s stateless in the sense that there is no implicit (or explicit) stack frame containing metadata about the current partition or where we want to go next. Unfortunately, this makes it harder to aggressively prune the search space without some linear scans through the unplaced elements. On the other hand, this technique is conceptually simpler than the recursive technique we discussed last time. ↩

  2. Note that there are lots of hidden runtime factors in the increment function itself and it’s not yet clear to me how to do this efficiently. On the other hand, it’s good enough for most situations where you’d actually want to visit every partition. ↩

tags: