Week 110 of 125
TAOCP 7.2.1.2 Generating All Permutations
Sign up or sign in to tick these off and give this week a due date.
-
Many ways to list all permutations: lexicographic order, plain changes (adjacent swaps), Heap's method, and others, with comparisons of their speed and properties.
Time About 8 hours this week
Why it matters
next_permutation is a standard library function and a classic interview question. Choosing the right generator matters when you brute force.
Before you start
- 7.2.1.1 Generating All n-Tuples
- 1.3.3 Permutations
How to approach it
Implement lexicographic next-permutation, plain changes, and Heap's method. Count swaps per permutation and benchmark.
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.
Traps
- Lexicographic generation with duplicates: handle multisets correctly.