Thoughts on Pascal’s triangle in Python

February 11, 2008

For a Project Euler problem I had to work on a generator for Pascal’s Triangle. Ultimately, it didn’t emerge as the right way to solve the problem, but I arrived at an interesting implementation that I’d like to share.

The naive implementation is:

def gen_pascal():
    last = []
    while True:
        n = len(last)
        row = [1]*(n+1)
        for i in range(1,n):
            row[i] = last[i-1]+last[i]
        last = row
        yield row
    return

This is pretty similar to any number of implementations you can find on the web. Works quite nicely, too, except it requires 2*n storage, which gets big if you’re interested in really large triangles.So I started thinking about automatic ways of generating only a row at a time, and yielding an iterator for that row rather than a list, to reduce the memory usage. Again, the obvious way to generate the elements are:

def fact(n):
    if n <= 0: return 1
    return prod(xrange(1,n+1))def combos(n,m): return fact(n)/fact(n-m)/fact(m)

def combos_slower(n,m):
    if m == 0 or n == m: return 1
    return combos(n-1,m-1)+combos(n-1,m)

def gen_pascal_row(n):
    for r in range(0,n+1):
        yield combos(n,r)
    return

So this version doesn’t use any memory, but actually takes a great deal of computation (roughly N^3??) per new element, which seems a bit wasteful, and starts to bog down even sooner than the naive version.

I played around with an alternate way to generate the combinations, in part inspired by the naive version:

 def combos_slower(n,m):
    if m == 0 or n == m: return 1
    return combos(n-1,m-1)+combos(n-1,m)

but, as the name implies, it was even slower still.

Ultimately I settled on this version:

def gen_pascal_row_fast(n):
    el = 1
    yield el
    for m in range(1,n+1):
        el = (el*(n-m+1))/m
        yield el
    return

which only takes 4 operations to make a new element, and no memory, which I think is pretty cool. Of course, I don’t kid myself that I’m the first one to think of this, but I still wanted to share it, especially since, as it turns out, I can’t use it for the problem I’m trying to solve in Project Euler.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: