0

I have a problem I'm supposed to solve using recursion:

Hamming distance. The Hamming distance between two bit strings of length n is equal to the number of bits in which the two strings differ. Write a program that reads in an integer k and a bit string s from the command line, and prints out all bit strings that have Hamming distance at most k from s. For example if k is 2 and s is 0000 then your program should print out:

0011 0101 0110 1001 1010 1100

Hint: choose k of the N bits in s to flip.

I have no idea where to begin could someone point me in the right direction?

4

3 回答 3

2

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

在您的情况下，您有一个字符串，即一个字符序列。在 k 个位置与 S 不同的字符串集合由一些字符串组成，这些字符串要么首先同意 S，要么不同意。这有帮助吗？

于 2012-10-22T22:07:25.143 回答
1

代码如下。基本思想只是考虑字符串 t = s[:-1]。您将所有汉明距离小于 k-1 的字符串连接到 t 与 s[-1] 的翻转，再加上您将所有汉明距离等于 k ​​的字符串连接到 t 与 s[-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']
于 2012-10-22T22:12:10.623 回答
0

让一组长度为具有汉明距离的H(s, k)位串，然后我们可以使用较小的集合轻松计算它，其中没有 最后一个字符：len(s)ksH(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

演示

于 2012-10-23T03:58:45.393 回答