Hacker News Reader

Comment by ajkjk | Hacker News Reader

To answer the obvious next question:

Four 5-bit values in order have 20 bits of entropy, so cannot be stored in 16 bits.

Four 5-bit values without order have 20 - log2(4!) =~ 20 - 4.59 = 15.41 bits of entropy (corresponding to log(2^20/4!) possible configurations), and thus can fit in 16 bits of data if you're clever about it.

View on HN

Your math is wrong.

If two of the numbers happen to be the same, order no longer matters for those numbers, so your log2(4!) needs to be larger...

The maximum entropy is what is important, to the encoding challenge, as I understood it.

Right. So the true answer is

    log2((32*31*30*29)/(4*3*2) + (32*31*30)/2 + (32*31) + (32*31)/2) = 15.675

 which is still smaller than 16.

Are you sure you don't mean

   log2((32*31*30*29)/(4*3*2*1) + (32*31*30)/(3*2*1) + (32*31)/(2*1) + 32/1) = 15.34

using the number of sets of values from {0, 2^5-1} with at most 4 elements?

If on the other hand you want to store exactly 4 values, possibly with duplicates (while still ignoring order), you need to count multisets ( https://en.wikipedia.org/wiki/Bag_(mathematics)#Counting_mul... )

  log2( (35*34*33*32)/(4*3*2*1) ) = 15.676

The second answer, 15.676, is the correct one. It can also be arrived at by:

log2(32C4 + 32C3 * 3 + 32C2 * 3 + 32C1)

I followed the original link as well as this calculation. Why not use this to map them directly (instead of breaking it into 12 bits and 4 bits) ? We'll just have some unused headroom in 16 bits. This would seem more natural than thinking of the 12 + 4 solution.

It uses more memory.

What the parent message did is: log2(32+4-1 C 4), because the number of k-sized combinations of n objects with repetitions is (n+k-1)Ck. One way to prove it is that you sort the objects (so you can establish an order among the objects in the combination) and add k-1 dummy objects for "the second is the same as the first, the third is the same as the second,..., the last is the same as the penultimate".

His math is right. The factorial already took care of the fact that order does not matter.

If you want to optimize storage of duplicates, you still have to store the number of duplicate numbers, and you are back where you started.

The factorial is taking too much care of the fact that order does not matter. If I wanted to store four 1-bit numbers, ajkjk's math would suggest that I need log2(2^4/4!) = -0.58, i.e. a negative number of bits. You can't just divide by 4! because not all combinations of 4 numbers have 4! unique permutations.

> If you want to optimize storage of duplicates, you still have to store the number of duplicate numbers, and you are back where you started.

No, because you can shave off a few bits by ignoring the ordering of the non-duplicates.

You’re right, correction appreciated.

Actually the log2(4!) needs to be smaller, because as yorwba below says, duplicates don't have 24 permutations.

Does this implementation allow duplicates? Typically a set is defined as an unordered collection with no duplicate items.

Is there a specific topic of study that taught you those formulas?

Not the person you asked but

4! is the number of permutations of a list - it's commonly seen throughout CS theory and other forms of discrete math.

log_2(n) is the number of bits needed to store a integer from 0 to n - it's reasonably commonly used in CS theory education.

Probability theory and information theory.

As cameldrv said, information theory. The late David MacKay has a good free book:

http://www.inference.org.uk/itprnn/book.html

The intro chapters cover the topic of measuring informational entropy.

Aside: One interesting application is to the problem of “use a balance scale only three times to determine which of twelve balls has the wrong weight (too heavy or light)”. You choose the weighings so as as to maximize the entropy of the outcome i.e. so there are many possible outcomes of equal probability.

try combinatorics branch of mathematics

https://en.wikipedia.org/wiki/Information_theory

As others have mentioned, it comes up in information theory, or maybe in some subfields of combinatorics and probability. I learned it tangentially in various parts of physics.

But I might just recommend going to the source! which is Claude Shannon's seminal masters thesis on coding: http://affect-reason-utility.com/1301/4/shannon1948.pdf . It's surprisingly readable and worth at least skimming if you like this stuff.

[deleted]

They're not ordered: that's the whole point.

My bad, I misread!

Reply on news.ycombinator.com