Created
January 11, 2014 10:50
-
-
Save regularcoder/8369386 to your computer and use it in GitHub Desktop.
Minimum Hamming Distance in Common Lisp
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;XOR p q => (p V q) ^ !(p ^ q) | |
(defun xor (p q) | |
(and | |
(or p q) | |
(not (and p q)) | |
) | |
) | |
;Represent a number as a boolean list | |
(defun getbinary (n) | |
(map | |
'list | |
;"111" becomes (T T T) | |
(lambda (x) | |
(if (eq #\1 x) t nil) | |
) | |
;7 becomes "111" | |
(format nil "~b" n))) | |
;Find hamming distance between two *binary* numbers using XOR | |
(defun hammingdistance (n1 n2) | |
(count t | |
(append | |
(map | |
'list | |
(lambda (x y) | |
(xor x y) | |
) | |
n1 | |
n2) | |
;map will not work when lists are not of the same length, | |
;we need to count extra digits in case of length differential. | |
;taking everything after certain point is fine | |
(nthcdr (length n1) n2) | |
(nthcdr (length n2) n1) | |
))) | |
;find minimum element in a list | |
(defun findmin (l &optional m) | |
(if l | |
(findmin | |
(cdr l) | |
(min | |
(car l) | |
;optional parameter is initially nil so | |
;we replace it first element of list | |
(if m m (car l)))) | |
;terminating condition | |
m)) | |
;gets all unique pairings between elements in a list | |
(defun uniquepairs (l) | |
(if l | |
(append | |
;start from beginning element and pair with every element *head* | |
;in (1, 2, 3), 1 gets paired with 2 and 3 in first iteration | |
(loop for x in (cdr l) | |
collect (list (car l) x)) | |
;generate pairs for remaining elements | |
(uniquepairs (cdr l))) | |
;terminating condition | |
nil)) | |
;find minimum hamming distance between any two elements in input list | |
;(minhd '(79 83)) => 3 | |
;(minhd '(13500 1935 9645 5790)) => 4 | |
(defun minhd (i) | |
(findmin | |
(map | |
'list | |
;input is a pair, list of two elements | |
(lambda (x) | |
(hammingdistance (getbinary (first x)) (getbinary (second x)))) | |
;generate a list of all possible pairings | |
(uniquepairs i)))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment