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.
> 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?
Yeah, 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.
