Classical FP problem in python : Hamming problem

[Steven Bethard]

Nick Craig-Wood wrote:
> Thinking about this some more leads me to believe a general purpose
> imerge taking any number of arguments will look neater, eg
> 
> def imerge(*generators):
>     values = [ g.next() for g in generators ]
>     while True:
>         x = min(values)
>         yield x
>         for i in range(len(values)):
>             if values[i] == x:
>                 values[i] = generators[i].next()
> 

This kinda looks like it dies after the first generator is exhausted, 
but I'm not certain.  An alternate version that doesn't search for 'i':

py> def imerge(*iterables):
...     iters = [iter(i) for i in iterables]
...     values = [i.next() for i in iters]
...     while iters:
...         x, i = min((val, i) for i, val in enumerate(values))
...         yield x
...         try:
...             values[i] = iters[i].next()
...         except StopIteration:
...         	del iters[i]
...         	del values[i]
...         	
py> list(imerge([1, 4, 7], [2, 5, 8], [3, 6, 9]))
[1, 2, 3, 4, 5, 6, 7, 8, 9]
py> list(imerge([3, 6, 9], [1, 4, 7], [2, 5, 8]))
[1, 2, 3, 4, 5, 6, 7, 8, 9]
py> list(imerge([1, 4, 7], [3, 6, 9], [2, 5, 8]))
[1, 2, 3, 4, 5, 6, 7, 8, 9]

> This means that this can be further simplified thus,
> 
> def hamming():
>     def _hamming():
>         yield 1
>         for n in imerge( imap(lambda h: 2*h, hamming2),
>                          imap(lambda h: 3*h, hamming3),
>                          imap(lambda h: 5*h, hamming5) ):
>             yield n
>     hamming2, hamming3, hamming5, result = tee(_hamming(), 4)
>     return result

Nice.

Steve