language: Python (python 2.7.3)
date: 208 days 4 hours ago
link:
visibility: private 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def H(s, k):
    if k == 0:
        yield s  # only one n-bit string has Hamming distance 0 from s (itself)
    elif s: # k > 0
        for s_k_minus_one_flipped in H(s[:-1], k - 1):
            yield s_k_minus_one_flipped + flip(s[-1])  # flip last bit
        for s_k_flipped in H(s[:-1], k):
            yield s_k_flipped + s[-1]  # don't flip last bit
 
 
def flip(bit):
    assert bit == "0" or bit == "1"
    return "0" if bit == "1" else "1"
 
import sys
s, k = sys.stdin.read().split()
print(" ".join(H(s, int(k))))