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 57
""" For a given number, prints Pascal's Triangle upside-down up to that line. Prints everything alligned at first, but starts screwing up at about 13. Some info: 0. Takes advantage of the fact that the Triangle is symmetric. 1. Uses the combinatorics property of the Triangle: For any NUMBER in position INDEX at row ROW: NUMBER = C(ROW, INDEX) 2. A dictionary stores the values of the combinatorics already calculated, so the comb function speeds up a little. Think of it as a recursive function with a memory. Pablo A. Torres Navarrete tn.pablo@gmail.com 03/09/07 """ #! /usr/bin/env python 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 works recursively. """ try: ans = combs[(N,n)] except KeyError: if n == 0: ans=1 elif n == 1: ans=N else: # A little maths... 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
Refactorings
No refactoring yet !
erokar
October 6, 2007, October 06, 2007 12:32, permalink
No rating.
Login to rate!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
def printLine(line): string = '' for l in line: string += str(l) + ' ' print string def pascal(numberOfLines): currentLine = [1] printLine(currentLine) newLine = [] for i in range(numberOfLines-1): for i in range(len(currentLine)-1): newLine.append(currentLine[i] + currentLine[i+1]) newLine.insert(0,1) # add the 1's at the beggining newLine.append(1) # and end of the line printLine(newLine) currentLine = newLine newLine = []
Anthony
October 15, 2007, October 15, 2007 03:14, permalink
No rating.
Login to rate!
Broke up of erokar's main pascal() function.
Made printLine and nextLine more functional in nature.
Seems to be a fair bit faster too, but I think that's just the new printLine.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
def printLine(line): print ' '.join([str(l) for l in line]) def nextLine(currentLine): return [1] + \ [currentLine[i] + currentLine[i+1] for i in range(len(currentLine)-1)] + \ [1] def pascal(numberOfLines): currentLine = [1] printLine(currentLine) for i in range(numberOfLines-1): newLine = nextLine(currentLine) printLine(newLine) currentLine = newLine if __name__ == '__main__': import sys pascal(int(sys.argv[1]))
dave
October 15, 2007, October 15, 2007 16:01, permalink
No rating.
Login to rate!
I figure the extra functions aren't needed.
1 2 3 4 5 6 7 8 9 10
def pascal(max): line = [1] while len(line)-1 < max: yield line line = [1] + [line[i] + line[i+1] for i in range(len(line)-1)] + [1] if __name__ == '__main__': import sys for line in pascal(int(sys.argv[1])): print ' '.join(map(str, line))
Anders Waldenborg
October 28, 2007, October 28, 2007 10:00, permalink
No rating.
Login to rate!
Just some minor improvement to Dave's code.
* Doesn't calculate an extra line that is thrown away.
* map(sum,zip(line[:-1],line[1:]))
instead of
[line[i] + line[i+1] for i in range(len(line)-1)
1 2 3 4 5 6 7 8 9 10
def pascal(nlines, line=[1]): yield line for x in xrange(nlines-1): line = [1] + map(sum,zip(line[:-1],line[1:])) + [1] yield line if __name__ == '__main__': import sys sys.stdout.writelines([(" ".join(map(str,x))+'\n') for x in pascal(int(sys.argv[1]))])
Algorithms and Data Structures assignment. At first I had no idea how to start this, but I nailed it at my second try. Yay.