Create a list of all strings within hamming distance of a reference string with a given alphabet
Your strategy here is to keep a working set and repeatedly expand it by adding strings within Hamming distance 1 of elements in the set. This involves a lot of duplicated work, because the same candidate strings are going to be generated many times over (and then thrown away because they are already members of the working set).

I find that I get a substantial speedup just by generating each string exactly once.

from itertools import chain, combinations, product

def hamming_circle(s, n, alphabet):
    """Generate strings over alphabet whose Hamming distance from s is
    exactly n.

    &gt;&gt;&gt; sorted(hamming_circle('abc', 0, 'abc'))
    ['abc']
    &gt;&gt;&gt; sorted(hamming_circle('abc', 1, 'abc'))
    ['aac', 'aba', 'abb', 'acc', 'bbc', 'cbc']
    &gt;&gt;&gt; sorted(hamming_circle('aaa', 2, 'ab'))
    ['abb', 'bab', 'bba']

    """
    for positions in combinations(range(len(s)), n):
        for replacements in product(range(len(alphabet) - 1), repeat=n):
            cousin = list(s)
            for p, r in zip(positions, replacements):
                if cousin[p] == alphabet[r]:
                    cousin[p] = alphabet[-1]
                else:
                    cousin[p] = alphabet[r]
            yield ''.join(cousin)

def hamming_ball(s, n, alphabet):
    """Generate strings over alphabet whose Hamming distance from s is
    less than or equal to n.

    &gt;&gt;&gt; sorted(hamming_ball('abc', 0, 'abc'))
    ['abc']
    &gt;&gt;&gt; sorted(hamming_ball('abc', 1, 'abc'))
    ['aac', 'aba', 'abb', 'abc', 'acc', 'bbc', 'cbc']
    &gt;&gt;&gt; sorted(hamming_ball('aaa', 2, 'ab'))
    ['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba']

    """
    return chain.from_iterable(hamming_circle(s, i, alphabet)
                               for i in range(n + 1))


In pure Python, this runs about 4 times as fast as the code in the original post.