Technique for cyclical iteration « Python recipes « ActiveState Code (original) (raw)

1 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."

  1. The output is split four ways: one returned result and three copies to feed back in.
  2. Each of the three copies is consumed in a generator of multiples.
  3. The combined result has 1 as a starting point and is followed by the merge of the multiples.
  4. 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)))