Sign in to watch this lesson
Advanced - Combinatorics, Games and Puzzles Ā· 4:52
Generating K-Combinations
Two ways to list every K-subset of N items. The dictionary order steps from one combination to the next by bumping the rightmost slot that is still below its ceiling and refilling everything after it, while the revolving-door order, read off the Gray codes with exactly K ones, changes one member at a time. We see why the reflection behind the Gray code keeps every step to a single swap, build that order directly with a recursion instead of filtering 2^N codes, and time both on a Mac.
You will learn
- Step to the next K-combination in dictionary order by finding the rightmost slot below its ceiling n - k + i + 1, incrementing it and refilling the suffix
- Produce a revolving-door order (one member out, one in) by keeping the Gray codes with exactly K ones
- Explain with the reflected construction G(n) = 0 + G(n-1), then 1 + G(n-1) reversed, why every step and the wrap-around is a single swap
- Generate the revolving-door order directly with G(n, k) = 0 + G(n-1, k), then 1 + G(n-1, k-1) reversed, avoiding the 2^N filter when C(N, K) is small