Today's Little Program prints all bit strings of length `n`
subject to the requirement that the string have exactly `k`
1-bits.
For example, all bit strings of length 4 with 2 bits set are
0011, 0101, 0110, 1001, 1010, and 1100.
Let's write
BitString(`n`, `k`) to mean all the bit strings
of length `n` with exactly `k` bits set.

Let's look at the last bit of a typical member of
BitString(`n`, `k`).
If it is a zero, then removing it leaves a string one bit shorter
but with the same number of bits set.
Conversely every BitString(`n` − 1, `k`) string
can be extended to a BitString(`n`, `k`) string
by adding a zero to the end.

If the last bit is a one, then
removing it leaves a bit string of
length `n` − 1 with exactly `k` − 1 bits set,
and conversely every bit string of length `n` − 1 with
exactly `k` − 1 bits set can be extended to a bit string of
length `n` with exactly `k` bits set by adding a one to the end.

Therefore, our algorithm goes like this:

- Handle base cases.
- Otherwise,
- Recursively call
BitString(
`n`− 1,`k`) and add a 0 to the end. - Recursively call
BitString(
`n`− 1,`k`− 1) and add a 1 to the end.

- Recursively call
BitString(

This algorithm may look awfully familiar. The overall recursive structure is the same as enumerating subsets with binomial coefficients; we just decorate the results differently.

That's because this problem is the same as the problem of enumerating subsets. You can think of the set bits as selecting which elements get put into the subset.

It's not surprising, therefore, that the resulting code is identical except for how we report the results. (Instead of generating arrays, we generate strings.)

function repeatString(s, n) { return new Array(n+1).join(s); } function BitString(n, k, f) { if (k == 0) { f(repeatString("0", n)); return; } if (n == 0) { return; } BitString(n-1, k, function(s) { f(s + "0"); }); BitString(n-1, k-1, function(s) { f(s + "1"); }); }

If `k`

is zero, then that means we are looking
for strings of length `n`

that contain no bits set at all.
There is exactly one of those, namely the string consisting
of `n`

zeroes.

If `k`

is nonzero but `n`

is zero,
then that means we want strings of length zero with some bits set.
That's not possible, so we return without generating anything.

Finally, we handle the recursive case by generating the shorter strings and tacking on the appropriate digits.

Since this is the same algorithm as subset generation, we should be able to write one in terms of the other:

function BitString(n, k, f) { Subsets(n, k, function(s) { var str = ""; for (var i = 1; i <= n; i++) { str += s.indexOf(i) >= 0 ? "1" : "0"; } f(str); }); }

First Comment. First time commenter

Uncaught ReferenceError: Subsets is not defined.

Subsets is defined in the previous little program blog entry about binomial coefficients: blogs.msdn.com/.../10516909.aspx

I am amused by the way that BitString(0, 0, f) works.

Can we have Gosper's Hack yet?

Would you not consider the case when k == n also to be a base case?

if (k == n) { f(repeatString("1", n)); return; }

Drak, that's a potential optimisation that could be included, but not necessary - the recursion will take care of it, eventually.

Another optimisation would be to change the "return nothing" condition from "n == 0" to "n < k".

I know this is just an example, but can I ask why you'd want to count how many bits are set in the real world? I can see testing individual bits is useful, but not sure the count is much use?

Um, this program does not count bits. It generates bits. For example, for test cases. -Raymond]> why you'd want to count how many bits are set in the real world

One example is to verify that WAVEFORMATEXTENSIBLE.Format.nChannels == BitsSetIn(WAVEFORMATEXTENSIBLE.dwChannelMask).