NUnullc·Aug 25, 2023
There is a pattern here (that also goes with the author's prior article on inverting gauss' sum formula): Generally if if you can make a formula that counts the combination of things you can convert that into a code to encode and decode those combinations into indexes.
It's often easiest to convert the counting expression into enumeration code if you can express it in a recursive form.
So for example the opus audio codec needs to encode/decode signed integer vectors of dimension n whose absolute values sum to k. https://github.com/xiph/opus/blob/master/celt/cwrs.c#L74
(More writeup on enumerations for that set of combinations here: https://web.archive.org/web/20150619082342/https://people.xi... and https://nt4tn.net/papers/cwrs.pdf)
Or this rolling cuckoo filter that optimally encode/decode four sorted numbers in a range 0..2N with the c
Read the rest
onstraint that the they span a range of <=N. https://github.com/sipa/bitcoin/blob/202006_cuckoo_filter/sr...
If you're lucky there will be closed form expressions for the encoding and decoding equations. (There are for both of the above, at least for some parameters, but in both those examples the implementations use small tables because for the ranges involved the tables end up being faster than sqrts).
Another simple example of these is converting subsets of N out of a collection of M elements, where the underlying counting function is just the binomial function. I often do this when constructing tests for trying many combinations of choices without a whole bunch of nested loops or uglier constructs.
Though if you don't need indexing iterating can of often be more simply done in other ways. For a particularly extreme example, to iterate the subsets define your membership as the bits in an unsigned integer. Start with N least significant bits set then update your state each step like so (stopping when the N most significant bits are set):
t=(state&-state)+state;
state=t|((1<<(popcount(state^t)-2))-1);