4 ms·
For those who are not aware, knowing how to count the number of structures is (nearly) the same as knowing how to encode said structure as an integer (space-opt
by qazxcvbnm 1y ago
For those who are not aware, knowing how to count the number of structures is (nearly) the same as knowing how to encode said structure as an integer (space-optimally) (the naive general algorithm would not have good time complexity); to convert to integer, simply define some ordering on said structures, enumerate until you find your structure, the index of the structure is the integer encoding; conversely, to decode, simply list all structures and pick the structure with the index of the integer.
- manmal 1y agoThat reminds me of https://everyuuid.com/ https://everyuuid.com/
- abeppu 1y ago> simply list all structures and pick the structure with the index of the integer This sounds like to decode a single item you have to do work proportional to the cardinality of the set? Optimal space efficiency comes at a high computational overhead?
- qazxcvbnm 1y agoYeah, its a theoretical general connection. Once you’ve pinned down the specific structure and know how many structures to skip by virtue of knowing how to count them, it becomes a somewhat practical algorithm.