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
Download
Copy to clipboard1 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']
