Binom Bijection - Storing k-Subsets Efficiently

bumbledraven · on Sept 7, 2009

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 · on Sept 7, 2009

Thanks 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 · on Sept 7, 2009

The 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 · on Sept 7, 2009

Yes, 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.

zaphar · on Sept 7, 2009

I know this isn't a discussion of his subject matter but I love his presentation format.

volkergrabsch · on Sept 7, 2009

Thanks! 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

carbocation · on Sept 7, 2009

I was thinking the exact same thing. This is a rare example of an appropriate use of the PowerPoint medium.

volkergrabsch · on Sept 7, 2009

More exactly, it's the "beamer" package of LaTeX, not PowerPoint.