Welcome, guest | Sign In | My Account | Store | Cart

Algorithms and Data Structures assignment: make a recursive program that prints Pascal's Triangles upside down. I found it impossible at the time, but I just gave it another shot and solved it in 5min. Yay. P.S Optimisation took one day though.

Python, 56 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56``` ```#! /usr/bin/env python """ For a given number, prints Pascal's Triangle upside-down up to that line. Takes advantage of the fact that the Triangle is symmetric. Uses the combinatorics property of the Triangle: For any NUMBER in position INDEX at row ROW: NUMBER = C(ROW, INDEX) A hash map stores the values of the combinatorics already calculated, so the recursive function speeds up a little. Prints everything alligned at first, but starts screwing up at about 13. tn.pablo@gmail.com 03/09/07 """ import sys def comb(N, n, combs): """ Returns the value of C(N,n). First the function looks it up in a dictionary and only calculates if it isn't present, in which case it works recursively. """ try: ans = combs[(N,n)] except KeyError: if n == 0: ans=1 elif n == 1: ans=N else: ans = (comb(N, n-1, combs) * (N-n+1) * 1/n) combs[(N,n)] = ans return ans lines = int(sys.argv[1]) # stack that will contain the items of the row to be mirrored mirror = [] # dictionary of combinatoric-value pairs combs = {} for row in range(lines, -1, -1): # insert indentation print ' ' * (lines - row), # first half of the row limit = (row//2)+1 for index in range(limit): num = comb(row, index, combs) if not((row%2 == 0) and (index == limit-1)): mirror.append(num) print '%i ' % num, # for the second half, mirror the first while mirror: print '%i ' % mirror.pop(), print ```

This program is 75.89 times as efficent as my previous attempt at it (without a couple of optimisations).

Rogier Steehouder 15 years, 9 months ago

Memoize. You could use a simple memoize (see e.g. http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52201 ). Something like:

``````memo = {(0,0): 1, (1,0): 1, (1,1): 1}
def calcnum(row, index):
try:
return memo[(row, index)]
except KeyError:
pass

# Also set (row, row-index) since the triangle is symmetric
if col in (0, row):
# first and last column are 1
value = memo[(row, 0)] = memo[(row, row)] = 1
else:
value = memo[(row, index)] = memo[(row, row-index)] =\
calcnum(row - 1, index) + calcnum(row - 1, index- 1)
return value
``````
Steven Bethard 15 years, 9 months ago

calculate a row at a time. If you know you're calculating the whole triangle, you can do a row at a time. Of course, then there's really no point in using recursion:

``````def get_rows(depth):
rows = [[1]]
for i in xrange(depth - 1):
last_row = rows[-1]
new_row = [1]
for i in xrange(len(last_row) - 1):
new_row.append(last_row[i] + last_row[i + 1])
new_row.append(1)
rows.append(new_row)
return rows
``````
Pablo Torres (author) 15 years, 9 months ago

response. It isn't exactly the triangle I calculate recursively, it's the combinatorics. Besides, the assignment required recursion. I liked your solution though, faster than mine for sure.

Pablo Torres (author) 15 years, 9 months ago

response. The assignment required recursion :( I liked your solution though, faster than mine for sure.

Pablo Torres (author) 15 years, 9 months ago

response. My first version was your code without the memory/dictionary. You can imagine how slow it was.

Steven Bethard 15 years, 9 months ago

Did it say where it required recursion? Because you could certainly rewrite my for-loop recursively if necessary. (That is, have get_rows(n) call get_rows(n-1) and remove the loop.)

Pablo Torres (author) 15 years, 9 months ago

response. No, it didn't. I'll give your idea a try :)

Michael Puckett 12 years, 4 months ago

Old thread, but pascal's triangle was a challenge on a forum I frequent today and this is what I came up with:

``````def pascals_triangle(n):
x=[[1]]
for i in range(n-1):
x.append([sum(i) for i in zip([0]+x[-1],x[-1]+[0])])
return x

for x in pascals_triangle(10):
print('{0:^39}'.format(x))

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]
``````
 Created by Pablo Torres on Sun, 2 Sep 2007 (PSF)