Python Pascal Triangle
Python Pascal Triangle
A pascal triangle is a number pattern of triangular array of the binomial coefficients. For designing a pascal triangle, we write a function in the program which takes an integer value as the input and print the number of lines (given by user as the integer value) for the pascal triangle.
Example: Following is the example of a pascal triangle pattern with the first 6 rows:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
Pascal triangle in Python
In Python, we draw the pascal triangle pattern using the math module. We use the factorial functions of the math module in our Python program to implement the nCr formula for pascal triangle.
Here, in this tutorial, we will learn about the following methods in our Python program to get the pascal triangle pattern in the output:
1). Directly implementing nCr formula
2). Using C (line, m-1) implementation
3). Using powers of 11 implementation
Let's learn about the all the above given methods details and understand them with an example program.
Method 1: Directly implementing the nCr Formula in the program:
When we use the nCr formula in our program, a pictorial representation as given below will appear on the screen:
We will use the following steps or algorithm in the program while implementing this method:
- We will first take an input integer which is the number of rows of pascal triangle to be printed. Let's assume this input integer as 'num'.
- We will make outer iteration of m variable from 0 to given num times, for printing the rows of triangle.
- Then, we will make inner iteration of variable n from 0 to (num-1) times, for printing variables in each row.
- After that, we will print single blank space as " ".
- Then, we will close the inner loop (n variable loop) and it will create the left spacing in the rows.
- After that, we will make an inner iteration for the n variable from 0 to m.
- Then, we will print the nCr result for m and n.
- Now, we will close the inner loop of program.
- In last, we will print or add new line after each inner iteration of n loop. It will add a new line while printing a new row.
Now, look at the following program for the implementation of above algorithm:
# importing factorial functions from math module from math import factorial # taking number of rows as input from user num = int (input ("Enter the number of rows for pascal triangle: ")) # defining the outer iteration for number of loops for m in range(num): # defining inner iteration for variables in each row for n in range(num-m+1): # closing inner n iteration for left spacing print (end=" ") # inner n iteration for elements of pascal triangle for n in range(m+1): # implementing the nCr = n!/((n-r)!*r!) formula print (factorial(m)//(factorial(n)*factorial(m-n)), end=" ") # using print statement for new line print ()
Enter the number of rows for pascal triangle: 6 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 The time complexity for the pascal triangle we have printed above is O(N²).
Method 2: Using C (line, m-1) implementation:
In this method, we will learn that how we can optimize the complexity of code given in method 1. In this method, we will follow the concept of binomial coefficients i.e., the mth entry in a given line number (let's say line) is the binomial coefficient for C (line, m). And, all the lines of pascal triangle will start with the value 1.
The basic idea used in this implementation is that we have to calculate the C (line, m) binomial coefficients using the C (line, m-1) coefficient. General formula for such type of implementation is as follows:
C (line, m) = [C (line, m-1) * (line - m + 1)]/ m
Now, look at the following program for the implementation of above given method:
# taking number of rows as input from user num = int (input ("Enter the number of rows for pascal triangle: ")) # defining for loop for number of rows for m in range(1, num+1): # using inner iteration for elements in triangle rows for n in range(0, num-m+1): # for left spacing in rows print (' ', end='') # defining C as first element of array equals to 1 C = 1 # using for loop for values in line for n in range(1, m+1): # the first value in a line is always equals to 1 print (' ', C, sep='', end='') # using Binomial Coefficient for C variable C = C * (m - n) // n # printing new line for each row print()
Enter the number of rows for pascal triangle: 7 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 The time complexity for the pascal triangle we have printed above is O(N²).
Method 3: Using powers of 11 implementation:
This method is considered as the most optimized approach for printing pascal triangle pattern in Python. This method is based on the approach of powers of 11. Look at the following powers of 11 to understand this approach:
11? = 1 11¹ = 11 11² = 121 11³ = 1331 etc.
Note: However, this approach is only limited up to the n = 5 i.e., 11?. It means we cannot print more than 5 rows of pascal triangle using this approach.
Now, look at the following program for the implementation of above given approach:
Example – 1
# taking number of rows as input from user num = int (input ("Enter the number of rows for pascal triangle (Maximum 5): ")) # using for loop for number of rows for a in range(num): # adjust left spacing between each element print (' '*(num-a), end='') # computing power of 11 for each row print(' '.join(map(str, str(11**a))))
Enter the number of rows for pascal triangle (Maximum 5): 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 The time complexity for the pascal triangle we have printed above is O(N).