Re:A maximally-dense encoding for n-choose-k (2013)
by dahart on Friday May 20, 2022 @09:18AM
(#31446979)
Isn’t that mapping ambiguous? Maybe I’m mission something, but if you have a number to decode, say n+4, how you do differentiate between (3,n+1) and (2,n+2) and (1,n+3)?
[ Parent
| on HN ]
Re:A maximally-dense encoding for n-choose-k (2013)
by Someone on Friday May 20, 2022 @10:42AM
(#31448117)
If you have to decode n+4, you know the result can’t be in S, as its elements are mapped to {1,…,n}.
So, the result is in T. You subtract n, leaving 4, and use whatever bijection you had for T to decode that into an element of T.
If, on the other hand, you had n-4, you know it must decode to an element of S, and directly use its decoder to find that element.