Classical FP problem in python : Hamming problem

[Michael Spencer]

Nick Craig-Wood wrote:
> 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.
> 
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