# Generating Pascal's triangle

I am trying to generate Pascal's triangle table in Python 3. I started to like using this following pattern when dealing with 2D arrays.

1. Generate a list of valid indices
2. Use a function that works with those indices in a list comprehension. (may produce side effects)

I wonder, is this pattern pythonic and how common is it in practice?

def pascal_triangle(level):
def compute(table, row, col):
if row == 0:
table.append([])
if col == 0 or row == col:
table[row].append(1)
elif col <= row:
table[row].append(table[row-1][col] + table[row-1][col-1])
table = []
valid_idxs = [(r,c) for r in range(level) for c in range(level)]
[compute(table, r, c) for r, c in valid_idxs]
print(table)

• Hi, I appreciate the fact that you considered my answer as satisfying. However, I reckon it would be best for you not to accept it too quickly as it can prevent other people to want to come and bring new ideas to the table. – SylvainD Jul 25 '14 at 16:18

In :

table = []
valid_idxs = [(r,c) for r in range(level) for c in range(level)]
[compute(table, r, c) for r, c in valid_idxs]
print(table)


the line [compute(table, r, c) for r, c in valid_idxs] definitly shouldn't be a list comprehension as we are building a list that we do not use. If it is side-effects we are interested in, we might as well use a for.

table = []
valid_idxs = [(r,c) for r in range(level) for c in range(level)]
for r, c in valid_idxs:
compute(table, r, c)
print(table)


Once, this is done, it seems quite clear that the first list comprehension is not really required neither as it could be :

table = []
for r in range(level):
for c in range(level):
compute(table, r, c)
print(table)


This being said, even though it looked like a good idea to use a function to extract common code, the responsabilities are not clearly defined making things a bit hard to track. Let's put the body of the function back in the loop and try to see what can be improved :

def pascal_triangle(level):
table = []
for r in range(level):
for c in range(level):
if r == 0:
table.append([])
if c == 0 or r == c:
table[r].append(1)
elif c <= r:
table[r].append(table[r-1][c] + table[r-1][c-1])
print(table)


First thing to improve : print the content of table before or after the table.append([]) : isn't it a bit weird to build all lists as we go through the c variable ? Also, the first list created is non-empty but the other one are. Let's make the process clearer and add an empty list at each r iteration.

def pascal_triangle(level):
table = []
for r in range(level):
print(table) # look how the tables gets populated now : isn't it cool ?
table.append([])
for c in range(level):
if c == 0 or r == c:
table[r].append(1)
elif c <= r:
table[r].append(table[r-1][c] + table[r-1][c-1])
print(table)


Let's go one step further, please note that the deeper loop will not do anything if c > r (this wasn't true before previous change but it is now correct). We can easily remove this pointless iterations (and the pointless check) :

def pascal_triangle(level):
table = []
for r in range(level):
print(table)
table.append([])
for c in range(r+1):
if c == 0 or r == c:
table[r].append(1)
else:
assert(c<=r)
table[r].append(table[r-1][c] + table[r-1][c-1])
print(table)


Now, it's time for the special trick : we could remove the test if c == 0 by performing this before the loop. Also, we could't remove the if c == r by performing this after the loop (but we need to check that this would have happened which is when r>0).

def pascal_triangle(level):
table = []
for r in range(level):
print(table)
table.append([])
table[r].append(1)
for c in range(1, r):
table[r].append(table[r-1][c] + table[r-1][c-1])
if r:
table[r].append(1)
print(table)


Now, we can try to be more fancy : instead of calling table[r] every time : let's introduce a line variable and use it :

def pascal_triangle(level):
table = []
for r in range(level):
line = []
line.append(1)
for c in range(1, r):
line.append(table[r-1][c] + table[r-1][c-1])
if r:
line.append(1)
table.append(line)
print(table)


We can see that this looks a lot like a list comprehension scenario and indeed, we can use it :

def pascal_triangle(level):
table = []
for r in range(level):
table.append([1] + [table[r-1][c] + table[r-1][c-1] for c in range(1, r)] + ([1] if r else []))
print(table)