91–100 of 149 posts
What's the practical use for this?
Earlier quoted context omitted.
Yes, the universe is expanded.
I really like this mechanism. It seems like it should be the optimal way to store a set of size k. Out of curiosity, do you know of an efficient way to calculate this without sorting first? Or even better, without knowing k ahead of time? If you can sort your input first it's trivial, but even though it seems like a super efficient way to store a set of numbers I don't know how to use it to solve, for example, the ot…
Why is this first line true: "This works because there are 3876 possible unique values for a set of 4 4 bit values" Each 4 bit number has 16 possible values. And you can order them in the set in 4! = 24 ways. So I thought you would get 24 * 16 = 384. Can someone explain?
So it's \binom{2^4 + 4 - 1}{4} = 3876
In other words, there are 3876 multisets of cardinality 4 with elements taken from the set containing all 4 bit values.
Earlier quoted context omitted.
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.
Is there a specific topic of study that taught you those formulas?
What's the practical use for this?
Saving space in data structures that use buckets such as hash tables. I actually discovered this in a paper on hash tables that kind of just mentioned that it was a thing but I had a harder time finding out exactly how it was done.
Ah, without preserving order. That's a set of four 5-bit values, not a sequence of four 5-bit values.
Let's assume that our set is (a, b, c, d). It is ordered, therefore a Consider all possible numbers that may be in our set, laid out in order.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
For each element in the set, we mark its position in this order by placing a marker to the left of the corresponding number.
For our example, we first mark element 2:
0 1 m 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Then 4:
0 1 m 2 3 m 4 5 6 7 8 9 10 11 12 13 14 15
Then, 4 again:
0 1 m 2 3 m m 4 5 6 7 8 9 10 11 12 13 14 15
And finally, 10:
0 1 m 2 3 m m 4 5 6 7 8 9 m 10 11 12 13 14 15
Now, out of these 16+4 places, only 19 of them could be a valid placement for a marker, as a marker should always be placed to the left of a number (or said differently, "15" will always be in the end.)
Therefore, there are 19 choose 4 ways to pick the locations of the markers.
Earlier quoted context omitted.
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.
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...