Week 74 of 125
TAOCP 5.1.2 Permutations of a Multiset
Sign up or sign in to tick these off and give this week a due date.
-
Permutations where elements can repeat, and an algebraic product on them (the intercalation product) that lets Knuth prove facts about factoring permutations into cycles in a unified way.
Time About 7 hours this week
Why it matters
Sorting with duplicate keys is the normal case in practice. This section is fairly abstract, though; the practical payoff is mostly the mental model.
Before you start
- 5.1.1 Inversions
How to approach it
Read the definitions with lots of small examples. The intercalation product is unusual; work several products by hand before reading the theorems. Accept a slower pace here.
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.
Traps
- Trying to rush through the abstract algebra. It only clicks with examples.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.