Itertools examples with Fibonacci Sequence

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
```

mdogo/fibonacci_itertools.md