TAOCP Vol 4A: Combinatorial Algorithms, Part 1 · Week 113
TAOCP 7.2.1.5 Generating All Set Partitions: reading guide
Generating all ways to split a set into nonempty blocks, using restricted growth strings, with Gray-code-like orderings and the Bell numbers that count them.
Time About 6 hours this week
Why it matters
Set partitions show up in clustering, test case generation and some scheduling problems.
Before you start
- 7.2.1.4 Generating All Partitions
How to approach it
Implement generation via restricted growth strings and verify counts match Bell numbers.
Exercises
Do every exercise rated 00 to 20 in your head or on paper; they are quick and they check you actually absorbed the definitions. Then pick two or three rated 20 to 25 (M or not) and grind them out fully. Attempt one M25 to M30 and give yourself a hard 90-minute cap before reading the answer. Always read the answer to every exercise you attempted, even the ones you got, because Knuth's answers often teach a second technique.