Source code online books for professionals by professionals

Listing 8-1.  A Naïve Solution to the Longest Increasing Subsequence Problem
from itertools import combinations
 
def naive_lis(seq):
    for length in range(len(seq), 0, -1):       # n, n-1, ... , 1
        for sub in combinations(seq, length):   # Subsequences of given length
            if list(sub) == sorted(sub):        # An increasing subsequence?
                return sub                      # Return it!
Don’t Repeat Yourself
You may have heard of the DRY principle: Don’t repeat yourself. It’s mainly used about your code, meaning that you 
should avoid writing the same (or almost the same) piece of code more than once, relying instead of various forms of 
abstraction to avoid cut-and-paste coding. It is certainly one of the most important basic principles of programming, 
but it’s not what I’m talking about here. The basic idea of this chapter is to avoid having your algorithm repeat itself. 
The principle is so simple, and even quite easy to implement (at least in Python), but the mojo here is really deep,  
as you’ll see as we progress.
But let’s start with a couple of classics: Fibonacci numbers and Pascal’s triangle. You may well have run into 
these before, but the reason that “everyone” uses them is that they can be pretty instructive. And fear not—I’ll put a 
Pythonic twist on the solutions here, which I hope will be new to most of you.

---

Chapter 8 
■
 tangled dependenCies and MeMoization 
165
The Fibonacci series of numbers is defined recursively as starting with two ones, with every subsequent number 
being the sum of the two previous. This is easily implemented as a Python function
3
:
 
>>> def fib(i):
...     if i < 2: return 1
...     return fib(i-1) + fib(i-2)
 
Let’s try it out:
 
>>> fib(10)
89
 
Seems correct. Let’s be a bit bolder:
 
>>> fib(100)
 
Uh-oh. It seems to hang. Something is clearly wrong. I’m going to give you a solution that is absolutely overkill 
for this particular problem but that you can actually use for all the problems in this chapter. It’s the neat little memo 
function in Listing 8-2. This implementation uses nested scopes to give the wrapped function memory—if you’d like, 
you could easily use a class with cache and func attributes instead.
Note
 
■
  there is actually an equivalent decorator in the 
functools
 module of the python standard library, called 
lru_cache
 (available since python 3.2, or in the package 
functools32
 for python 2.7
4
). if you set its 
maxsize
 argument 
to 
None
, it will work as a full memoizing decorator. it also provides a 
cache_clear
 method, which you could call between 
uses of your algorithm.