Classical FP problem in python : Hamming problem
Steven Bethard
steven.bethard at gmail.com
Tue Jan 25 11:45:11 EST 2005
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
More information about the Python-list
mailing list