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.

• Generate a list of valid indices

• 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)

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)

StackExchange Code Review Q#58050, answer score: 5