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.

### Like this:

Like Loading...

*Related*

This entry was posted on February 11, 2008 at 2:11 am and is filed under Programming, Python.

## Leave a Reply