<p>Edit: I'm wrong. In Mastermind, you also have knowledge of the number of colors that were right, but not in the right spot. That changes the number of possible solutions, so that there is no obvious exact translation between the two problems and so I can't make the conclusion below. Leaving the answer here for now, maybe it helps someone think about the problem.</p>

<p>I answered:</p>

<p>Bad news, it's at least NP-complete.</p>

<p>Your problem reminded me of the game <em>Mastermind</em> (<a href="http://en.wikipedia.org/wiki/Mastermind_%28board_game%29" rel="nofollow">Wikipedia</a>). On that page, they also mention the "Mastermind satisfiability problem: given a set of two-color Mastermind guesses and answers, is there a possible right guess?</p>

<p>So that problem has slightly more information than you: Mastermind gives number of correct colors in the right place (== length minus Hammond distance), plus the number of correct colors in the wrong place. And they only try to decide whether the number of possibilities is > 0. And that problem is NP-complete according to <a href="http://arxiv.org/abs/cs.CC/0512049" rel="nofollow">this paper</a>.</p>
How to speed up exponential time code
<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>