0

再帰を使用して解決することになっている問題があります。

ハミング距離。長さの 2 つのビット文字列間のハミング距離はn、2 つの文字列が異なるビット数に等しくなります。コマンド ラインから整数kとビット文字列を読み取り、sから最大 k 以下のハミング距離を持つすべてのビット文字列を出力するプログラムを作成しsます。たとえば、kis2とsis0000の場合、プログラムは次のように出力する必要があります。

0011 0101 0110 1001 1010 1100

ヒント:反転kするNビットを選択します。s

どこから始めればよいかわかりません。誰かが私を正しい方向に向けることができますか?

4

3 に答える 3

2

問題を再帰的に解決するには、問題を同様の、しかしより小さな問題に分解できるようにする、少量の作業を行う必要があります。

あなたの場合、あなたは文字列、すなわち文字のシーケンスを持っています。k個の場所でSと異なる文字列のセットは、最初にSに同意するか、または同意しないいくつかの文字列で構成されます。それは役に立ちますか？

于 2012-10-22T22:07:25.143 に答える
1

コードは次のとおりです。基本的な考え方は、文字列 t = s[:-1] を考慮することです。t に対して k-1 未満のハミング距離を持つすべての文字列を s[-1] のフリップで連結し、さらに t に対してハミング距離が k に等しいすべての文字列を 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 に答える