Today's problem is to generate the first 1000 numbers in the sequence of Hamming numbers. More information on Hamming numbers can be found at the Programming Praxis blog post.

When I first saw this problem my mind jumped right to an imperative way of solving it. Start building up a list of numbers, keep checking to see if I had a 1000, and then print the list. Although this would work, it didn't seem very Clojureish.

That's when I remebered lazy sequences. A lazy sequence will generate the numbers as I need them. Then I can just ask for a 1000 and it will generate a 1000 numbers (maybe a few more, but we'll never see these). Here's the code:

;;Hamming Numbers (defn hamming-generator ([] (hamming-generator (sorted-set 1))) ([some-set] (let [n (first some-set) s (disj some-set n)] (cons n (lazy-seq (hamming-generator (conj s (* n 2) (* n 3) (* n 5)))))))) (def hamming-numbers (take 1000 (hamming-generator)))

The first line in the function is there to seed the function with a "1". The real meat of the function goes like this: I bind the first value in the sorted set to `n`

and then I remove `n`

from the sorted set and bind the new set to `s`

. From there I create a `seq`

with `n`

at the front and a `lazy-seq`

representing the future values at the end. I don't get a stack overflow with the recursive call because `lazy-seq`

only calls `hamming-generator`

when a new number is needed. `lazy-seq`

caches the values from the previous calls to `hamming-generator`

and passes the last generated set to `hamming-generator`

to get the next value in the sequence. Nice and elegant and it does all the book keeping work for you!

I'm not pretty sure but in a first view

ReplyDeletes (disj some-set n)

is not the same than:

s (rest n) because n always is the first term...

It seem more clojureish

I decided to go with disj because I wanted to make sure I got a sorted set after removing the element. Doing a rest can change the collection so something else. Try:

ReplyDelete(type (sorted-set :a :b :c))

(type (disj (sorted-set :a :b :c) :a))

and

(type (rest (sorted-set :a :b :c)))