Itertools examples with Fibonacci Sequence

fibonacci_itertools.md

By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two. The recursive definition of the fibonacci number in Python is:

def fiboncci(n):
    if n == 0:
      return 0
    elif n == 1:
      return 1
    else
      return fibonacci(n-1) + fibonacci(n-2) 

In Python, we can get the n first fibonacci numbers this way:

def fibonacci(n):
    a, b = 0, 1
    sequence = []
    for i in xrange(n):
        sequence.append(a)
        a, b = b, a + b
    return sequence 

This is a very simple way to obtain n first fibonacci number. First, we set the seed values fibonacci(0) = 0, fiboncci(1) = 1 then, append the fibonacci numbers to list.

We can improve this function with generators:

def fibonacci(n):
    a, b = 0, 1
    for i in xrange(n):
        yield a
        a, b = b, a + b 

This improvement is easier, shorter and more efficient. It works like the last function but instead of returning a list it returns a generator.

Let's change the for loop for a infinite loop:

def fibonacci():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b 

We can not use it like in for i in fibonacci() because it will run forever but we can do a couple of nice things using itertools.

• islice; we can slice the generator using this function. For example, we can obtain the n first fibonacci numbers like:

  for i in islice(fibonacci(), n):
      print i

• takewhile; we can also obtain all the fibonacci numbers until a condition fails, for example all the numbers less than n:

  for i in takewhile(lambda x: x < n, fibonacci()):
      print i

• dropwhile; this function is just the opposite of takewhile. Instead of returning the numbers until a condition fails, it returns the numbers starting when the condition fails. An example, all the fibonacci numbers greater than n:

  for i in dropwhile(lambda x: x < n, fibonacci()):
      print i

• ifilter; very similar to takewhile. It returns every number that fulfill a condition. To get every odd number in the fibonacci sequence:

  for i in ifilter(lambda x: x % 2, fibonacci()):
      print i

  There is an opposite function to ifilter, ifilterfalse, that returns every number that does not fulfill a condition. Same example as before, to get even numbers:

  for i in ifilterfalse(lambda x: x % 2, fibonacci()):
      print i

• chain; get the numbers for one sequence then the numbers for another sequence. We are going to do a more complex example this time, get the odd fibonacci numbers then the even numbers:

  odd = ifilter(lambda x: x % 2, fibonacci())
  even = ifilterfalse(lambda x: x % 2, fibonacci())
  for i in chain(odd, even):
      print i

• tee; the thing with generators is that we can iterate them just once. What happens when we want to use the same generator two times? We can use tee, that makes n independent "copies" from a single iterator. For example, we want to obtain the even and odd numbers from the n first fibonacci numbers;

  generator1, generator2 = tee(islice(fibonacci(), n))
  for i in ifilterfalse(lambda x: x % 2, generator1):
      print i
  for i in ifilter(lambda x: x % 2, generator2):
      print i

• compress; we want the first, third and sixth numbers in the fibonacci sequence. We can use compress instead of casting the generator to a list:

  for i in compress(fibonacci(), [1, 1, 0, 0, 0, 1]:
      print i

• groupby; if we want to make a dictionary with the fibonacci numbers grouped by which are even or odd, we can use groupby.

  for k,i in groupby(fibonacci(), lambda x: 'odd' if x % 2 else 'even'):
      for v in i:
          groups.setdefault(k, []).append(v)

• imap; imap is like map but stop in the shortest iterable instead of filling in None. For example, to obtain fibonacci numbers squared we can use this:

  for i in imap(pow, fibonacci(), repeat(2)):
      print i

• izip; returns a iterator of tuples where the n tuple contains the nth element from each argument. For example, we can obtain the fibonacci numbers with the position in the sequence for each number.

  for i in izip(fibonacci(), count(1)):
      print i

• izip_longest; like the izip function, instead it does not stop with the shortest iterable. When the shortest iterable is exhausted the function uses some value to fill its space.

• starmap; works like imap but instead of receiving n arguments it uses a list of iterators as arguments for the function. We can copy the functionality of imap example using izip and startmap.

  for i in starmap(pow, izip(fibonacci(), repeat(2))):
      print i