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<

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)

### Required Modules

• (none specified)