Hamming numbers are those with no prime factors other than 2, 3 or 5.
So 10, 15, and 30 are Hamming numbers, but 21 is not. How can you
efficiently implement (hamming n) in lisp?
It seems natural to do a recursive solution- the hamming numbers are 1
and 2, 3, or 5 times some other hamming number. Autrijus Tang solved
it in Haskell this way:
main = print (take 1000 hamming)
hamming = 1 : map (2*) hamming ~~ map (3*) hamming ~~ map (5*) hamming
where
···@(x:xs) ~~ ···@(y:ys) -- To merge two streams:
| x==y = (x : xs~~ys) -- if the heads are common, take that
| x<y = (x : xs~~yys) -- otherwise, take the smaller one
| x>y = (y : xxs~~ys) -- and proceed to merge the rest
The best I can do is this one:
(defun nhammings (twos threes fives tail n out)
(if (= n 0)
out
(let* ((2l (* 2 (car twos)))
(3l (* 3 (car threes)))
(5l (* 5 (car fives)))
(next (min 2l 3l 5l)))
(progn (setf (cdr tail) (cons next ()))
(let ((out2 (if (= next 2l) (cdr twos) twos))
(out3 (if (= next 3l) (cdr threes) threes))
(out5 (if (= next 5l) (cdr fives) fives)))
(nhammings out2 out3 out5 (cdr tail) (1- n) out))))))
(defun nHammingNums (n)
(let ((res (list 1)))
(nhammings res res res res (1- n) res)
(nth n res))
This just seems like a lot of manual labor-I mean, I have 5 pointers
into the same list, which is a bit ugly. What is the better way?
Also, should I have collapsed the let* and the let into a single let*,
or perhaps broke it into 2-3 lets?
Thank you both-I had not considered writing hamming-p. There is indeed
more than one way to skin a cat. and pascal-I had gotten correct
results (other than non-termination for n=0) when I ran the code on
clisp 2.33.2-r2 -which lisp did you get those results on?
I think Hamming's original puzzle was to enumerate the
Hamming numbers in order.
I think the key idea is merging an ordered list of numbers,
remembering that they represent sets, so duplicates must be
discarded. This is a straight forward exercise in recursion.
CL-USER> (defun mosen (u v)
"Merge Ordered SEt of Numbers"
(cond ((endp u) v)
((endp v) u)
((= (car u)(car v))(mosen (cdr u) v))
((< (car u)(car v))(cons (car u)
(mosen (cdr u) v)))
((> (car u)(car v))(cons (car v)
(mosen u (cdr v))))))
I like to keep lambda and function out of the main body of
my code by hiding lambda in little function builders
CL-USER> (defun multiply-by (n)
(lambda(x)(* x n)))
Then one might wonder what is so special about
2,3,5. Presumably the code should work for any set of
factors
CL-USER> (defun hammer(factors)
"Return a closure that generates Hamming numbers"
(let ((pending '(1)))
(lambda()
(prog1 (car pending)
(setf pending
(mosen (cdr pending)
(mapcar (multiply-by (car pending))
factors)))))))
CL-USER> (let ((2&3 (hammer '(2 3)))
(|2,3,5| (hammer '(2 3 5)))
(|2,3,5,7| (hammer '(2 3 5 7))))
(dotimes (i 20)
(format t "~&~3D ~3D ~3D ~3D"
i
(funcall 2&3)
(funcall |2,3,5|)
(funcall |2,3,5,7|))))
0 1 1 1
1 2 2 2
2 3 3 3
3 4 4 4
4 6 5 5
5 8 6 6
6 9 8 7
7 12 9 8
8 16 10 9
9 18 12 10
10 24 15 12
11 27 16 14
12 32 18 15
13 36 20 16
14 48 24 18
15 54 25 20
16 64 27 21
17 72 30 24
18 81 32 25
19 96 36 27
I just realised that mosen is a one-liner
CL-USER> (defun mosen (u v)
(remove-duplicates (merge 'list u v #'<)))
I can get away with '(1) instead of (list 1) even though
merge is destructive because I merge (cdr '(1)). Thereafter
I merge the fresh lists made by mapcar and merge.
Alan Crowe
Edinburgh
Scotland
···········@gmail.com writes:
> Thank you both-I had not considered writing hamming-p. There is indeed
> more than one way to skin a cat. and pascal-I had gotten correct
> results (other than non-termination for n=0) when I ran the code on
> clisp 2.33.2-r2 -which lisp did you get those results on?
clisp-2.35 -ansi
Perhaps there was copy-and-paste problems, at least one paren was
missing in your post.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Small brave carnivores
Kill pine cones and mosquitoes
Fear vacuum cleaner
matthewknox wrote:
> It seems natural to do a recursive solution- the hamming
> numbers are 1 and 2, 3, or 5 times some other hamming
> number.
CL-USER> (defun hamming(n)
(flet ((ham (p)
"True if n is p times a hamming number"
(and (zerop (mod n p))
(hamming (/ n p)))))
(and (plusp n)
(or (= n 1)
(ham 2)
(ham 3)
(ham 5)))))
HAMMING
CL-USER> (dotimes (i 30)
(format t "~&~A ~A" i (hamming i)))
0 NIL
1 T
2 T
3 T
4 T
5 T
6 T
7 NIL
8 T
9 T
10 T
11 NIL
12 T
13 NIL
14 NIL
15 T
16 T
17 NIL
18 T
19 NIL
20 T
21 NIL
22 NIL
23 NIL
24 T
25 T
26 NIL
27 T
28 NIL
29 NIL
Alan Crowe
Edinburgh
Scotland
···········@gmail.com writes (a while ago; I tend to check c.l.l
about once a week...):
> Hamming numbers are those with no prime factors other than 2, 3 or 5.
> So 10, 15, and 30 are Hamming numbers, but 21 is not. How can you
> efficiently implement (hamming n) in lisp?
(This is a problem that suits a lazy language like Haskell
exceptionally well.) Here's an efficient-ish and more general
solution is Lisp; the list manipulation, trying quite hard to
avoid excess consing, is pretty ugly and can surely be done better.
It can certainly be made much nicer if you don't mind consing
more.
(defun enumerate-products (f &rest numbers)
"Call F once for each positive integer that's a product
of things from NUMBERS, perhaps with repetitions, in
ascending order. If F ever returns something true, stop."
(let ((pending (list 1)))
(loop
(let ((n (first pending)))
(when (funcall f n) (return))
;; now merge multiples of N into PENDING.
(let ((tail pending))
(loop for k in numbers do
(let ((m (* n k)))
;; invariants:
;; - TAIL isn't null
;; - everything up to LAST is known < M
(loop while (and (rest tail)
(> m (second tail))) do
(setf tail (cdr tail)))
(unless (and (rest tail)
(= (second tail) m))
(setf (rest tail) (cons m (rest tail))))))))
(setf pending (rest pending)))))
But we're really working with a priority queue here, and
a list isn't obviously the right data structure for that.
--
Gareth McCaughan
.sig under construc