News for hackers. Stuff that matters.

A comment on A maximally-dense encoding for n-choose-k (2013). Parent comment

Re:A maximally-dense encoding for n-choose-k (2013) by bmc7505 on Friday May 20, 2022 @09:20AM (#31446997)
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.
[ Parent | on HN ]
Re:A maximally-dense encoding for n-choose-k (2013) by Someone on Friday May 20, 2022 @10:37AM (#31448051)
Did 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.

[ Parent | on HN ]
Re:A maximally-dense encoding for n-choose-k (2013) by bmc7505 on Friday May 20, 2022 @11:01AM (#31448409)
> 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).

[ Parent | on HN ]