4 ms·
Binom Bijection - Storing k-Subsets Efficiently
- zaphar 17y agoI know this isn't a discussion of his subject matter but I love his presentation format.
- carbocation 17y agoI was thinking the exact same thing. This is a rare example of an appropriate use of the PowerPoint medium.
- volkergrabsch 17y agoMore exactly, it's the "beamer" package of LaTeX, not PowerPoint.
- volkergrabsch 17y agoThanks! In fact, I originally wanted to write a classic paper, but I realized that ... * The subject isn't complex enough to really fill a paper. * Whenever I want to talk to someone about this, presentation slides are very handy in contrast to continuous text. * The audience are people in the web, who look at it on screen and won't print it. In addition, I was inspired by other mathematical slides such as http://www.tu-harburg.de/~matjz/work/lectures/ZAemB.pdf http://www.tu-harburg.de/~matjz/work/lectures/ZAemB.pdf
- bumbledraven 17y agoIt'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").
- cperciva 17y agoThe author has a rather narrow definition of "efficient". Yes, he uses close to the minimum number of bits of storage... but his encoding scheme is horribly slow -- encoding takes O(k^2 log n) time, and decoding using the presented algorithm takes O(k^2 n log n) time.
- volkergrabsch 17y agoYes, I meant just space efficiency. It might be handy if you have many subsets (e.g. a solution space) you need to store in memory or on disk. I'm still looking for a faster algorithm that reaches the optimal space efficiency.