#! /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