Week 111 of 125
TAOCP 7.2.1.3 Generating All Combinations
Sign up or sign in to tick these off and give this week a due date.
-
Generating all k-subsets of an n-set: lexicographic order, revolving-door Gray codes where one element enters and one leaves, and other orderings.
Time About 7 hours this week
Why it matters
Subset enumeration is everywhere in brute-force search and testing. Gray-code orderings let you update a running computation in O(1) per step.
Before you start
- 7.2.1.2 Generating All Permutations
How to approach it
Implement lexicographic combinations and a revolving-door order. Use the revolving door to maintain a running sum of selected elements cheaply.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.