Classical FP problem in python : Hamming problem

[Francis Girard]

Le mardi 25 Janvier 2005 09:01, Michael Spencer a écrit :
> Francis Girard wrote:
> > 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.
>

Yes, it's been fun.

> 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
>
>

Interesting idea.

> Regards
>
> Michael