通过递归的锤击距离

Question

我有一个问题，我应该使用递归解决：

锤击距离。长度n的两个位字符串之间的锤距等于两个字符串不同的位数。编写一个程序，该程序在命令行中读取整数k和一些位字符串s，并打印出最多来自s k的所有位字符串。例如，如果k是2，并且s是0000，则您的程序应打印出来：

0011 0101 0110 1001 1010 1100

提示：选择s中的N位的k进行翻转。

我不知道从哪里开始可以指向我的方向正确？

Answer 1

要递归解决问题，您需要做一些少量的工作，使您可以将其分解为类似但较小的问题。

在您的情况下，您有一个字符串，即字符的顺序。与k个位置不同的一组琴弦由一些字符串组成，这些字符串首先与s一致或不同意。这有帮助吗？

Answer 2

代码如下。基本想法只是考虑字符串t = s [：-1]。您将所有与t的锤子距离的字符串与t的hamming距离相连，而t的翻转s [-1]，再加上与t [-1]相等k的所有字符串等于k [-1]。

def flip(c): return str(1-int(c))
def flip_s(s, i):
   t =  s[:i]+flip(s[i])+s[i+1:]
   return t
def hamming(s, k):
 if k>1:
      c = s[-1]
      s1 = [y+c for y in hamming(s[:-1], k)] if len(s) > k else []
      s2 = [y+flip(c) for y in hamming(s[:-1], k-1)]
      r = []
      r.extend(s1)
      r.extend(s2)
      return r
 else:
   return [flip_s(s,i) for i in range(len(s))]

>>> print hamming("0000", 2)
>>> ['1100', '1010', '0110', '1001', '0101', '0011']

Answer 3

让 H(s, k)是一组长度为 len(s)的位字符串 s的锤距离 k，然后我们可以轻松地使用较小的集合H(s[:-1], k-1)和H(s[:-1], k)，其中s[:-1]是 s没有最后一个字符：

def H(s, k):
    # invariant: H yields `len(s)`-bit strings that have k-bits flipped
    if len(s) < k:
        return  # produce nothing; can't flip k bits
    if k == 0:
        yield s  # only one n-bit string has Hamming distance 0 from s (itself)
    else:
        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"
print(" ".join(H("0000", 2)))
# -> 0011 0101 1001 0110 1010 1100

demo