## § Generating k bitsets of a given length n:

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 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, 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 e
1| 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 e
2| 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 e
3| 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 e
4| 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 e
5| 1 0 0 1 1 (LSB)

Continuing this process gives us the rest of the sequence:
    a b c d e
5 | 1 0 0 1 1
6 | 1 0 1 0 1
7 | 1 0 1 1 0
8 | 1 1 0 0 1 (note the reset of d!)
9 | 1 1 0 1 0
10| 1 1 1 0 0
{"ft_lang_label":"__label__en","ft_lang_prob":0.8681073,"math_prob":0.9800248,"size":1906,"snap":"2021-04-2021-17","text_gpt3_token_len":716,"char_repetition_ratio":0.1493165,"word_repetition_ratio":0.07770961,"special_character_ratio":0.39821616,"punctuation_ratio":0.08836207,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9630962,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-01-18T12:54:37Z\",\"WARC-Record-ID\":\"<urn:uuid:0ba70015-d5a8-4fd5-b84f-0b99a94b0684>\",\"Content-Length\":\"10045\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:ec5c22c9-2223-4337-9cd0-90eba1804e60>\",\"WARC-Concurrent-To\":\"<urn:uuid:b06a1ea1-e2ae-456e-b413-9a819568a328>\",\"WARC-IP-Address\":\"185.199.111.153\",\"WARC-Target-URI\":\"http://bollu.github.io/generating-k-bitsets-of-a-given-length-n.html\",\"WARC-Payload-Digest\":\"sha1:RIZCEBBCCCVA65QS3DFSDZO4ZAQ6IF6J\",\"WARC-Block-Digest\":\"sha1:ZJ63HPPWE4PGSLGOMUI5YCLVGXPK7H34\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-04/CC-MAIN-2021-04_segments_1610703514796.13_warc_CC-MAIN-20210118123320-20210118153320-00023.warc.gz\"}"}