In which we are strung along with a string of 1s and 0s.
Have you ever had occasion to generate all possible bit combinations of a certain length? Perhaps you are working through Jeffrey Ullman's Automata class on Coursera or futzing about with crypto/encodings/etc. and need all the possible combinations for testing some brilliant algorithm you have been working on. I do not remember what I was working on the last two times I implemented this (the above are logical guesses); however, I am posting it so I will not have to do it a third time.
import itertools
def kbits(n, k):
bit_patterns = []
# generate all possible k positions to set to 1
for bits in itertools.combinations(xrange(n), k):
# create a string of all 0 of the proper length
s = ['0'] * n
# set the chosen positions to 1
for bit in bits:
s[bit] = '1'
# rinse and repeat for all possible positions
bit_patterns.append(''.join(s))
return bit_patterns
def generate_bit_patterns(length):
bit_patterns = []
# starting with no bits set to 1
# create strings with an increasing number of bits set to 1
# until all bits are set to 1
for i in xrange(length + 1):
bit_patterns.extend(kbits(length, i))
return bit_patterns
Usage is simple.
generate_bit_patterns(3)
which will result in
['000', '100', '010', '001', '110', '101', '011', '111']
Note: the implementation of kbits is similar to the one here, and it is entirely likely to be what I started with.
[UPDATE 16APR2014]
As pointed out by grubernd in the comments, if you are generating long bit patterns, you should probably do it with a generator to conserve resources. Here is my original and perhaps harder to understand attempt.
def bit_pattern(length, set_bits):
pattern = ['0'] * length
for i in set_bits:
pattern[i] = '1'
return ''.join(pattern)
def bit_range(length):
return (bit_pattern(length, bits)
for i in xrange(length + 1)
for bits in itertools.combinations(xrange(length), i))
To test this try
for b in bit_range(3):
print b
which will result in
000
100
010
001
110
101
011
111