codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
; minimum hamming distance (define (logand a b) (if (or (zero? a) (zero? b)) 0 (+ (* (logand (floor (/ a 2)) (floor (/ b 2))) 2) (if (or (even? a) (even? b)) 0 1)))) (define (logxor a b) (cond ((zero? a) b) ((zero? b) a) (else (+ (* (logxor (floor (/ a 2)) (floor (/ b 2))) 2) (if (even? a) (if (even? b) 0 1) (if (even? b) 1 0)))))) (define (ash int cnt) (if (negative? cnt) (let ((n (expt 2 (- cnt)))) (if (negative? int) (+ -1 (quotient (+ 1 int) n)) (quotient int n))) (* (expt 2 cnt) int))) (define (pop-count n) (let loop ((n n) (count 0)) (if (zero? n) count (loop (ash n -1) (+ count (logand n 1)))))) (define (hamming xs) (pop-count (apply logxor xs))) (define (pairings xs) (let loop1 ((xs xs) (zs (list))) (if (null? xs) (reverse zs) (let loop2 ((ys (cdr xs)) (zs zs)) (if (null? ys) (loop1 (cdr xs) zs) (loop2 (cdr ys) (cons (list (car xs) (car ys)) zs))))))) (define (min-hamm xs) (apply min (map hamming (pairings xs)))) (display (hamming '(79 83))) (newline) (display (min-hamm '(13500 1935 9645 5790))) (newline)
Private
[
?
]
Run code
Submit