Generate all binary strings of length n with k bits set

help
1

I want to do a benchmark in rust, using boolean array of size 1_000_000 to generate all the combinations in the array.

There is a python implementation at the below link along with the output; what would be the rust equivalent using boolean array or vector?

https://stackoverflow.com/questions/1851134/generate-all-binary-strings-of-length-n-with-k-bits-set/2075867#2075867

import itertools

def kbits(n, k):
result =
for bits in itertools.combinations(range(n), k):
s = ['0'] * n
for bit in bits:
s[bit] = '1'
result.append(''.join(s))
return result

print((kbits(4, 3)))

Output: ['1110', '1101', '1011', '0111']

2

You do realize the answer will have (1_000_000 choose k) values in the result, right? Even if you could generate a variation in 1 ns, it would take longer than the age of the universe to do anything above k = 4.

If you use a more realistic n, you can go with one of the primitive types (e.g. u128), or a bitvec.

1 Like