Week 112 of 125
TAOCP 7.2.1.4 Generating All Partitions
Sign up or sign in to tick these off and give this week a due date.
-
Generating all ways to write n as a sum of positive integers, in several orders, plus the beautiful theory of partition counting and generating functions (including Euler's results).
Time About 7 hours this week
Why it matters
Integer partitions appear in dynamic programming problems (coin change), and the generating function theory is a great application of 1.2.9.
Before you start
- 7.2.1.3 Generating All Combinations
- 1.2.9 Generating Functions
How to approach it
Implement partition generation in reverse lexicographic order. Compute partition counts with a DP and check against the generator.
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.