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


Comments (2) -

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


      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.

Comments are closed