Skip to content

Instantly share code, notes, and snippets.

@mdogo
Last active October 22, 2022 12:10
Show Gist options
  • Save mdogo/dd267c5358b06c1e8990 to your computer and use it in GitHub Desktop.
Save mdogo/dd267c5358b06c1e8990 to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment