# Classical FP problem in python : Hamming problem

Michael Spencer mahs at telcopartners.com
Tue Jan 25 14:06:56 EST 2005

```Nick Craig-Wood wrote:
> Steven Bethard <steven.bethard at gmail.com> wrote:
>
>> Nick Craig-Wood wrote:
>>
>>>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.
>
Here's a dict-based implementation: cute, but slow, at least for a small number
of iterators

>>> def imerge(*iterables):
...     cache = {}
...     iterators = map(iter,iterables)
...     number = len(iterables)
...     exhausted = 0
...     while 1:
...         for it in iterators:
...             try:
...                 cache.setdefault(it.next(),[]).append(it)
...             except StopIteration:
...                 exhausted += 1
...                 if exhausted == number:
...                     raise StopIteration
...         val = min(cache)
...         iterators = cache.pop(val)
...         yield val

>>> list(imerge([1, 2, 3, 6], [1, 2, 3, 7], [1, 2, 3, 4, 5]))
[1, 2, 3, 4, 5, 6, 7]
>>>

Michael

```