Geek Answers Handbook

Creating a list of bits of length n in Python

I need a function that will give me all possible strings of a certain length, which consist only of zeros and ones. For instance:

spam(4)

should get me:

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

I tried using itertools.permutations for the job. So this is what I did.

 def getPerms(n): perms = getCandidates(n) res = [] for i in perms: res.extend(permutations(i)) res = clean(res) return res def clean(ar): res = [] for i in ar: temp = "" for j in i: temp += j res.append(temp) return list(set(res)) def getCandidates(n): res = [] for i in range(1, n): res.append("1"*i + "0"*(ni)) return res

But it is terribly inefficient and gives a memory error of 10 as input.

+4
source share
4 answers

Use itertools.product instead.

 >>> import itertools >>> [''.join(i) for i in itertools.product('01', repeat=4)] ['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']

Using the function (if itertools already imported):

 def bitGen(n): return [''.join(i) for i in itertools.product('01', repeat=n)]

For larger n may be more appropriate to return the generator.

 def bitGen(n): return (''.join(i) for i in itertools.product('01', repeat=n)) # Alternatively: def bitGen(n): for i in itertools.product('01', repeat=n): yield ''.join(i)
+9
source

You just want to generate bit strings, obviously. Here is the fastest way that I know:

 for i in xrange(1, 2**n-1): yield '{:0{n}b}'.format(i, n=n)

This generates every bitstream of length exactly n containing at least one 1 and one 0.

Example:

 >>> def gen(n): ... for i in xrange(1, 2**n-1): ... yield '{:0{n}b}'.format(i, n=n) ... >>> list(gen(4)) ['0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110']
+7
source

In addition to the excellent answers above, if you want to continue the path you started, here is a better implementation using yield :

 from itertools import permutations def spam(n): for perm in getPerms(n): print perm, print def getPerms(n): for i in getCandidates(n): for perm in set(permutations(i)): yield ''.join(perm) def getCandidates(n): for i in range(1, n): res = "1" * i + "0" * (n - i) yield res spam(4)
0
source

Or you can use recursion. This has the added benefit of being able to generate any n bits k of base number

 def bitStr(numDig, base): if numDig == 0: return [] if numDig == 1: return [str(i) for i in range(0,base)] return [ digit + bits for digit in bitStr(1, base)for bits in bitStr(numDig - 1, base)]

print (bitStr (4, 2))

0
source

More articles:


All Articles