The problem is to generate all bitvectors of length n that have k bits set. For example, generate all bitvectors of length 5 that have 3 bits set.

I know that an algorithm exists in Hacker's delight, but I've been too sick to crack open a book, so I decided to discover the algorithm myself. The one I came up with relies on looking at the numbers moving at a certain velocity, and them colliding with each other. For example, let us try to generate all 5C3 combinations of bits.

We start wih:

#1           count of positiona b c d e    positions1 1 1 0 0    bitset< - - - -    velocity

Where the < represents that the 1 at position a is moving leftwards. Our arena is circular , so the leftmost 1 can wrap around to the right. This leads to the next state

#2a b c d e0 1 1 0 1- - - - <

We continue moving left peacefully.

#3a b c d e0 1 1 1 0- - - < -

whoops, we have now collided with a block of 1s. Not to worry, we simply transfer our velocity by way of collision, from the 1 at d to the 1 at b.

I denote the transfer as follows:

#3a b c d e0 1 1 1 0  original state- - - < -- < < < -  transfer of velocity- < - - -  final state after transfer of velocity

The 1 at b proceeds along its merry way with the given velocity

#4a b c d e1 0 1 1 0< - - - -

Once again, it wraps around, and suffers a collision

#5a b c d e0 0 1 1 1- - - - - < (collision, transfer)- - < < < transfer of velocity- - < - - final state after transfer of velocity

This continues:

0 1 0 1 1  #6- < - - -1 0 0 1 1  #7< - - - - (collision, transfer velocity)< - - < <- - - < -1 0 1 0 1 #8- - < - -1 1 0 0 1 #9- < - - - (colision, transfer velocity< < - - <- - - - <1 1 0 1 0 #10- - - < -1 1 1 0 0 #11: wrap around to initial state

I don't have a proof of correctness, but I have an intuition that this should generate all states. Does anyone have a proof?

EDIT: this algorithm does not work , since it will keep clusters of $k-1$ bits next to each other, when a bit hits a cluster of $k - 1$ bits. For completeness, I'm going to draft out the usual algorithm in full:

§ Usual Algorithm

Let's consider the same example of 5C3:

   a b c d e1| 0 0 1 1 1 (LSB)

We start with all bits at their lowest position. Now, we try to go to the next smallest number, which still has 3 bits toggled. Clearly, we need the bit at position b to be 1, since that's the next number. Then, we can keep the lower 2 bits d, e set to 1, so that it's still as small a number as possible.

   a b c d e2| 0 1 0 1 1 (LSB)

Once again, we now move the digit at d to the digit at c, while keeping the final digit at e to make sure it's still the smallest possible.

   a b c d e3| 0 1 1 0 1 (LSB)

Now, we can move the 1 at e to d, since that will lead to the smallest increase:

   a b c d e4| 0 1 1 1 0 (LSB)

At this point, we are forced to move to location a, since we have exhausted all smaller locations. so we move the 1 at b to a, and then reset all the other bits to be as close to the LSB as possible:

   a b c d e5| 1 0 0 1 1 (LSB)

Continuing this process gives us the rest of the sequence:

    a b c d e5 | 1 0 0 1 16 | 1 0 1 0 17 | 1 0 1 1 08 | 1 1 0 0 1 (note the reset of d!)9 | 1 1 0 1 010| 1 1 1 0 0