Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

all permutations of a binary sequence x bits long

I would like to find a clean and clever way (in python) to find all permutations of strings of 1s and 0s x chars long. Ideally this would be fast and not require doing too many iterations...

So, for x = 1 I want: ['0','1'] x =2 ['00','01','10','11']

etc..

Right now I have this, which is slow and seems inelegant:

    self.nbits = n     items = []     for x in xrange(n+1):         ones = x         zeros = n-x         item = []         for i in xrange(ones):             item.append(1)         for i in xrange(zeros):             item.append(0)         items.append(item)     perms = set()     for item in items:         for perm in itertools.permutations(item):             perms.add(perm)     perms = list(perms)     perms.sort()     self.to_bits = {}     self.to_code = {}     for x in enumerate(perms):         self.to_bits[x[0]] = ''.join([str(y) for y in x[1]])         self.to_code[''.join([str(y) for y in x[1]])] = x[0] 
like image 408
ComputationalSocialScience Avatar asked Feb 08 '11 00:02

ComputationalSocialScience


2 Answers

itertools.product is made for this:

>>> import itertools >>> ["".join(seq) for seq in itertools.product("01", repeat=2)] ['00', '01', '10', '11'] >>> ["".join(seq) for seq in itertools.product("01", repeat=3)] ['000', '001', '010', '011', '100', '101', '110', '111'] 
like image 64
Josh Bleecher Snyder Avatar answered Oct 05 '22 20:10

Josh Bleecher Snyder


There's no need to be overly clever for something this simple:

def perms(n):     if not n:         return      for i in xrange(2**n):         s = bin(i)[2:]         s = "0" * (n-len(s)) + s         yield s  print list(perms(5)) 
like image 31
Glenn Maynard Avatar answered Oct 05 '22 20:10

Glenn Maynard