改变汉明距离

Question

我想通过添加尽可能少的部分来找到改变字符串之间汉明距离的方法。我应该使用稀疏树和深度首次搜索，但我真的不知道我将如何使用它。

Answer 1

你可以玩这个代码。它计算列表中每对字符串之间的汉明距离（如果是二进制字符串）。如果距离小于最小阈值，则只修改两个字符串中的一个，直到达到最小距离。这是不正确的，因为修改对中的一个字符串会导致对一个字符串进行更多修改，所以更好的解决方案将修改一个字符串，然后再次修改另一个字符串。但是如果这看起来像你所需要的，你可以修复那个。

import Levenshtein as lv 

min_distance = 3 
numbers = {'1100010' ,'1001101', '1111111', '1111101', '1101001'} 

for number in numbers: 
    other_numbers = numbers - {number} 
    for other_number in other_numbers: 
     distance = lv.hamming(number, other_number) 
     backup_other_number = other_number 
     while lv.hamming(number, other_number) < min_distance: 
      for count, (a, b) in enumerate(zip(number, other_number)): 
       if a == b: 
        other_number = ''.join([ 
         n if c != count else str(int(a != '1')) 
         for c, n in enumerate(other_number) 
        ]) 
       if lv.hamming(number, other_number) >= min_distance: 
        break 
     print 'Old pair: {0}, distance: {1}'.format(
      (number, backup_other_number), 
      distance 
     ) 
     print 'New pair: {0}, distance: {1}'.format(
      (number, other_number), 
      lv.hamming(number, other_number) 
     ) 
    print '=' * 80 

输出：

(tmp)➜ ~ python hamming.py 
Old pair: ('1001101', '1111101'), distance: 2 
New pair: ('1001101', '0111101'), distance: 3 
Old pair: ('1001101', '1111111'), distance: 3 
New pair: ('1001101', '1111111'), distance: 3 
Old pair: ('1001101', '1100010'), distance: 5 
New pair: ('1001101', '1100010'), distance: 5 
Old pair: ('1001101', '1101001'), distance: 2 
New pair: ('1001101', '0101001'), distance: 3 
================================================================================ 
Old pair: ('1111101', '1001101'), distance: 2 
New pair: ('1111101', '0001101'), distance: 3 
Old pair: ('1111101', '1111111'), distance: 1 
New pair: ('1111101', '0011111'), distance: 3 
Old pair: ('1111101', '1100010'), distance: 5 
New pair: ('1111101', '1100010'), distance: 5 
Old pair: ('1111101', '1101001'), distance: 2 
New pair: ('1111101', '0101001'), distance: 3 
================================================================================ 
Old pair: ('1111111', '1001101'), distance: 3 
New pair: ('1111111', '1001101'), distance: 3 
Old pair: ('1111111', '1111101'), distance: 1 
New pair: ('1111111', '0011101'), distance: 3 
Old pair: ('1111111', '1100010'), distance: 4 
New pair: ('1111111', '1100010'), distance: 4 
Old pair: ('1111111', '1101001'), distance: 3 
New pair: ('1111111', '1101001'), distance: 3 
================================================================================ 
Old pair: ('1100010', '1001101'), distance: 5 
New pair: ('1100010', '1001101'), distance: 5 
Old pair: ('1100010', '1111101'), distance: 5 
New pair: ('1100010', '1111101'), distance: 5 
Old pair: ('1100010', '1111111'), distance: 4 
New pair: ('1100010', '1111111'), distance: 4 
Old pair: ('1100010', '1101001'), distance: 3 
New pair: ('1100010', '1101001'), distance: 3 
================================================================================ 
Old pair: ('1101001', '1001101'), distance: 2 
New pair: ('1101001', '0001101'), distance: 3 
Old pair: ('1101001', '1111101'), distance: 2 
New pair: ('1101001', '0111101'), distance: 3 
Old pair: ('1101001', '1111111'), distance: 3 
New pair: ('1101001', '1111111'), distance: 3 
Old pair: ('1101001', '1100010'), distance: 3 
New pair: ('1101001', '1100010'), distance: 3 
================================================================================ 
(tmp)➜ ~ 
(tmp)➜ ~ python hamming.py 
Old pair: ('1001101', '1111101'), distance: 2 
New pair: ('1001101', '0111101'), distance: 3 
Old pair: ('1001101', '1111111'), distance: 3 
New pair: ('1001101', '1111111'), distance: 3 
Old pair: ('1001101', '1100010'), distance: 5 
New pair: ('1001101', '1100010'), distance: 5 
Old pair: ('1001101', '1101001'), distance: 2 
New pair: ('1001101', '0101001'), distance: 3 
================================================================================ 
Old pair: ('1111101', '1001101'), distance: 2 
New pair: ('1111101', '0001101'), distance: 3 
Old pair: ('1111101', '1111111'), distance: 1 
New pair: ('1111101', '0011111'), distance: 3 
Old pair: ('1111101', '1100010'), distance: 5 
New pair: ('1111101', '1100010'), distance: 5 
Old pair: ('1111101', '1101001'), distance: 2 
New pair: ('1111101', '0101001'), distance: 3 
================================================================================ 
Old pair: ('1111111', '1001101'), distance: 3 
New pair: ('1111111', '1001101'), distance: 3 
Old pair: ('1111111', '1111101'), distance: 1 
New pair: ('1111111', '0011101'), distance: 3 
Old pair: ('1111111', '1100010'), distance: 4 
New pair: ('1111111', '1100010'), distance: 4 
Old pair: ('1111111', '1101001'), distance: 3 
New pair: ('1111111', '1101001'), distance: 3 
================================================================================ 
Old pair: ('1100010', '1001101'), distance: 5 
New pair: ('1100010', '1001101'), distance: 5 
Old pair: ('1100010', '1111101'), distance: 5 
New pair: ('1100010', '1111101'), distance: 5 
Old pair: ('1100010', '1111111'), distance: 4 
New pair: ('1100010', '1111111'), distance: 4 
Old pair: ('1100010', '1101001'), distance: 3 
New pair: ('1100010', '1101001'), distance: 3 
================================================================================ 
Old pair: ('1101001', '1001101'), distance: 2 
New pair: ('1101001', '0001101'), distance: 3 
Old pair: ('1101001', '1111101'), distance: 2 
New pair: ('1101001', '0111101'), distance: 3 
Old pair: ('1101001', '1111111'), distance: 3 
New pair: ('1101001', '1111111'), distance: 3 
Old pair: ('1101001', '1100010'), distance: 3 
New pair: ('1101001', '1100010'), distance: 3 
================================================================================