While I know how to generate all (n choose k) bitstrings of size n with exactly k bits set to one, I'm struggling finding a bijection, that gets as input a number i between 1 and (n choose k) and outputs the i-th vector of that kind in an arbitrary ordering.
Obviously, one could simply enumerate all of that vectors in a list and then output the i-th entry of the list, but unfortunately that approach has to high memory requirements for my setting.
Edit: also it should be an efficient computation, computing the list of all vectors for each call to the bijection is also not an option.
The straightforward way:
If i < (n-1 choose k), then the leftmost bit is 0 and i determines the remainder of the bits recursively. Otherwise, the leftmost bit is 1, and i - (n-1 choose k) determines the remainder of the bits recursively. In the second case there are at most (n-1 choose k-1) possible values of i - (n-1 choose k).