You need to generate Pascal's Triangle in Python, and you're lazy (an admirable trait). Alternatively, you're looking for a Pascal's Triangle generator that can show really high-ranking rows, ones with multi-hundred-digit (or multi-million-digit) coefficients.
Solution
Here's the essential, unadorned code:
def pascal(n): """ Yield up to row ``n`` of Pascal's triangle, one row at a time. The first row is row 0. """ def newrow(row): "Calculate a row of Pascal's triangle given the previous one." prev = 0 for x in row: yield prev + x prev = x yield 1 prevrow = [1] yield prevrow for x in xrange(n): prevrow = list(newrow(prevrow)) yield prevrow
Discussion
It all revolves around the auxilliary function newrow(), which generates a row of Pascal's triangle given the previous one. We bootstrap it with the 0-th row, [1], and then we iterate, cascading out new rows.
The return value of pascal() is a generator of lists, one list to a row, starting with row 0. If you'd rather have a list of lists, you simply call list(pascal(x)).
Python generators are speedy beasts. On my desktop computer, pascal(1000) runs in 0.3 seconds, yielding the first 1,001 rows of the triangle — and remember, you need Arbitrary-precision arithmetic (aka bignums) to calculate the coefficients of most of these rows.
In fact, pascal(35) is the biggest triangle a C implementation using 32-bit unsigned int numbers can generate. Even with 64-bit integers, C can handle up to pascal(68). The beauty of Python for numerical recipes like this is that it switches seamlessly to bignums whenever it's necessary. This is a serious boon when it comes to factorially-exploding results like this one. For your information, the highest coefficient in pascal(1000) is a 300-digit integer.
Extensions
This version includes an example (and doctest), and checks the value of n for correctness:
def pascal(n): """ Yield up to row ``n`` of Pascal's triangle, one row at a time. The first row is row 0. >>> list (pascal (0)) [ [1] ] >>> list (pascal (1)) [ [1], [1, 1]] >>> list (pascal (4)) [ [1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1] ] >>> list (pascal (-1)) Traceback (most recent call last): ValueError: n must be an integer >= 0 """ if not isinstance(n, int): raise TypeError('n must be an integer') if n < 0: raise ValueError('n must be an integer >= 0') def newrow(row): "Calculate a row of Pascal's triangle given the previous one." prev = 0 for x in row: yield prev + x prev = x yield 1 prevrow = [1] yield prevrow for x in xrange(n): prevrow = list(newrow(prevrow)) yield prevrow
In all other aspects, this is identical to the first implementation.


Comments
I'm not really familiar with
I'm not really familiar with the yield function, so could you help me out by explaining how the code works? I find the simpleness of your solution very interesting.
Thanks.
Thanks! I love Python for the
Thanks! I love Python for the simplicity of its code. The
yieldstatement (it's not a function — a function would have parentheses wrapping its arguments) is like thereturnstatement, but it turns a function into a generator (check the python documentation). Generators turn ugly nested loops with lots of state keeping into elegant, short code.I will be sure to read up on
I will be sure to read up on generators. Thanks again.
Add new comment