How can this function be faster? Solving for a row of Pascal's triangle

Question

I saw a posting on Hacker News this morning that was ranting about people not being able to solve an interview question. I thought I would give it a shot, but I would like to know how my attempt could be improved.

def get_pascal_row(n):
    """
    Returns the nth row of Pascal's Triangle for a given n. Uses
    Gray's algorithm.
    """
    if n == 0: return []
    n -= 1
    row = [1]
    for i in xrange(1,n+1):
        row.append(row[-1] * n/i)
        n -= 1
    return row

Answer 1

You can memoize the rows you have already computed previously.

Alternatively, you could compute it in closed form using the binomial coefficients:

Start looking in scipy.special.binom.

Answer 2

@wim, I can't add a comment to your answer, so allow me to follow up here. I think one of us is confused (and it's likely me); the point of my method was to avoid having to compute any earlier rows. I don't see how memoizing comes into play, but I am still probably missing something else. Thanks for the input regardless!

Answer 3

you can try something like this:

def func(n):
    lis=[[1],[1,1]]
    if n in (1,2):
        return lis[n-1]
    for _ in range(n-2):
        lis.append([1]+map(sum,zip(lis[-1],lis[-1][1:]))+[1])
    return lis[-1]


In [6]: func(5)
Out[6]: [1, 4, 6, 4, 1]

In [7]: func(7)
Out[7]: [1, 6, 15, 20, 15, 6, 1]

In [8]: func(3)
Out[8]: [1, 2, 1]