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:
>>
>>>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
More information about the Python-list
mailing list