title: How to speed up exponential time code
body: <p>I am writing a simulation. The problem I need to solve is as follows.</p>
  
  <p>I am given a random binary vector <code>t</code> (a list in python) of length <code>l</code>.    I then sample binary vectors of the same length and measure the Hamming distance (that is the number of aligned mismatches) between each of the sampled vectors and <code>t</code> and store the results.  I want to determine how many binary vectors of length l are compatible with the distances found so far.  Clearly <code>t</code> is but it is also likely many others are too.  </p>
  
  <p>My code is as follows.</p>
  
  <pre><code>import random
  import itertools
  import operator
  
  l=23
  t = [random.randint(0,1) for b in range(l)]
  stringsleft = set(itertools.product([0,1],repeat=l))
  
  xcoords = []
  ycoords = []
  iters = l
  for i in xrange(iters):
      print i, len(stringsleft)
      xcoords.append(i)
      ycoords.append(math.log(len(stringsleft)))
      pattern = [random.randint(0,1) for b in range(l)]
      distance = sum(itertools.imap(operator.ne, pattern, t))
      stringsleft = stringsleft.intersection(set([y for y in stringsleft if sum(itertools.imap(operator.ne, pattern, y)) == distance]))
  </code></pre>
  
  <p>Unfortunately it is very slow and uses a lot of memory and does not work at all if I increase l to 30. Is it possible to speed this up to solve the <code>l=30</code> case?</p>
  
  <p><strong>Update</strong><br>
  I made a small optimisation by replacing the lists by integers so now it runs with <code>l=26</code>.  </p>
  
  <pre><code>l=26
  t = random.randint(0,2**l)
  stringsleft = set(range(2**l))
  xcoords = []
  ycoords = []
  iters = l
  for i in xrange(iters):
      print i, len(stringsleft)
      if (len(stringsleft) &gt; 1):
          xcoords.append(i)
          ycoords.append(math.log(len(stringsleft),2))
      pattern = random.randint(0,2**l)
      distance = bin(pattern ^ t).count('1')
      stringsleft = stringsleft.intersection(set([y for y in stringsleft if bin(pattern ^ y).count('1') == distance]))
  </code></pre>
  
  <p>The problem that stops me getting to <code>l=30</code> is RAM usage rather than time.    </p>