Solution to the Hamming Number problem. Demonstrates a lazy evaluation evaluation technique using itertools.tee() to feed an iterator into itself. This is a common technique with Haskell. The deferred_output() function is the key technique for implementing a forward reference to the output of the stream.
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | from itertools import tee, chain, islice, groupby
from heapq import merge
def hamming_numbers():
# Generate "5-smooth" numbers, also called "Hamming numbers"
# or "Regular numbers". See: http://en.wikipedia.org/wiki/Regular_number
# Finds solutions to 2**i * 3**j * 5**k for some integers i, j, and k.
def deferred_output():
'Works like a forward reference to the "output" global variable'
for i in output:
yield i
result, p2, p3, p5 = tee(deferred_output(), 4) # split the output streams
m2 = (2*x for x in p2) # multiples of 2
m3 = (3*x for x in p3) # multiples of 3
m5 = (5*x for x in p5) # multiples of 5
merged = merge(m2, m3, m5)
combined = chain([1], merged) # prepend starting point
output = (k for k, v in groupby(combined)) # eliminate duplicates
return result
if __name__ == '__main__':
print(list(islice(hamming_numbers(), 1000))) # Show first 1000 hamming numbers
|
Problem statement (see http://en.wikipedia.org/wiki/Regular_number ) : "Output in ascending sequence all numbers which have only 2, 3, and 5 as non-trivial factors. The first such number is 1; and if x is any such number, so are 2x, 3x, and 5x. Use three generators to produce the multiples and feed them to a merge routine, then eliminate duplicates which ensures they are eventually output in ascending order."
- The output is split four ways: one returned result and three copies to feed back in.
- Each of the three copies is consumed in a generator of multiples.
- The combined result has 1 as a starting point and is followed by the merge of the multiples.
- Repeated values (runs of the same value) are eliminated.
The important part of the technique is the deferred_output function which lets you assume the result is known. Using those assumed values, the actual results get assigned to the output variable which is referred to by deferred_output. The tee itertool copies and splits-off the returned result from the buffered streams which are fed back into the multiple generators. The chain itertool loads the initial value to the result so that the cyclical iterator will have a starting point.
This is a general purpose technique. It is used extensively in Haskell programming language examples.
The same technique can be used for a fibonacci sequence (though there are much simpler ways to do it):
def fibonacci():
def deferred_output():
for i in output:
yield i
result, c1, c2 = tee(deferred_output(), 3)
paired = map(add, c1, islice(c2, 1, None))
output = chain([0, 1], paired)
return result
print(list(islice(fibonacci(), 50)))
I needed to change "i is not last" to "i != last" to get no_repeats() to work properly.
Could function deferred output be seen as a form of forward declaration of variable output, allowing it to be referenced before it is later assigned too?
P.S. this recipe inspired this
As written above, I get repeats in the sequence:
After making Mike's suggested change, the repeats disappear and the results tally with another generator using a different algorithm:
Very nice, Raymond.
This whole idea looks general&useful enough that may deserve some support in the language or in the itertools module, if possible.
(I'll need to work some on the D language standard library to allow similar things).
In that fibonacci() function this line:
paired = map(add, c1, islice(c2, 1, None))
Needs an imap() to work, instead of a map().
@bearophile: although not explicitely stated, this recipe seems to be using Python 3, where builtin map behaves like itertools.imap in 2.x But since that's the only place where the difference 2 vs 3 matters, a short comment in the code would be nice.