 # Lemon Difficult

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.