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).

8 comments

Rogier Steehouder 16 years, 7 months ago  # | flag

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 16 years, 7 months ago  # | flag

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) 16 years, 6 months ago  # | flag

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) 16 years, 6 months ago  # | flag

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

Pablo Torres (author) 16 years, 6 months ago  # | flag

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

Steven Bethard 16 years, 6 months ago  # | flag

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) 16 years, 6 months ago  # | flag

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

Michael Puckett 13 years, 2 months ago  # | flag

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)
Python recipes (4591)
Pablo Torres's recipes (1)

Required Modules

Other Information and Tasks