3 ms·
How do you map a Natural to the corresponding subset in O(1), while still preserving the compactness of the fixed-size combination encoding? That’s the key prop
by bmc7505 4y ago
How do you map a Natural to the corresponding subset in O(1), while still preserving the compactness of the fixed-size combination encoding? That’s the key property we want from our bounded-length encoding.
- Someone 4y agoDid I miss any requirement about this having to be O(1)? The solutions in the article certainly aren’t, with their for and while loops. I think that’s moving the goalposts.
- bmc7505 4y ago> I think that’s moving the goalposts. It depends on your cost model. If your cost model is with respect to n, this requirement does not move the goalposts because the solution in the article does not depend on n and k is fixed. Computing (1) the natural number corresponding to any n choose k subset or (2) the subset corresponding to any natural number n takes constant time (assuming a constant cost model for all naturals).