Generating Pascal's triangle

Question

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)

• SylvainD: 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.

Answer 1

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)