fork(2) download
  1. def H(s, k):
  2. if k == 0:
  3. yield s # only one n-bit string has Hamming distance 0 from s (itself)
  4. elif s: # k > 0
  5. for s_k_minus_one_flipped in H(s[:-1], k - 1):
  6. yield s_k_minus_one_flipped + flip(s[-1]) # flip last bit
  7. for s_k_flipped in H(s[:-1], k):
  8. yield s_k_flipped + s[-1] # don't flip last bit
  9.  
  10.  
  11. def flip(bit):
  12. assert bit == "0" or bit == "1"
  13. return "0" if bit == "1" else "1"
  14.  
  15. import sys
  16. s, k = sys.stdin.read().split()
  17. print(" ".join(H(s, int(k))))
  18.  
Success #stdin #stdout 0.08s 10840KB
stdin
0000 2
stdout
0011 0101 1001 0110 1010 1100