Binom Bijection - Storing k-Subsets Efficiently | Hacker News Reader

Binom Bijection - Storing k-Subsets Efficiently

profv.de

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.

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").

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.

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.

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

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

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

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

Reply on news.ycombinator.com