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
    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.


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