4 ms·
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 wi
by nightcracker 9y ago
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 https://en.wikipedia.org/wiki/Combinatorial_number_system. This is very efficient.
Then, to encode duplicates you use the stars and bars trick.
- scythe 9y agoI'm pretty sure that computing N choose k requires O(k log N) memory to store the result (for N >> k). Neat trick though.
- nightcracker 9y agoI should've said O(small), I'm comparing to the solution in the OP, which computes all possible combinations in a lookup table.
- tveita 9y agoArithmetic coding will work too, without any special trick to code duplicates.
- nightcracker 9y agoI don't believe that it does, at least not without some additional trick. How do you handle the case where you repeatedly encode the largest case? E.g. {31, 31, 31, 31}.
- rafael859 9y agoCan you elaborate? I am not very familiar with arithmetic coding, but I thought it required arbitrary precision floating point numbers, so not O(1) memory.
- tveita 9y agoYou don't need arbitrary precision, just enough precision. Specifically, in this case you only need 16 bits. You can start with an upper and lower bound, and narrow it down for each number. Here's an example with numbers dumped from a quick prototype encoder. The exact range numbers aren't that important, but note how the range gets smaller for every symbol we encode: Say we want to encode the ordered numbers 10, 15, 31, 31. We start with the full range [0, 65536) There are C(32 - 10 + 2, 3) = 2024 combinations that start with 10, out of 52360 possible, so that narrows it down to around 4% of the full range, we'll use [49702, 52236) For the next number we only allow numbers 10 and above, 15 has 153 out of 2024 possibilities, range [51022, 51214) For the next number, 31 is only 1 of the 153 possibilities, so it gets a tiny range, [51212, 51214). And now 31 is the next number in 1 out of 1 of cases, so the range is again [51212, 51214) We can code the sequence as either 51212 or 51213, since we used a range that is slightly larger than needed some combinations have multiple codes. We could have started with the smaller range [0, 52360) instead to get a bijection.
- sirclueless 9y agoCan 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"?
- nightcracker 9y agoYes, the universe is expanded.
- sirclueless 9y agoI 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 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).
- nightcracker 9y agoI don't know of a way of doing this without sorting or knowing k ahead of time, sorry.
- syrrim 9y agoThis seems obviously wrong, though I admittedly don't know the stars and bars trick. Lets say you wanted to store a number a in [0,k), for arbitrarily large k. All you would need to so is encode your value as 0 repeated a times, and 1 repeated k-a times. Because you can store arbitrary integers below k with this method, you would need at least log(k) space. If k can be arbitrarily large, you would require unbounded space.