2 ms·
It's odd that in listing the ways to store a choice of 40 numbers from the set {1..100} the paper doesn't mentioning the traditional approach of using a string
by bumbledraven 17y ago
It's odd that in listing the ways to store a choice of 40 numbers from the set {1..100} the paper doesn't mentioning the traditional approach of using a string of 100 bits. Bit n is set to 1 if n is in the subset, and 0 otherwise. This is damn close to the theoretical optimum of 94 bits, and way simpler.
- volkergrabsch 17y agoThanks for the hint! I really forgot that one. I just added it to the presentation. In addition, I adjusted the example to "30 of 100" as this better reflects the average case. ("40 of 100" was too close to the pathological corner case "50 of 100").