python python-3.x algorithm optimization pascals-triangle

How to optimize printing Pascal's Triangle in Python?

I have implemented the Pascal's triangle in Python, it is pretty efficient, but it isn't efficient enough and there are a few things I don't like.

The Pascal's triangle is like the following:

I have read this useless tutorial and this question, and the solutions are extremely inefficient, involving factorials and don't use caching.

Instead, I implemented a different algorithm I created myself. My mathematics isn't that good, but I have spotted the following simple recursive relationships:

The triangle starts with a row with only 1 number in it, and that number is 1.

For each subsequent row, the length of the row increment by 1, and the first and last number of the row is 1.

Each number that isn't the first or last, is the sum of the number at the row above it with index equal to the number's index minus 1, and the number at row above it with the same index.

And the rows of the triangle are symmetric.

In other words, if we use zero-based indexing:

p(r, 0) = p(r, r) = 1
p(r, c) = p(r - 1, c - 1) + p(r - 1, c)
p(r, c) = p(r, r - c)

Below is my code:

from typing import List

class Pascal_Triangle:
    def __init__(self, rows: int = 0, fill: bool = True):
        self.data = []
        self.length = 0
        if rows:
            self.fill_rows(rows)
        if fill:
            self.fill_values()

    def add_row(self, length: int):
        row = [0] * length
        row[0] = row[-1] = 1
        self.data.append(row)

    def fill_rows(self, rows: int):
        for length in range(self.length + 1, rows + 1):
            self.add_row(length)
        self.length = rows

    def comb(self, a: int, b: int) -> int:
        if not 0 <= b <= a:
            raise ValueError(f'cannot choose {b} elements from a population of {a}')

        if self.length < (length := a + 1):
            self.fill_rows(length)

        return self.at(a, b)

    def at(self, row: int, col: int) -> int:
        if val := self.data[row][row - col]:
            self.data[row][col] = val
            return val

        if val := self.data[row][col]:
            return val

        self.data[row][col] = val = self.at(row - 1, col - 1) + self.at(row - 1, col)
        return val

    def fill_values(self):
        for row in range(2, self.length):
            for col in range(1, row):
                self.at(row, col)

    def get_row(self, row: int) -> List[int]:
        if self.length < (length := row + 1):
            self.fill_rows(length)

        self.fill_values()
        return self.data[row]

    def pretty_print(self):
        print('\n'.join(f"{' ' * (self.length - i)}{' '.join(map(str, row))}" for i, row in enumerate(self.data)))

First, the output of tri = Pascal_Triangle(12); tri.pretty_print() is extremely ugly:

            1
           1 1
          1 2 1
         1 3 3 1
        1 4 6 4 1
       1 5 10 10 5 1
      1 6 15 20 15 6 1
     1 7 21 35 35 21 7 1
    1 8 28 56 70 56 28 8 1
   1 9 36 84 126 126 84 36 9 1
  1 10 45 120 210 252 210 120 45 10 1
 1 11 55 165 330 462 462 330 165 55 11 1

How can I dynamically adjust the spacing between the elements so that the output looks more like an equilateral triangle?

Second I don't like the recursive function, is there any way that I can get rid of the recursive function and calculate the values using the recursive relationship by iteration, while remembering already computed numbers?

Third, is there a data structure more efficient than my nested lists for the same data? I have thought of numpy.array but arrays need each row to have the same length and arrays can't grow.

Finally can my algorithm be optimized further?

The data after calling tri.at(16, 5) is:

[[1],
 [1, 1],
 [1, 2, 1],
 [1, 3, 3, 1],
 [1, 4, 6, 4, 1],
 [1, 5, 10, 10, 5, 1],
 [1, 6, 15, 20, 15, 6, 1],
 [1, 7, 21, 35, 35, 21, 0, 1],
 [1, 8, 28, 56, 70, 56, 0, 0, 1],
 [1, 9, 36, 84, 126, 126, 0, 0, 0, 1],
 [1, 10, 45, 120, 210, 252, 0, 0, 0, 0, 1],
 [1, 11, 55, 165, 330, 462, 0, 0, 0, 0, 0, 1],
 [1, 12, 66, 220, 495, 792, 0, 0, 0, 0, 0, 0, 1],
 [1, 0, 78, 286, 715, 1287, 0, 0, 0, 0, 0, 0, 0, 1],
 [1, 0, 0, 364, 1001, 2002, 0, 0, 0, 0, 0, 0, 0, 0, 1],
 [1, 0, 0, 0, 1365, 3003, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
 [1, 0, 0, 0, 0, 4368, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]]

I know I am already doing memoization, and that is not what I meant. I want to calculate the unfilled values without ever using a recursive function. Instead of using the recursive definition and going backwards, we can somehow use iteration, start from where the lowest value that was filled and needed for the query, and iterate through all needed numbers, make two copies of each number and go forwards, until the requested index was reached.

The needed numbers can be computed using indexing and mathematics.

In this way there is no recursive function call at all.

Update

I have rewrote my code to the following:

class Pascal_Triangle:
    def __init__(self, end_row: int = 2, opt: int = 0):
        self.data = [[1], [1, 1]]
        self.length = 2
        self.opt = [self.add_rows_o0, self.add_rows_o1]
        if end_row > 2:
            self.opt[opt](end_row)

    def add_rows_o0(self, end_row: int):
        last_row = self.data[-1]
        for _ in range(self.length, end_row):
            self.data.append(
                last_row := [1] + [a + b for a, b in zip(last_row, last_row[1:])] + [1]
            )

        self.length = end_row

    def add_rows_o1(self, end_row: int):
        last_row = self.data[-1]
        for n in range(self.length, end_row):
            mid = n // 2 + 1
            row = [0] * (n - 1)
            m = n - 2
            for i, (a, b) in enumerate(zip(last_row, last_row[1:mid])):
                row[i] = row[m - i] = a + b

            self.data.append(last_row := [1] + row + [1])
        self.length = end_row

    def pretty_print(self):
        longest = len(str(self.data[-1][self.length // 2]))
        line_length = (longest + 1) * self.length
        for row in self.data:
            print(" ".join(f"{n:{longest}}" for n in row).center(line_length))

I have used list comprehension to generate new rows and got rid of the expensive recursive function call. The code is much faster as a result.

However, I tried to exploit the symmetric nature of the rows and only calculate half of the row and mirror it to get the other half. In this way the number of calculations would be halved.

But it is actually slower:

In [257]: %timeit Pascal_Triangle(64, 1)
237 µs ± 7.43 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [258]: %timeit Pascal_Triangle(64, 0)
224 µs ± 9.75 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [259]: Pascal_Triangle(64, 1).data == Pascal_Triangle(64, 0).data
Out[259]: True

Why is it slower? And how can I actually skip the unnecessary calculations and make it faster?

Solution

You can improve the pretty_print by getting the length (as string) of the longest number and using that as the basis for all the numbers' width; also using str.center might be easier.

 def pretty_print(self):
     longest = max(len(str(n)) for row in self.data for n in row)
     line_length = (longest + 1) * self.length
     for row in self.data:
         print(' '.join(f'{n:{longest}}' for n in row).center(line_length))

With this check if val := self.data[row][col]: return val, you are already doing that, and each value is calculated exactly once. You could make it purely iterative in fill_values directly, and drop the at method entirely, though:
```
 def fill_values(self):
     for row in range(2, self.length):
         for col in range(1, row):
             self.data[row][col] = self.data[row - 1][col - 1] + self.data[row - 1][col]
```
I'd say a nested list-of-lists is a good choice here, and your algorithm (even before 2.) should already be as efficient as possible.

Having said that, I noticed you have a comb function, so maybe your goal is not really to print the triangle, but to calculate individual values. In this case, there are two possible ways to make you code faster (although I did not actually time it).

First, you could use a dict as data structure and then only calculate the values that are actually needed to find the value at a given row and col. In the worst case (centre of bottom row) that will be 50% of the entire triangle, and on average much less than that.

class Pascal_Triangle:
    def __init__(self):
        self.data = {(0, 0): 1}
        
    def fill_rows(self, rows: int):
        # actually, just the last row would be enough here...
        for row in range(rows + 1):
            for col in range(row + 1):
                self.at(row, col)
        
    def at(self, row: int, col: int) -> int:
        if not 0 <= col <= row:
            raise ValueError(f'column position {col} is invalid for row {row}')
        if (row, col) not in self.data:
            self.data[row, col] = 1 if col in (0, row) else self.at(row - 1, col - 1) + self.at(row - 1, col)
        return self.data[row, col]
    
    def pretty_print(self):
        longest = max(len(str(n)) for n in self.data.values())
        max_row = max(row for (row, col) in self.data)
        line_length = (longest + 1) * max_row
        for row in range(max_row+1):
            print(' '.join(str(self.data.get((row,col), "")).center(longest) for col in range(row + 1)).center(line_length))

This version still has the fill_rows and pretty_print functions (nicely showing which values were actually calculated). If you don't need those, you could also just make at a function and use functools.cache to cache the values...

from functools import cache

@cache
def at(row: int, col: int) -> int:
    if not 0 <= col <= row:
        raise ValueError(f'column position {col} is invalid for row {row}')
    return 1 if col in (0, row) else at(row - 1, col - 1) + at(row - 1, col)

... or calculate the binomial coefficient directly using factorials:

    from math import factorial as fac
    def comb(n, k):
        return fac(n) // (fac(k)*(fac(n-k)))