Submitted by alexios on

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.

Tags: 

Language: 


Comments


Add new comment

Leave a comment