The following implementation is even more speaking as it makes self-evident and almost mechanical how to translate algorithms that run after their tail from recursion to "tee" usage :
Thanks, Francis and Jeff for raising a fascinating topic. I've enjoyed trying to get my head around both the algorithm and your non-recursive implementation.
Here's a version of your implementation that uses a helper class to make the algorithm itself prettier.
from itertools import tee, imap
def hamming():
def _hamming():
yield 1
for n in imerge(2 * hamming, imerge(3 * hamming, 5 * hamming)):
yield n hamming = Tee(_hamming())
return iter(hamming)
class Tee(object): """Provides an indepent iterator (using tee) on every iteration request Also implements lazy iterator arithmetic""" def __init__(self, iterator): self.iter = tee(iterator,1)[0] def __iter__(self): return self.iter.__copy__() def __mul__(self, number): return imap(lambda x: x * number,self.__iter__())
def imerge(xs, ys):
x = xs.next()
y = ys.next()
while True:
if x == y:
yield x
x = xs.next()
y = ys.next()
elif x < y:
yield x
x = xs.next()
else: # if y < x:
yield y
y = ys.next()>>> hg = hamming() >>> for i in range(10000): ... n = hg.next() ... if i % 1000 == 0: print i, n ... 0 1 1000 51840000 2000 8100000000 3000 279936000000 4000 4707158941350 5000 50960793600000 6000 409600000000000 7000 2638827906662400 8000 14332723200000000 9000 68024448000000000
Regards
Michael
-- http://mail.python.org/mailman/listinfo/python-list
