Welcome, guest | Sign In | My Account | Store | Cart

HammingNeighbors returns all integers that are k number of bits away (i.e. k Hamming distance away) from an integer.
The algorithm uses dynamic programming.

Python, 29 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def HammingNeighbors(n, dist, numBits):
    """Returns list of numbers that are given hamming distance away                                                                        
    from an integer.                                                                                                                       
                                                                                                                                           
    n : an integer                                                                                                             
    dist : Hamming distance                                                                                                                
    bits : number of bits of neighbors                                                                                                     
    """
    if dist < 0:
        raise Exception, 'Invalid distance'
    onesMask = int('1'*numBits, 2)

    # Cur array maintains the invariant that for some dist d,                                                                                  
    # Cur[i] holds all numbers that that are d distance                                                                                    
    # away from lower i-bits of n                                                                                                          

    # dist == 0                                                                                                                            
    Cur = [[n % (1 <<  _)] for _ in range(numBits+1)]
    # dist > 0
    for d in range(1, dist+1):
        Prev = Cur
        Cur = [[] for _ in range(numBits+1)]
        for i in range(d, numBits+1):
            # n's i-th bit and its inversion                                                                                               
            iBit = n & (1<<i-1)
            iBitInv = iBit ^ (1<<i-1)
            Cur[i] = [iBitInv + x for x in Prev[i-1]] + \
                     [iBit + x for x in Cur[i-1]]
    return Cur[numBits]

Sample usage:

>>> bin(20)
'0b10100'
>>> neighs = HammingNeighbors(20, 1, 8)                                                                                                
>>> [bin(n) for n in neighs]                                                                                                           
['0b10010100', '0b1010100', '0b110100', '0b100', '0b11100', '0b10000', '0b10110', '0b10101']                                           

>>> neighs = HammingNeighbors(20, 2, 8)                                                                                                
>>> len(neighs) # should equal to 8 choose 2                                                                                           
28                                                                                                                                     
>>> [bin(n) for n in neighs]                                                                                                           
['0b11010100', '0b10110100', '0b10000100', '0b10011100', '0b10010000', '0b10010110', '0b10010101', '0b1110100', '0b1000100', '0b1011100', '0b1010000', '0b1010110', '0b1010101', '0b100100', '0b111100', '0b110000', '0b110110', '0b110101', '0b1100', '0b0', '0b110', '0b101', '0b11000', '0b11110', '0b11101', '0b10010', '0b10001', '0b10111']
Created by Yong Shin on Thu, 17 Jan 2013 (MIT)
Python recipes (4591)
Yong Shin's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks