問題
今日はFind a rotation with maximum hamming distanceに挑戦する。この問題は、リストをローテーションさせて ハミング距離の最大値を見つけるという問題。ハミング距離というのは、等しい文字数を持つ二つの文字列の中で、対応する位置にある異なった文字の個数のことをいう。例えば、下記のような場合、ハミング距離は2になる。
1011101 1001001 Maximum Hamming distance is 2
ということで、今回の問題は、リストをローテーションさせてハミング距離が最大値を探す問題。
input: 2480 Comparison1: 0248 Comparison2: 8024 Comparison3: 4802 Maximum Hamming distance is 4
実装
方針としては、元のリストと回転させたリストを用意して、インデックスを動かしなら、異なるかどうかを判定するような方法もありだけど、ここで紹介されているのは、前回の記事で説明したリストの拡張を行うことで、ローテーションしたとみなせるという方法。なので、今回はそれを活かした方法でチャレンジ。
たとえば、元のリストが121の場合、拡張リストは121121となる。211、112をチェックし、ハミング距離が最大になる値を探す。イメージは下記の通り。
from typing import List
def maxHamming(numbers: List[int]) -> int:
len_numbers = len(numbers)
tmp = [0] * (2 * len_numbers)
for i in range(len_numbers):
tmp[i] = tmp[len_numbers + i] = numbers[i]
maxHam = 0
for i in range(1, len_numbers):
currHam = 0
k = 0
for j in range(i, i + len_numbers):
if numbers[k] != tmp[j]:
currHam += 1
k += 1
if currHam == len_numbers:
return len_numbers
maxHam = max(maxHam, currHam)
return maxHam
if __name__ == '__main__':
numbers = [1,2,1]
print(maxHamming(numbers))
numbers = [2,4,8,0]
print(maxHamming(numbers))
2
4
