## Positive and negative, huh? You're a Bit, aren't you?

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

## grubernd

4/16/2014 3:08:59 AM |nice, this might come in handy.

one question as being relative new to python and still low on the learning curve: isnt this something that one would want to implement with a generator? especially if patterns and the resulting list get longer and bigger? at least that would be my very theoretical understanding of using generators.

## Lemoneer

4/16/2014 4:37:09 AM |grubernd,

Thanks for the comment. I originally wrote a method that returned a generator that looked (something) like this:

def bit_range(length):

return (bit_pattern(length, bits) for i in xrange(length + 1) for bits in itertools.combinations(xrange(length), i))

that relied on a method bit_pattern to generate each pattern as needed, but I thought it to be a lot less understandable. However, you are correct. If you are generating patterns of large length, you should probably do it with a generator. I have updated the post with my original generator.