[Tutor] Bit Strings

[Marc Barry]

Tim:

Here is an example script of what I think you were looking for. It is fairly
simple and doesn't use any recursion. See explanation after script.

#----

def decToBin(dec_number):

	bit_string = ""

	# The following just does simple decimal to binary conversion.
	if(dec_number == 0):
		bit_string = "0"
	else:
		while(dec_number != 0):
			if(dec_number % 2 == 1):
				bit_string = "1" + bit_string
				dec_number = dec_number - 1
				dec_number = dec_number / 2
			else:
				bit_string = "0" + bit_string
				dec_number = dec_number / 2

	return bit_string

def createBitStrings(bit_string_length):

	bit_strings = []
	bit_string = ""

	# This just here to illustrate a point that the maximum decimal number
	# represented by n bits is (2^n)-1. We have to add 1 below when using
	# range because it generates values in the range [start, end).
	max_decimal_number = (2**bit_string_length) - 1

	# This for loop just loops through all the decimal numbers that can be
	# represented by n bits.
	for i in range(0, max_decimal_number + 1):
		bit_string = decToBin(i)
		# At this point the bit string needs to be padded with 0's so
		# that it contains n bits.
		while(len(bit_string) < bit_string_length):
			bit_string = "0" + bit_string
		bit_strings.append(bit_string)

	return bit_strings

# Print the list of bit strings.
print createBitStrings(4)

#---

The output from the above script is:

['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000',
'1001', '1010', '1011', '1100', '1101', '1110', '1111']

Basically, what I have done is created two functions called decToBin and
createBitStrings. The decToBin function takes as input a decimal number and
convertes it to it binary string representation. The createBitStrings function
takes the length of the bit string for which all possible combinations should
be generated. It just loops through all possible decimal numbers, converts them
to binary and pads with 0's as necessary so that you have n bits.

I hope this helps.

Regards,

Marc


 --- "Timothy M. Brauch" <tbrauch at mindless.com> wrote: > There has to be an
easy way to do this that I am just not seeing.  I am
> trying to create all bit strings of length n.  Right now my code is as
> follows:
> 
> bitStrings = []
> for a0 in [0,1]:
>     for a1 in  [0,1]:
>         for a2 in [0,1]:
>             oneString = str(a0)+str(a1)+str(a2)
>             bitStrings.append(oneString)
> print bitStrings
> 
> I know this is ugly and when I need longer strings, say n = 10, the code
> gets way too repetitive with 10 nested for loops.  Surely there is an easier
> way to do this, but I just can't figure it out.  I have a function that will
> generate the above functions, but it is uglier and probably way not the
> correct way to go about this.
> 
> def generator(n):
>     tb = "    "
>     stringMaker = ""
>     print "bitStrings = []"
>     for i in xrange(0,n+1):
>         print i*tb + "for a"+str(i)+" in [0,1]:"
>         stringMaker = stringMaker + "str"+chr(40)+"a"+str(i)+chr(41)+chr(43)
>     stringMaker = stringMaker[:-1] #strip the last chr(43)
>     print (i+1)*tb + "oneString = "+stringMaker
>     print (i+1)*tb + "bitStrings.append(oneString)"
>     print "print bitStrings"
> 
> 
> Any suggestions?
> 
>  - Tim
> 
> 
> ---
> Outgoing mail is certified Virus Free.
> Checked by AVG anti-virus system (http://www.grisoft.com).
> Version: 6.0.528 / Virus Database: 324 - Release Date: 10/17/2003
> 
> 
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor 

________________________________________________________________________
Want to chat instantly with your online friends?  Get the FREE Yahoo!
Messenger http://mail.messenger.yahoo.co.uk