The hamming problem has an interesting variant. That is generating the numbers in ascending order (e.g. quoting wikipedia "regular numbers are often called Hamming numbers, after Richard Hamming, who proposed the problem of finding computer algorithms for generating these numbers in order.").
It turns out that a beautiful and compact solution is obtained by using 3 queues (Q2, Q3, Q5). The solution produces numbers in order and without duplicates. Time complexity is linear in the size output space. Hmm ... intuitively space should be constant in the output space, but still I need to think a bit about it... Here you have the C++ code for Hamming numbers in order and without duplicates. No need to explain the algorithm here since he code is self-explaining.
You should post code directly inline your articles. At least relevant sections. Otherwise, having to download a tgz, uncompress it and look at it means that 99% of the visitors will just walk away. Life is short.
ReplyDeleteAnyways, you should also post your result at http://lambda-the-ultimate.org/node/608 (discussions on LTU stay open pretty much for ever) for some beating and insights.