Last time we saw that producing all the subsequences of a given size k from a given sequence of size n is essentially the same problem as computing all the sequences of n Booleans where exactly k of them are true. How do we do that?
An approach that I often see is “enumerate all sequences of n Booleans, count the number of on bits, and discard those which have too many or too few”. Though that works, it’s not ideal. Suppose we are seeking to enumerate the combinations of 16 items chosen from a set of 32. There are over four billion possible combinations of 32 bits, and of those over three billion of them have more or fewer than 16 true bits, so that’s a lot of counting and discarding to do. We can do better! To do so, we’ll use a combination of all my favourite techniques:
- Immutable data structures
- Abstract classes with derived nested classes
- Recursion
Long-time readers of this blog will have seen me use these techniques before, but for new readers, a quick introduction is in order. Continue reading
