Classical FP problem in python : Hamming problem

[Nick Craig-Wood]

Steven Bethard <steven.bethard at gmail.com> wrote:
>  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.

Yes it will stop iterating then (rather like zip() on lists of unequal
size). Not sure what the specification should be!  It works for the
hamming problem though.

>>> list(imerge(iter([1, 2]), iter([1, 2, 3]), iter([1, 2, 3, 4])))
[1, 2]

> 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 isn't quite right...

>>> list(imerge([1, 2, 3], [1, 2, 3], [1, 2, 3]))
[1, 1, 1, 2, 2, 2, 3, 3, 3]

This should produce
[1, 2, 3]

So I'm afraid the searching *is* necessary - you've got to find all
the generators with the min value and move them on.

-- 
Nick Craig-Wood <nick at craig-wood.com> -- http://www.craig-wood.com/nick