# Correctness proof for algorithm to generate k bitsets of n bits (nCk)

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. There are $$\binom 5 3$$ possible combinations, and they are:

# 1 | 0 0 1 1 1
# 2 | 0 1 0 1 1
# 3 | 0 1 1 0 1
# 4 | 0 1 1 1 0
# 5 | 1 0 0 1 1
# 6 | 1 0 1 0 1
# 7 | 1 0 1 1 0
# 8 | 1 1 0 0 1
# 9 | 1 1 0 1 0
# 10| 1 1 1 0 0


### The algorithm:

Begin from the state

#1           count of position
a b c d e    positions
1 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

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


We continue moving left peacefully.

#3
a b c d e
0 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:

#3
a b c d e
0 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

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


Once again, it wraps around, and suffers a collision

#5
a b c d e
0 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. I feel like intuition might be possible, but I am not sure. Could someone help me with a proof strategy? Is this a known algorithm?

• What will your algorithm produce for $1010$ ? Oct 17, 2019 at 23:07

This will not work. At any point in time, by the very definition of how you "transfer verlocity", you always have a contiguous (in the circular sense) block of $$1$$'s of length $$k-1$$ (or $$k$$).
In this example, you are lucky to get $$10101$$ which looks like three separate $$1$$s but in fact, in the circular sense, has a block of two $$1$$s.
However, if you try e.g. $$n=6, k=3$$, this method will never be able to generate $$101010$$.