81–90 of 149 posts
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?
Earlier quoted context omitted.
But if I pick my buckets right, I can store only the lsb in each bucket. Or more efficient, dynamically construct an implicit trie/heap type thing, where each leaf is the count of times that int appears (and the int itself is encoded in the location) That feels really, really handwavy but promising?
You're sort of on the right track, but of course you have to encode those counts very carefully because 1M counts will exceed 2MB of memory unless you work hard.
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...
It is possible to do this in O(1) memory, for arbitrary sized collections, efficiently. The first trick is to make a function that can calculate the nth set with k elements from some universe U (in this case U = {0..2^5-1} without order (no duplicates) directly. This is done using the https://en.wikipedia.org/wiki/Combinatorial_number_system . This is very efficient. Then, to encode duplicates you use the stars and b…
Arithmetic coding will work too, without any special trick to code duplicates.
Earlier quoted context omitted.
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…
log2(32C4 + 32C3 * 3 + 32C2 * 3 + 32C1)
It is possible to do this in O(1) memory, for arbitrary sized collections, efficiently. The first trick is to make a function that can calculate the nth set with k elements from some universe U (in this case U = {0..2^5-1} without order (no duplicates) directly. This is done using the https://en.wikipedia.org/wiki/Combinatorial_number_system . This is very efficient. Then, to encode duplicates you use the stars and b…
Arithmetic coding will work too, without any special trick to code duplicates.
This is quite related to the problem of sorting a million 32 bit integers using only 2M of RAM (and no disk). It can be done.
A list of deltas should do it. In the worst case, the deltas would use log2[2^32/1000000] * 1000000 bits, so about 1.5 MB. Plus some space because of base 128 encoding (it increases size up to 37/32, rounded up per byte). I got a worst case of exactly 2 MB (1.907 MiB) (all deltas being 4294, so the list is 0, 4294, 8588...), but maybe it's possible to get better than that. It would be uber slow though, probably n^2.
Earlier quoted context omitted.
Can you elaborate on the second part? Are you saying you're going to expand the size of the universe by a factor of 2^(k-1) to use as locations of the "bars"?
Yes, the universe is expanded.
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 other problem in these comments of sorting 1M 32-bit integers in 2MB of RAM (you can store them with this mechanism in about 1.7MB of RAM, but only if they were already sorted).
It is possible to do this in O(1) memory, for arbitrary sized collections, efficiently. The first trick is to make a function that can calculate the nth set with k elements from some universe U (in this case U = {0..2^5-1} without order (no duplicates) directly. This is done using the https://en.wikipedia.org/wiki/Combinatorial_number_system . This is very efficient. Then, to encode duplicates you use the stars and b…
I'm pretty sure that computing N choose k requires O(k log N) memory to store the result (for N >> k). Neat trick though.