3

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.

Memphisd
  • 307
  • 1
  • 8

1 Answers1

3

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).

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87