Categories
APIs Cloud Integrations General Python Software Engineering

Python Firebase Authentication Integration with FastAPI

FastAPI is a new Python framework to facilitate the creation of APIs. Google Firebase Authentication is Google Cloud Platform’s authentication tool. It’s similar to tools like AWS Cognito, Azure Active Directory, or Okta. 

In this post, we’re going to go over how to integrate Firebase Auth with FastAPI. We’ll cover:

An Introduction to the Python FastAPI Framework

FastAPI is a Python framework designed specifically for building APIs. It’s built on Starlette and Pydantic. Starlette is the base for the web pieces and Pydantic is the base for the data pieces. FastAPI is compatible with all versions of Python 3.6 and above. For this example, we’ll be using Python 3.10.

Python Packages to Run FastAPI Apps Locally

To run an app built on FastAPI locally, we will also need an asynchronous server gateway interface (ASGI), and we’ll use uvicorn as suggested in the docs. To get the packages you’ll need to build a basic FastAPI app, run pip install fastapi uvicorn in your terminal.

What is Google Firebase Authentication?

In 2008, Google launched their App Engine. In 2010, they launched their cloud storage. Firebase was founded in 2012 and in 2014, Google acquired Firebase and announced Firebase Auth and Firebase Hosting. Google Firebase Authentication is the user management solution part of Google Cloud Platform. You need a Google Cloud Platform account for it.

To install the Google Firebase SDK and the Python wrapper to work with it, run pip install pyrebase4 firebase-admin. It is very important that you install pyrebase4 and not pyrebase which will install pyrebase 3. You will get a SyntaxError in the RSA.py file if you use pyrebase 3.

Install Pyrebase 4, you will get an error with Pyrebase 3

How Does Google Firebase Auth Work?

Google Firebase Authentication fully manages users for you. It allows you to easily add sign in methods from the basic email/phone configuration to single-sign-ons. Currently, it supports Google, Facebook, Apple, Microsoft, Twitter, and many more. It also provides an easy way to implement email verification and idempotency, and track usage.

Like other managed user solutions, Google Firebase Auth uses JSON Web Tokens (JWT) to verify identity. When you create a user, Firebase Auth populates a user with a unique ID in your managed user database. It then sends that ID back, it’s up to you if you want to populate your own user database with that ID or not.

If you are running an application where you want to customize user access, then you will need your own user database. Once a user is created, they can now log in with the login methods that they signed up with. When a user logs in, Firebase Auth will verify their ID and then return a JWT token.

Once you have a JWT token, your user is “logged in”. There are many ways to verify if your user is logged in with the right JWT token. The most common solutions include sending your JWT token in the header (which we’ll do here), sending your user id in the header or body, or simply using a “logged in” flag on the front end. The reason we’ll be sending the JWT token in the header and decoding it on the server side is because it’s safer than sending unencoded messages directly through your request.

Setting up Firebase Authentication

To set up Firebase Authentication, we first need to sign up for Google Firebase. Once you sign up for a Firebase account, you will need to create a Project. Click into your project and you should see a sidebar, look for a person icon (circled in red in the image below). The authentication page will look like the image below (as of Jun 18, 2022).

Google Firebase Authentication – Get Started Page

Once you click “Get started”, it’ll take you to a page to set up your sign-in methods. The easiest one to get started with is the Email/Password option. Setting up Google auth is also simple. 

Creating a Firebase Authentication Sign in Method

Once you’ve set up your Firebase Authentication using an email and password, you want to go to your project settings and scroll all the way down under the “General” tab. You will see the apps in your project. Pick whichever app you’re working on, iOS, Android, Web, Unity, or Flutter. For this project, we’re going to create a webapp.

add new app for firebase auth

The wizard will ask you to name your app. After you name your app, it will ask you if you want to use npm or <script> tags to use the SDK. You can ignore this. Once you’re out of the app creation wizard, go back to project settings and scroll down again. You should now see an image like the one below. Copy the config below and save it as firebase_config.json. You will also need to add a line that says ”databaseURL”: “” because the Python SDK looks for it.

Get app config from Firebase Authentication (for Pyrebase)

Once you have this file saved locally, scroll back up the page and go to the “Service accounts” tab. Choose Python to see the example code to load your credentials. Click “Generate new private key” to get your admin keys. Save this file locally as <project-name>_service_account_keys.json and move it into your project root directory.

Service Account Keys for Firebase Admin

Setting Up Our FastAPI App to Connect with Google Firebase Auth

Before we get into building out our signup and login endpoints, we need to set up FastAPI and our Firebase connection. We will be using uvicorn to create our server, firebase_admin and pyrebase connect to Firebase and use its authentication service, json to read JSON objects, and finally FastAPI to build our API endpoints. This will all be in one file called main.py.

import uvicorn
import firebase_admin
import pyrebase
import json
 
from firebase_admin import credentials, auth
from fastapi import FastAPI, Request
from fastapi.middleware.cors import CORSMiddleware
from fastapi.responses import JSONResponse
from fastapi.exceptions import HTTPException

After our imports, the first thing we want to do is create our Firebase connection. Use the service account keys that you downloaded earlier to create a credentials.Certificate for Firebase. Then, use those credentials to initialize the firebase_admin app. Next, we’ll use pyrebase to initialize a Firebase app based on the Config file we downloaded above.

The difference between these two Firebase setups is what they do. The firebase_admin app will verify the ID token for the user while the pyrebase app is the one that lets you sign in with your email and password.

Now that we’ve set up our Firebase Authentication services, let’s set up our FastAPI app. It’s pretty simple, we just call FastAPI() to set up our app. We are also going to add middleware to our app that allows cross origin resource sharing (CORS). We’ll set it up so that we can hit our API from anywhere. Note that in production, you will want to limit how your API is called!

Finally, we’ll run the app on uvicorn in our main function.

cred = credentials.Certificate('eeee_service_account_keys.json')
firebase = firebase_admin.initialize_app(cred)
pb = pyrebase.initialize_app(json.load(open('firebase_config.json')))
app = FastAPI()
allow_all = ['*']
app.add_middleware(
   CORSMiddleware,
   allow_origins=allow_all,
   allow_credentials=True,
   allow_methods=allow_all,
   allow_headers=allow_all
)
 
# signup endpoint
 
# login endpoint
 
# ping endpoint
 
if __name__ == "__main__":
   uvicorn.run("main:app")

FastAPI Signup Endpoint for Google Auth

High Level Design Diagram for Signup Endpoint

Now let’s create the signup endpoint. This is the endpoint that we will hit to create a new user account in Firebase. To create a new user account, we will need to get an email and password from the user. This information should be passed through the request body as a JSON.

As with many modern Python frameworks, FastAPI uses decorators. We will use the FastAPI decorator to declare a way to send a POST request to the /signup endpoint. I’ve also opted to not include this in the schema. If you are creating an API, there’s a good chance you don’t want to expose this in your API schema. If you are creating a webapp, this is less applicable.

FastAPI uses async functionality, so we will be creating an asynchronous function. The only parameter that we need to pass our function is the HTTP request being sent. The first thing we’re going to do in our function is await the JSON of the request. Then, we’ll extract the email and password out and verify that they are both there or return an Exception.

Next, we’ll use the auth functionality from firebase_admin to create a new user with Firebase authentication. All we need to create a new user is the email and password, and the reason we can do this is because we set that up as an approved user type in the Firebase Authentication console earlier.

If the user is created successfully, we return a success message and the new user ID. You can store this ID in your personal user database. If the user is not created successfully, such as if someone re-uses an email, then we return an error message.

# signup endpoint
@app.post("/signup", include_in_schema=False)
async def signup(request: Request):
   req = await request.json()
   email = req['email']
   password = req['password']
   if email is None or password is None:
       return HTTPException(detail={'message': 'Error! Missing Email or Password'}, status_code=400)
   try:
       user = auth.create_user(
           email=email,
           password=password
       )
       return JSONResponse(content={'message': f'Successfully created user {user.uid}'}, status_code=200)    
   except:
       return HTTPException(detail={'message': 'Error Creating User'}, status_code=400)

FastAPI Login Endpoint for Google Firebase Auth

High Level Design Diagram for Login with Pyrebase

Just like our signup endpoint, our login endpoint will be a POST endpoint. The function will also only need to take the request as a parameter. Once again, we’ll await the loading of the JSON of the request. Then, we’ll extract the email and password from the JSON and try to authenticate the user using the pyrebase instance we created earlier. If successful, we return the JSON Web Token, otherwise we return an Exception.

@app.post("/login", include_in_schema=False)
async def login(request: Request):
   req_json = await request.json()
   email = req_json['email']
   password = req_json['password']
   try:
       user = pb.auth().sign_in_with_email_and_password(email, password)
       jwt = user['idToken']
       return JSONResponse(content={'token': jwt}, status_code=200)
   except:
       return HTTPException(detail={'message': 'There was an error logging in'}, status_code=400)

Dummy Endpoint to Validate Firebase Authentication

Verify JWT with Firebase_Admin Auth

Now that we’ve handled the login and signup code, let’s create a dummy endpoint to validate the token. I will call this endpoint ping, but you can call it whatever you want. It is going to expect to see the JWT in the authorization field of the request headers.

Technically, you can send the JWT through the request any way you want, but it is typically sent through the headers because it is used for validation. The advantage of sending it through the headers and not the JSON body is that we don’t have to await anything to load before running validation.

This example validation function will print out the JWT to the console. Then, it will call the auth module from firebase_admin to verify the JWT and return the user ID. If it can’t verify the token, there will be an error thrown. Technically we can throw it here, but I’ve opted to let the server do it.

# ping endpoint
@app.post("/ping", include_in_schema=False)
async def validate(request: Request):
   headers = request.headers
   jwt = headers.get('authorization')
   print(f"jwt:{jwt}")
   user = auth.verify_id_token(jwt)
   return user["uid"]

Run Your FastAPI App Locally with Uvicorn

To get your FastAPI App up and running locally just run uvicorn --port 1234 main:app --reload in the terminal. You can adjust the port to fit your usage, the default port is 8000 and the default host is your localhost, http://127.0.0.1.

While the app is running, the terminal will show a reload process that looks like the image below. It will also display the host and port that Uvicorn is running on.

Running your FastAPI App Locally

Testing Signup with Firebase Authentication and Pyrebase

Now let’s create a test program to test the Firebase signup endpoint we made. This is a separate file that I’ve called test_signup.py. This is not a traditional unit test. The first thing we’ll do is import the requests library. Then, we’ll create a signup function that takes an email and a password.

This function will take the email and password and form them into a JSON body to send to the POST endpoint. Then, we’ll use the requests library to send a POST request to the signup endpoint with the dictionary we created above as our JSON body. Finally, the function will return the text. We’ll call this function with an email and password and print out the response.

import requests
 
def signup(email: str, password: str):
   body = {
       "email": email,
       "password": password
   }
   response = requests.post(url="http://127.0.0.1:9001/signup", json=body)
   return response.text
 
print(signup("abcd@abcd.com", "password"))

The image below shows a response similar to the one you should get if you run the file above while the Uvicorn server is still running the FastAPI app we made earlier. The function returns a message that shows you the newly created User ID. You can save this ID in your custom user database if you’re using one.

Successfully created new user with firebase_admin and FastAPI

Testing Login with Firebase Auth Pyrebase and FastAPI

Okay, now that we’ve created a user, let’s also test login. For this file, separate from the signup test one, we’ll start by importing requests and json. Our login function will take an email and password just like the signup function. We will also create the same JSON body. Then, we need to send a post request to the login endpoint. In this case, we’ll return just the token by extracting out the token from the response text using the JSON library.

import requests
import json
 
def login(email: str, password: str):
   body = {
       "email": email,
       "password": password
   }
   response = requests.post(url="http://127.0.0.1:9001/login", json=body)
   return json.loads(response.text)["token"]
 
print(login("abcd@abcd.com", "password"))

The image below shows what an example response would look like. The JWT will be a long string.

Logging into Firebase Auth and get JWT back

Using the Ping Endpoint for JWT Validation with Firebase Auth and Pyrebase

In the same file as the login function is defined above, we’ll create a function to test the JWT returned. Instead of printing the login result, I store it in a variable called token. The ping function will take the token as a parameter.

In the function, we’ll create a header with an authorization key that corresponds to the token. Then, we’ll send off a POST request to the ping URL with the headers and print the response.

token = login("abcd@abcd.com", "password")
 
def ping(token: str):
   headers = {
       'authorization': token
   }
   response = requests.post(url="http://127.0.0.1:9001/ping", headers=headers)
   return(response.text)
 
print(ping(token))

We should expect to see a response like the one below which shows us the user ID we created earlier.

Successful ping/validation with Pyrebase for Firebase Auth

Summary of Using Google Firebase Auth with FastAPI Python Backend

In this post we covered the basics of the FastAPI package and Google Firebase Authentication. We covered the packages we need to run a FastAPI app locally, and the packages we need to interact with Google Firebase Authentication in Python.

We built a one-file FastAPI app with three endpoints: signup, login, and ping. These endpoints create a user, log a user in, and verify the JWT token returned from a login. Then we created test scripts to run while the FastAPI app was running locally on Uvicorn and tested our endpoints.

Further Reading

Learn More

To learn more, feel free to reach out to me @yujian_tang on Twitter, connect with me on LinkedIn, and join our Discord. Remember to follow the blog to stay updated with cool Python projects and ways to level up your Software and Python skills! If you liked this article, please Tweet it, share it on LinkedIn, or tell your friends!

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.

Yujian Tang

I started my professional software career interning for IBM in high school after winning ACSL two years in a row. I got into AI/ML in college where I published a first author paper to IEEE Big Data. After college I worked on the AutoML infrastructure at Amazon before leaving to work in startups. I believe I create the highest quality software content so that’s what I’m doing now. Drop a comment to let me know!

One-Time
Monthly
Yearly

Make a one-time donation

Make a monthly donation

Make a yearly donation

Choose an amount

$5.00
$15.00
$100.00
$5.00
$15.00
$100.00
$5.00
$15.00
$100.00

Or enter a custom amount

$

Your contribution is appreciated.

Your contribution is appreciated.

Your contribution is appreciated.

DonateDonate monthlyDonate yearly
Categories
General Python

How to Use Environment Variables with Python Dotenv

We often have to use API keys, secret keys, identity keys, and so on when we build applications. Each of these keys comes with a warning not to show it publicly or to lose it. Managing these keys is not only a safety concern, but also a matter of staying up to date as keys have to change from time to time.  That’s where Python dotenv comes into play.

Clearly, we shouldn’t be storing these keys directly in our code base. How should we be storing these keys? Currently, the best practice is to use environment variables. In this post we will be learning about:

  • What are Environment Variables?
  • When do We Use Environment Variables in Python?
  • What is Python Dotenv?
    • How to Use Python Dotenv to Manage Environment Variables
    • Why Load Environment Variables with Python Dotenv?
  • Summary of Using Environment Variables with Python Dotenv

What are Environment Variables?

Py Dotenv Manages environment variables

Environment variables are variables that we store in the programming environment that we use. Python practitioners should be familiar with virtual environments. Virtual environments manage things such as packages and your Python version. You can think of these packages and versions as environment variables for your virtual environment.

In terms of programming, environment variables are variables that are specific to your programming environment. Typical examples include your usernames and passwords, your identity and access keys, and anything else that is specific to your local programming setup.

When do We Use Environment Variables in Python?

We should use environment variables for Python anytime we’re creating a program that uses variables that are specific to our usage. We especially want to use environment variables if we’re going to upload our code to Git or anywhere online. Using environment variables keeps our secret keys secret through being stored in a .env file, which should be, and usually is automatically, added to the .gitignore file.

What is Python Dotenv?

The dotenv package is a common package in many programming languages including Python. The Python version of the package is called python-dotenv. The Python Dotenv module allows you to not only retrieve the values stored in a .env file easily, but also allows for finding these values from anywhere in your application.

How to Use Python Dotenv to Manage Environment Variables

The python-dotenv library provides two main functions to manage environment variables, load_dotenv and dotenv_values. The load_dotenv function from Python Dotenv loads the key-value pairs in the .env file as environment variables that can be accessed using os. The dotenv_values function returns the key-value pairs as a dictionary.

​​from dotenv import dotenv_values

config = dotenv_values(".env")  # config = {"USER": "foo", "EMAIL": "foo@example.org"}

from dotenv import load_dotenv
load_dotenv()
print(os.getenv(“USER”)) # should be “foo”

Why Manage Environment Variables with Python Dotenv?

Python Dotenv is not the only way to manage environment variables. Technically, you can use the os module to access the .env file and get environment variables without installing the python-dotenv package. However, that’s not nearly as pretty. You would have to find, open, and parse the file yourself.

Summary of Using Environment Variables with Python Dotenv

Environment variables are used to dictate how a program runs in a given environment. They help us keep secret keys secret. Using environment variables is common in all sorts of application programming. It’s so common that python-dotenv is just the Python version of the dotenv package.  Javascript, Java, R and more languages also have their own dotenv packages.

We can use Python Dotenv to load the variables in the .env file not only as environment variables, but also as a dictionary. Then, we can access the loaded environment variables either through the OS or through the dictionary values.

Further Reading

Learn More

To learn more, feel free to reach out to me @yujian_tang on Twitter, connect with me on LinkedIn, and join our Discord. Remember to follow the blog to stay updated with cool Python projects and ways to level up your Software and Python skills! If you liked this article, please Tweet it, share it on LinkedIn, or tell your friends!

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.

Yujian Tang

I started my professional software career interning for IBM in high school after winning ACSL two years in a row. I got into AI/ML in college where I published a first author paper to IEEE Big Data. After college I worked on the AutoML infrastructure at Amazon before leaving to work in startups. I believe I create the highest quality software content so that’s what I’m doing now. Drop a comment to let me know!

One-Time
Monthly
Yearly

Make a one-time donation

Make a monthly donation

Make a yearly donation

Choose an amount

$5.00
$15.00
$100.00
$5.00
$15.00
$100.00
$5.00
$15.00
$100.00

Or enter a custom amount

$

Your contribution is appreciated.

Your contribution is appreciated.

Your contribution is appreciated.

DonateDonate monthlyDonate yearly
Categories
Uncategorized

Accuracy, Precision, Recall, and F Score

How do you measure how well your machine learning model is doing? There are four main metrics for measuring the accuracy of a machine learning model. These metrics are accuracy, precision, recall, and F-Score (or F Score). In this post, we’ll be covering how to calculate each of these metrics and what they’re used for.

Before we get into learning what all of these metrics are, we first have to cover the confusion matrix. When your machine learning model makes a prediction it can either be right or wrong about its prediction. A confusion matrix keeps track of whether the model predicted the given class correctly or not. 

Table of Contents:

  • Confusion Matrices for Accuracy, Precision, Recall, and F Score
    • Confusion Matrix Example
  • Accuracy as a Machine Learning Model Metric 
    • How to Measure Model Accuracy
    • When to Use Accuracy as a Metric
  • Precision as a Machine Learning Model Metric 
    • How to Measure Model Precision
    • When to Use Precision as a Metric
  • Recall as a Machine Learning Model Metric 
    • How to Measure Model Recall
    • When to Use Recall as a Metric
  • F-Score as a Machine Learning Model Metric
    • How to Measure Model F Score 
    • When to Use F Score as a Metric
  • Summary of Accuracy, Precision, Recall, and F-Score

Confusion Matrices for Accuracy, Precision, Recall, and F Score

Before we dive into confusion matrices, I just want to say that I think these are poorly named. To create a confusion matrix, you create a two by two grid comparing the predicted and actual outcomes. An illustrated image is below. The image also shows the term used for each of the boxes.

Confusion Matrix + Terms

A common question that arises here is – what happens if my model predicts multiple classes? If your model predicts more than one class, the “negative” or “false” prediction just becomes “not the class we’re predicting for”.

You may also see the term False Positive referred to as a Type 1 Error and the term False Negative referred to as a Type 2 Error. These are the same things with different names.

Confusion Matrix Example

Let’s take a look at a contrived confusion matrix example so we can get a working knowledge of how they work. Let’s assume we have a model that predicts two classes and are making 20 predictions total. 

What would a confusion matrix look like if the truth was that there were 10 positives and 10 negatives and our model predicted 2 positives as negatives and 1 negative as a positive? To fill in the confusion matrix, we’d start with the errors we were given. We have two 2 false positives and 1 false negative. Then we fill in the other number in the row based on our errors.

Example Confusion Matrix

Accuracy as a Machine Learning Model Metric

Accuracy measures how often your model “gets it right” compared to the total number of predictions. In terms of metrics, it’s the total fraction of predictions that match the actual values.

How to Measure Model Accuracy

Using a confusion matrix, accuracy can be calculated as the number of true positives + the number of true negatives divided by the total number of predictions made.

Based on the example confusion matrix above, the accuracy of our example model would be (8+9)/20 or 85%. Not a great model, but we’re just using it as an example to illustrate how to measure accuracy, precision, recall, and F score.

When to Use Accuracy as a Metric

Knowing how to measure accuracy is just as important as knowing when to use accuracy as a metric. In many cases, it’s not inappropriate, but what if I were predicting whether or not there would be a tsunami in Seattle on any given day? I would just predict “no” every day and be right over 99% of the time. However, that would be a completely useless model.

Accuracy is a good metric to use if you are looking at a sample set that has closely balanced classes. If you have highly unbalanced classes, using accuracy as a metric would encourage the model to learn the most available class. A concrete example would be a neural network that predicts the MNIST digits dataset.

Precision as a Machine Learning Model Metric

Precision and accuracy are two terms that are often mixed up in everyday speech. In regular speech, accuracy refers to how close your prediction is to the actual truth and precision refers to how close your predictions are to each other. In machine learning metrics, we measure precision based on the total number of positive predictions.

How to Measure Model Precision

Unlike measuring your dart throwing precision, we’re not going to ask the machine to make the same prediction multiple times. We’re going to measure using the metrics we have in our confusion matrix. A machine learning model’s prediction is the number of true positives divided by the total number of positive predictions.

Based on the confusion matrix we have above, there are 8 true positives. We can find that we have 9 positive predictions by summing the number of true positives and false positives. This gives us a precision of 8/9 or about 88.89%.

When to Use Precision as a Metric

The main strength of precision as a metric is to measure how confident we are in the correctness of our prediction. If we need to be highly confident in our truth value, then we should prioritize precision as a metric. A real life example of this would be a model that predicts how safe a submarine would be in deep sea conditions. We want to be as sure as possible that our sailors will return alive.

Recall as a Machine Learning Model Metric

While accuracy and precision are two commonly used words that have slightly altered meanings when applied to machine learning model metrics, recall isn’t as commonly used as a measuring term. Usually we hear recall in terms of cars or other products in the market being “recalled”.

How to Measure Model Recall

The name “recall” suggests that we’re measuring how well our model “remembers” something. In this case, that something is the actual number of positive values. As a machine learning metric, recall is measured as the total number of true positives divided by the total number of actual positive values

In our example above, there are 8 true positives and 10 actually positive values. This gives us a recall of 8/10 or 80%. This is not a great recall score, but once again, we are just using the numbers in the given confusion matrix for example purposes.

When to Use Recall as a Metric

If we were using recall as a metric with the confusion matrix we have, we would have to continue tweaking our model. 80% is a pretty abysmal recall score.

Recall is a good metric to use when we are most concerned with getting as many true positive values as possible. A real life example would be a machine learning model to capture early stage cancer from medical images.

F-Score as a Machine Learning Model Metrics

Unlike accuracy, precision, or recall, F-Score (also called F1-Score) doesn’t really lend itself to any hints as to how to calculate it or what it may represent.

The F-Score is the harmonic mean of precision and recall. The harmonic mean of two numbers strikes a balance between them. We calculate the harmonic mean of a and b as 2*a*b/(a+b).

How to Measure Model F Score 

Plugging precision and recall into the formula above results in 2 * precision * recall / (precision + recall). When we turn this into the stats we have in the confusion matrix, we need to use all of the numbers except for true negatives. This harmonic mean simplifies to 2 * the number of true positives/(2 * the number of true positives + the number of false negatives + the number of false positives).

This simplified formula using only the stats we have in the confusion matrix shows us that F Score is a comparison of true positives to the total number of positives, both predicted and actual. Our example F Score would be 2*8/(2*8+2+1)=16/19 or 84%. Better than recall, but worse than precision. As expected.

When to Use F Score as a Metric

From the formula, we know that F-Score is a balance of precision and recall. We use F Score in cases where we need to have both good precision and good recall. This points to using F Score when we are concerned with getting the highest number of true positives and we want to be as sure as possible that our prediction is correct. 

A real life example would be if you’re investing. You want to invest in the most number of winners and invest in them as often as possible.

Summary of Accuracy, Precision, Recall, and F Score

Accuracy, Precision, Recall, and F Score are the four big machine learning model metrics. It’s impossible to say which of these metrics is “best” because each of them has their own usage. 

Accuracy is best used when we want the most number of predictions that match the actual values across balanced classes. Precision is best used when we want to be as sure as possible that our predictions are correct. Recall is best used when we want to maximize how often we correctly predict positives. Finally, F-Score is a combination of precision and recall. It is used when we want to be as sure as possible about our predictions while maximizing the number of correctly predicted positives.

Further Reading

Learn More

To learn more, feel free to reach out to me @yujian_tang on Twitter, connect with me on LinkedIn, and join our Discord. Remember to follow the blog to stay updated with cool Python projects and ways to level up your Software and Python skills! If you liked this article, please Tweet it, share it on LinkedIn, or tell your friends!

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.

Yujian Tang

I started my professional software career interning for IBM in high school after winning ACSL two years in a row. I got into AI/ML in college where I published a first author paper to IEEE Big Data. After college I worked on the AutoML infrastructure at Amazon before leaving to work in startups. I believe I create the highest quality software content so that’s what I’m doing now. Drop a comment to let me know!

One-Time
Monthly
Yearly

Make a one-time donation

Make a monthly donation

Make a yearly donation

Choose an amount

$5.00
$15.00
$100.00
$5.00
$15.00
$100.00
$5.00
$15.00
$100.00

Or enter a custom amount

$

Your contribution is appreciated.

Your contribution is appreciated.

Your contribution is appreciated.

DonateDonate monthlyDonate yearly
Categories
level 1 python

How to Make a 4×4 Magic Square in Python

Magic Squares are one of the oldest recreational mathematics games. The smallest magic squares are three by three, but they can be made up to any size with the right formulas. Odd and even ordered magic squares have different formulas, but can be easily generated. Programming has made it even easier to make magic squares, as we are about to see. Let’s make a 4×4 Magic Square in Python

In this post, we’ll learn about:

  • What is a Magic Square?
  • How Do You Create a 4×4 Magic Square?
  • The Five Binary Encoding Patterns for 4×4 Magic Squares
  • Python Code to Make a 4 by 4 Magic Square
    • Creating the Magic Square with Lists in Python
    • Full Code for Python 4×4 Magic Square
  • Testing Our Python Magic Square
  • Summary of Creating a 4×4 Magic Square in Python

What is a Magic Square?

3×3 Magic Square from Wikipedia

A magic square is a square that is filled with numbers, usually positive integers, such that the rows, diagonals, and columns of the square all add up to the same number.

How Do You Create a 4×4 Magic Square?

Odd and even rank magic squares are created with different formulas. The 4×4 even rank magic square is created using five binary encoded patterns. A binary encoded pattern is an overlay of the square in which each square contains either a 0 or a 1. Let’s take a look at what the patterns for the 4×4 magic square are.

The Five Binary Encoding Patterns for 4×4 Magic Squares

These are the five binary encoding patterns that we add up to make a 4×4 magic square.

5 magic patterns for generating a 4×4 magic square

If you layer these patterns you get the square below. This base 4×4 magic square adds up to 12 in every row, column, and diagonal.

a basic 4×4 magic square

Python Code to Make a 4 by 4 Magic Square

Now we know what a magic square is and what the basic 4×4 magic square looks like. Let’s use Python to create some 4×4 magic squares. We will use nested lists to represent our magic square and its binary encoded patterns. We don’t need any external Python libraries to create this function.

Creating the Magic Square with Lists in Python

The first thing we’re going to do is create a function to generate the magic square.Our function will create the five binary encoded patterns separately and has one parameter. The only parameter this function takes is a list, representing the values for each binary encoding pattern. For example, a list of 8, 4, 2, 1, 1 would yield the patterns below.

8, 4, 2, 1, 1 scaled 4×4 magic square generator patterns

These patterns will yield the following magic square with value 34.

8, 4, 2, 1, 1 params 4 x 4 magic square

The first thing we’re going to do in our function is create an empty nested list representation of all five patterns.

def create_square(params: list):
   patterns = [[None] for _ in range(5)]

Now let’s get started on creating the individual patterns.

First Magic Square Pattern in Python

Let’s implement the first pattern. Remember that we are implementing the square pattern as a nested list. This means that each row of the square should be represented as a list. There are only two different row patterns in this pattern, so we’ll create two lists that represent each pattern.

We use the first element of the parameter list to scale the binary pattern and create the square pattern using list comprehension on the two list patterns we created earlier.

   '''
   pattern 1
   0011
   1100
   0011
   1100
   '''
   pattern_1_1 = [0, 0, 1, 1]
   pattern_1_2 = [1, 1, 0, 0]
   patterns[0] = [[pattern*params[0] for pattern in pattern_1_1],
               [pattern*params[0] for pattern in pattern_1_2],
               [pattern*params[0] for pattern in pattern_1_1],
               [pattern*params[0] for pattern in pattern_1_2]]

Second Magic Square Pattern in Python

Our second magic square pattern will also need two different row patterns. Just like the first square pattern, we will create the two row patterns with lists. Then, we’ll create the square pattern using list comprehension to scale the patterns by the second entry in the parameters list.

   '''
   pattern 2
   0110
   1001
   0110
   1001
   '''
   pattern_2_1 = [0, 1, 1, 0]
   pattern_2_2 = [1, 0, 0, 1]
   patterns[1] = [[pattern*params[1] for pattern in pattern_2_1],
               [pattern*params[1] for pattern in pattern_2_2],
               [pattern*params[1] for pattern in pattern_2_1],
               [pattern*params[1] for pattern in pattern_2_2]]

Third Magic Square Pattern in Python

Our third magic square pattern is built in the same way as the first two. First, we’ll create another two list representations of the row pattern representations. Next, we use the third entry from the parameter list to scale these row patterns into the third magic square pattern.

   '''
   pattern 3
   0101
   0101
   1010
   1010
   '''
   pattern_3_1 = [0, 1, 0, 1]
   pattern_3_2 = [1, 0, 1, 0]
   patterns[2] = [[pattern*params[2] for pattern in pattern_3_1],
               [pattern*params[2] for pattern in pattern_3_1],
               [pattern*params[2] for pattern in pattern_3_2],
               [pattern*params[2] for pattern in pattern_3_2]]

Fourth Magic Square Pattern in Python

The process to create the first three magic square patterns has been almost the same. For the fourth one, we don’t need to recreate row patterns. We are simply reusing the row patterns that the third magic square uses in a different order and scaling by the fourth entry of the parameters instead of the third.

   '''
   pattern 4
   0101
   1010
   1010
   0101
   '''
   patterns[3] = [[pattern*params[3] for pattern in pattern_3_1],
               [pattern*params[3] for pattern in pattern_3_2],
               [pattern*params[3] for pattern in pattern_3_2],
               [pattern*params[3] for pattern in pattern_3_1]]

Fifth Magic Square Pattern in Python

This one is even easier than the fourth pattern. All we do here is create a matrix of ones and then scale by the fifth and last entry of the parameters list.

   '''
   pattern5
   1111
   1111
   1111
   1111
   '''
   patterns[4] = [[params[4] for _ in range(4)] for _ in range(4)]

Layering the Patterns into a Magic Square

Now that we have all five patterns created, we need to layer them together to create the magic square. To start off, we’ll create a magic square of all zeros. Then we’ll loop through the list of patterns and add each entry of each pattern to the corresponding entry in the magic square. Finally, we’ll return the square we created.

   square = [[0 for _ in range(4)] for _ in range(4)]
   for pattern in patterns:
       for i in range(4):
           for j in range(4):
               square[i][j] += pattern[i][j]
   return square

Full Code for Python 4×4 Magic Square Generator Function

That concludes the function to create a 4×4 magic square generator in Python. This is the full code for the create_square function.

def create_square(params: list):
   patterns = [[None] for _ in range(5)]
   '''
   pattern 1
   0011
   1100
   0011
   1100
   '''
   pattern_1_1 = [0, 0, 1, 1]
   pattern_1_2 = [1, 1, 0, 0]
   patterns[0] = [[pattern*params[0] for pattern in pattern_1_1],
               [pattern*params[0] for pattern in pattern_1_2],
               [pattern*params[0] for pattern in pattern_1_1],
               [pattern*params[0] for pattern in pattern_1_2]]
   '''
   pattern 2
   0110
   1001
   0110
   1001
   '''
   pattern_2_1 = [0, 1, 1, 0]
   pattern_2_2 = [1, 0, 0, 1]
   patterns[1] = [[pattern*params[1] for pattern in pattern_2_1],
               [pattern*params[1] for pattern in pattern_2_2],
               [pattern*params[1] for pattern in pattern_2_1],
               [pattern*params[1] for pattern in pattern_2_2]]
   '''
   pattern 3
   0101
   0101
   1010
   1010
   '''
   pattern_3_1 = [0, 1, 0, 1]
   pattern_3_2 = [1, 0, 1, 0]
   patterns[2] = [[pattern*params[2] for pattern in pattern_3_1],
               [pattern*params[2] for pattern in pattern_3_1],
               [pattern*params[2] for pattern in pattern_3_2],
               [pattern*params[2] for pattern in pattern_3_2]]
   '''
   pattern 4
   0101
   1010
   1010
   0101
   '''
   patterns[3] = [[pattern*params[3] for pattern in pattern_3_1],
               [pattern*params[3] for pattern in pattern_3_2],
               [pattern*params[3] for pattern in pattern_3_2],
               [pattern*params[3] for pattern in pattern_3_1]]
   '''
   pattern5
   1111
   1111
   1111
   1111
   '''
   patterns[4] = [[params[4] for _ in range(4)] for _ in range(4)]
   square = [[0 for _ in range(4)] for _ in range(4)]
   for pattern in patterns:
       for i in range(4):
           for j in range(4):
               square[i][j] += pattern[i][j]
   return square

Testing Our Python 4×4 Magic Square Generator

Now that we’ve made a magic square generator, let’s test our function. We will pass the parameters a list of [8, 4, 2, 1, 1] which should result in the magic square we showed right before the code.

sq = create_square([8, 4, 2, 1, 1])
for l in sq:
   print(l)

The printout from running this file with Python should look like the image below. This is the same 34 magic square we showed above. Feel free to play around with the entries in your parameter list to generate different magic squares.

Python generated 4×4 magic square

Summary of Creating a 4×4 Magic Square in Python

In this post we covered how to create a 4×4 magic square in Python. First, we covered some background information on magic squares. Magic squares are n by n squares filled with numbers. Each row, column, and diagonal adds to the same magic number.

Next, we covered the five binary encoding patterns involved in creating a 4×4 magic square before diving into the Python code. We created a function that takes one list of five parameters and makes a magic square. Each of the five parameters correspond to how we scale the patterns. We represented the five magic square patterns involved in making a 4×4 magic square as nested lists.

To finish off our magic square creation function, we create a matrix of 0s to represent the initial square and populate the square using the five magic patterns we created. Finally, we tested our magic square creator function and saw that it generated a magic square of 34 as predicted.

Further Reading

Learn More

To learn more, feel free to reach out to me @yujian_tang on Twitter, connect with me on LinkedIn, and join our Discord. Remember to follow the blog to stay updated with cool Python projects and ways to level up your Software and Python skills! If you liked this article, please Tweet it, share it on LinkedIn, or tell your friends!

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.

Yujian Tang

I started my professional software career interning for IBM in high school after winning ACSL two years in a row. I got into AI/ML in college where I published a first author paper to IEEE Big Data. After college I worked on the AutoML infrastructure at Amazon before leaving to work in startups. I believe I create the highest quality software content so that’s what I’m doing now. Drop a comment to let me know!

One-Time
Monthly
Yearly

Make a one-time donation

Make a monthly donation

Make a yearly donation

Choose an amount

$5.00
$15.00
$100.00
$5.00
$15.00
$100.00
$5.00
$15.00
$100.00

Or enter a custom amount

$

Your contribution is appreciated.

Your contribution is appreciated.

Your contribution is appreciated.

DonateDonate monthlyDonate yearly
Categories
data structures and algorithms General Python

Prim’s Algorithm in Python

Minimum Spanning Tree (MST) algorithms find the shortest path that connects all the points in a graph. Tree algorithms that find minimum spanning trees are useful in network design, taxonomies, or cluster analysis. On PythonAlgos, we’ve already covered one MST algorithm, Kruskal’s algorithm. This time we’re going to cover Prim’s algorithm for an MST.

Prim’s algorithm is similar to Kruskal’s algorithm. Whereas Kruskal’s adds to the MST by looping through edges, Prim’s adds to the MST by looping through vertices. In this post, we’ll cover how to implement Prim’s algorithm in Python through the following:

  • Pseudocode for Prim’s Algorithm for MST
  • Prim’s Algorithm in Python 
    • Creating a Graph Object
    • Print Function for MST Created by Prim’s Algorithm
    • Helper Function to Find the Minimum Vertex in Prims Algorithm
    • Prim’s Algorithm Implementation
    • Testing Our Python Implementation of Prim’s Algorithm
    • Full Code for Prim’s Algorithm in Python
  • Summary of Prims Algorithm

Psuedocode for Prim’s Algorithm for MST

Prim’s Algorithm is a graph algorithm that finds the minimum spanning tree of a graph. Our implementation will assume that the graph is connected, and therefore made up of one minimum spanning tree. Perhaps we will cover a more advanced implementation in the future.

Here’s the pseudocode for implementing Prim’s Algorithm:

  1. Pick a random point to start the graph at, in our example, we’ll start from point 0 (the first point)
  2. Go through the tree and find the point that is the shortest distance away from the current points in the MST
  3. Add the new point and update the current list of known minimum distances to the MST
  4. Repeat steps 2 and 3 until all the vertices have been added to the minimum spanning tree

Prim’s Algorithm in Python

We’re going to be using Python 3, and we won’t need any external libraries for this implementation. We will create a Graph object which will hold three properties and three functions. The properties our graph will have will be a large number representing the max possible value for an edge distance, the number of vertices in the graph, and an adjacency matrix representation of the graph.

Creating a Graph Object

The first thing we’re going to do is create a Graph object. Every other code block in this tutorial belongs inside this object. First, we create a class property called INF which represents the max value that an edge in the graph can have (or infinity). Then we’ll create the init function. 

The init function of the Graph object will take one parameter other than self, the number of vertices in the graph. It sets the instance property V to the number of vertices and creates an empty adjacency list representation of a graph with V vertices.

class Graph():
   INF = 999999
   def __init__(self, num_vertices):
       self.V = num_vertices
       self.graph = [[0 for column in range(num_vertices)] for row in range(num_vertices)]

Print Function for MST Created by Prim’s Algorithm

Now that we’ve finished the initial creation of our graph, let’s write the functions we need for Prim’s algorithm. In this section, we’ll create a function that prints the edges and weights of the MST that we find using Prim’s algorithm.

This function takes one parameter, parent. It expects parent to be a list of indices corresponding to the parent node of each index. Then it prints out a line that shows that we’re going to first print the edge, a tab, then the weight. Finally, we’ll loop through all the vertices from 1 (the root vertex, 0, has no parent node), until the end and print out the edge, a tab, then the weight.

   # pretty print of the minimum spanning tree
   # prints the MST stored in the list var `parent`
   def printMST(self, parent):
       print("Edge     Weight")
       for i in range(1, self.V):
           print(f"{parent[i]} - {i}       {self.graph[i][parent[i]]}")

Helper Function for Finding the Minimum Vertex in Prim’s

Now let’s create the helper function to find the next minimum distance vertex to add in Prim’s algorithm. This function takes two parameters, a list of distances called key, and a list representing whether a vertex, represented by the truth value at an index, is in the MST already.

The first thing we’ll do in this function is set a min value which represents the minimum edge distance to a vertex that we’ve found so far. We will initially set this value to the INF property we declared earlier. 

Next, we’ll loop through the list of vertices and check if the distance to a vertex in the key list is less than the current minimum and the vertex is not in the minimum spanning tree. If it is, then we’ll set the new minimum value to be the distance and the current minimum index to be the vertex being iterated on. After looping through each point, we’ll return the minimum index.

   # finds the vertex with the minimum distance value
   # takes a key and the current set of nodes in the MST
   def minKey(self, key, mstSet):
       min = self.INF
       for v in range(self.V):
           if key[v] < min and mstSet[v] == False:
               min = key[v]
               min_index = v
       return min_index

Prim’s Algorithm Implementation

Alright, let’s get to the fun part, the actual implementation of Prim’s algorithm. This Python implementation doesn’t take any parameters other than the object itself. The first things we’re going to do are initialize the list of distances, parent nodes, MST nodes, and their values.

The initial list of distances to existing nodes should be set to the max value, INF, for each node in the range of vertices. We’ll set the distance to the initial node, 0, to 0 to start the MST. The list of parent nodes should be set to None for each of the nodes, then we’ll set the parent node for the initial node, 0, to -1 to show it does not exist. Finally, we’ll create a truth value list where the truth value of each index represents whether that vertex is in the minimum spanning tree yet.

Now we’ll create the outer loop of vertices. In each iteration of this loop we’ll be adding a vertex to the MST. In this loop, we first find the vertex with the minimum distance using the minKey helper function we wrote earlier. Next, we’ll set the index of that vertex in the MST list to True.

Once we’ve selected the next vertex to add to the MST, we’ll sort out the keys which show the distances of the connectable vertices and the parent list. We’ll create another loop that goes through each vertex. This loop will check for all the new connectable vertices and new minimum distances based on the newly added vertex and update everything in the existing lists.

   # prim's algo, graph is represented as an v by v adjacency matrix
   def prims(self):
       # used to pick minimum weight edge
       key = [self.INF for _ in range(self.V)]
       # used to store MST
       parent = [None for _ in range(self.V)]
       # pick a random vertex, ie 0
       key[0] = 0
       # create list for t/f if a node is connected to the MST
       mstSet = [False for _ in range(self.V)]
        # set the first node to the root (ie have a parent of -1)
       parent[0] = -1
 
       for _ in range(self.V):
           # 1) pick the minimum distance vertex from the current key
           # from the set of points not yet in the MST
           u = self.minKey(key, mstSet)
           # 2) add the new vertex to the MST
           mstSet[u] = True
 
           # loop through the vertices to update the ones that are still
           # not in the MST
           for v in range(self.V):
               # if the edge from the newly added vertex (v) exists,
               # the vertex hasn't been added to the MST, and
               # the new vertex's distance to the graph is greater than the distance
               # stored in the initial graph, update the "key" value to the
               # distance initially given and update the parent of
               # of the vertex (v) to the newly added vertex (u)
               if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]:
                   key[v] = self.graph[u][v]
                   parent[v] = u
 
       self.printMST(parent)

Testing Our Python Implementation of Prim’s Algorithm

Let’s test out our Python implementation of Prim’s algorithm via a graph object on a graph of size five. Before we get into testing the code, let’s take a look at a visual representation of our graph and the expected MST.

Visual representation of the graph that we will be applying our Python implementation of Prim’s algorithm on:

Example Graph to Build an MST from Prims Algorithm

Expected Minimum Spanning Tree Yielded by Prims Algorithm:

Expected MST from Prim’s Algorithm

Now let’s take a look at the code and the output from our implementation.

g = Graph(5)
g.graph = [ [0, 2, 0, 6, 0],
           [2, 0, 3, 8, 5],
           [0, 3, 0, 0, 7],
           [6, 8, 0, 0, 9],
           [0, 5, 7, 9, 0]]
 
g.prims()

The expected print output for our Python implementation of Prim’s Algorithm:

Prim’s Algorithm’s MST

Full Code for Prim’s Algorithm in Python

Here’s the full code for Prim’s Algorithm in Python.

class Graph():
   INF = 999999
   def __init__(self, num_vertices):
       self.V = num_vertices
       self.graph = [[0 for column in range(num_vertices)] for row in range(num_vertices)]
      
   # pretty print of the minimum spanning tree
   # prints the MST stored in the list var `parent`
   def printMST(self, parent):
       print("Edge     Weight")
       for i in range(1, self.V):
           print(f"{parent[i]} - {i}       {self.graph[i][parent[i]]}")
  
   # finds the vertex with the minimum distance value
   # takes a key and the current set of nodes in the MST
   def minKey(self, key, mstSet):
       min = self.INF
       for v in range(self.V):
           if key[v] < min and mstSet[v] == False:
               min = key[v]
               min_index = v
       return min_index
  
   # prim's algo, graph is represented as an v by v adjacency matrix
   def prims(self):
       # used to pick minimum weight edge
       key = [self.INF for _ in range(self.V)]
       # used to store MST
       parent = [None for _ in range(self.V)]
       # pick a random vertex, ie 0
       key[0] = 0
       # create list for t/f if a node is connected to the MST
       mstSet = [False for _ in range(self.V)]
        # set the first node to the root (ie have a parent of -1)
       parent[0] = -1
 
       for _ in range(self.V):
           # 1) pick the minimum distance vertex from the current key
           # from the set of points not yet in the MST
           u = self.minKey(key, mstSet)
           # 2) add the new vertex to the MST
           mstSet[u] = True
 
           # loop through the vertices to update the ones that are still
           # not in the MST
           for v in range(self.V):
               # if the edge from the newly added vertex (v) exists,
               # the vertex hasn't been added to the MST, and
               # the new vertex's distance to the graph is greater than the distance
               # stored in the initial graph, update the "key" value to the
               # distance initially given and update the parent of
               # of the vertex (v) to the newly added vertex (u)
               if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]:
                   key[v] = self.graph[u][v]
                   parent[v] = u
 
       self.printMST(parent)
 
g = Graph(5)
g.graph = [ [0, 2, 0, 6, 0],
           [2, 0, 3, 8, 5],
           [0, 3, 0, 0, 7],
           [6, 8, 0, 0, 9],
           [0, 5, 7, 9, 0]]
 
g.prims()

Summary of Prims Algorithm

In this post on Prim’s algorithm in Python, we learned that Prim’s is a minimum spanning tree graph algorithm. Prim’s algorithm creates a MST by adding the nearest vertex one after another. We looked at the psuedocode for Prim’s algorithm, and then created a Python graph class that implements Prim’s. Finally, we tested our implementation on a five vertex graph.

Further Reading

Learn More

To learn more, feel free to reach out to me @yujian_tang on Twitter, connect with me on LinkedIn, and join our Discord. Remember to follow the blog to stay updated with cool Python projects and ways to level up your Software and Python skills! If you liked this article, please Tweet it, share it on LinkedIn, or tell your friends!

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.

Yujian Tang

I started my professional software career interning for IBM in high school after winning ACSL two years in a row. I got into AI/ML in college where I published a first author paper to IEEE Big Data. After college I worked on the AutoML infrastructure at Amazon before leaving to work in startups. I believe I create the highest quality software content so that’s what I’m doing now. Drop a comment to let me know!

One-Time
Monthly
Yearly

Make a one-time donation

Make a monthly donation

Make a yearly donation

Choose an amount

$5.00
$15.00
$100.00
$5.00
$15.00
$100.00
$5.00
$15.00
$100.00

Or enter a custom amount

$

Your contribution is appreciated.

Your contribution is appreciated.

Your contribution is appreciated.

DonateDonate monthlyDonate yearly
Categories
Uncategorized

Slicing Python Strings: A Complete Guide

Python comes with a string slicing system that is a Swiss army knife of functionality. Bracket notation allows us to slice Python strings to get one or more characters in order or in reverse. In this complete guide on slicing Python strings we’ll cover:

  • Slicing a Single Character from a Python String
  • Using a Negative Index While Slicing Python Strings
  • Slicing Python Strings by Position
  • Slicing a Python String for Every n Indices

Before we get into how to slice Python strings, we have to have some context on the string to slice. So the first thing we’ll do in our program is declare the string. For this example, let’s use abcdefg.

s = "abcdefg"

Slicing Python Strings: A Single Character

The most basic way to slice Python strings is to slice for a single character. Remember that strings start at index 0. In the example below we are slicing for index number 3, which is the fourth character, d.

# any character
print(s[3]) # expect d

Slicing Python Strings: Negative Indices

Unlike Java or C#, negative indices are permitted in Python. Negative indices are a neat trick that allow you to access the character n from the end. For example, in the line below we’ll access the character second from the end, f.

# negative indices
print(s[-2]) # expect second to last = f

Slicing Python Strings: Substrings By Position

Now let’s take a look at slicing Python strings by position. You can slice by position in Python using the colon operator. We’ll cover two examples of how to slice by position. 

First, we’ll slice from positions one to four, which will get us entries one, two and three, bcd. Python string slicing is inclusive for the first index, but exclusive on the second one. For our second example, we’ll leave the first index blank, which will default our slice to the start of the string, index zero. This will get us the first two entries, ab.

# slicing positions
print(s[1:4]) # expect 1, 2, 3 = bcd
print(s[:2]) # expect beginning to 1 = ab

Slicing Python Strings: Slicing Positions n at a time

Lastly, let’s take a look at slicing Python strings for every nth entry. We do this by adding a second colon inside the brackets. Here we’ll cover four examples of slicing Python strings for every nth entry.

First, we’ll slice from index zero to the end by two, which should get us aceg. Next, we’ll slice from index zero to seven by three or adg. Note that there are seven total letters in the string which means there are only indices zero to six. However, the closing end of indices when slicing strings in Python is open so we end our slice on seven.

Third, we’ll slice backwards from indices five to one by negative one, fedc. Finally, we’ll cover slicing from the second to last index to the fifth to last index by two or fd.

# slicing positions _n_ at a time
print(s[0::2]) # expect every 2 from 0 to end = aceg
print(s[0:7:3]) # expect every 3 from 0 to 6 = adg
print(s[5:1:-1]) # expect reverse entries from 5 to 2 = fedc
print(s[-2:-5:-2]) # expect reverse every other entry from second to fifth to last = fd

Results from Python String Slicing

When we run all those lines for the string abcdefg, we should get the results as commented. The output will look like the image below.

Slicing Python Strings Example Outputs

Summary of Slicing Python Strings

In this post we went over how to slice Python strings forward, backwards, and while skipping count. First, we learned how to slice a single character out of a string. Then we looked at using negative indices. Next, we looked at how to slice substrings by position and for every nth index.

More Resources

Learn More

To learn more, feel free to reach out to me @yujian_tang on Twitter, connect with me on LinkedIn, and join our Discord. Remember to follow the blog to stay updated with cool Python projects and ways to level up your Software and Python skills! If you liked this article, please Tweet it, share it on LinkedIn, or tell your friends!

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.

Yujian Tang

I started my professional software career interning for IBM in high school after winning ACSL two years in a row. I got into AI/ML in college where I published a first author paper to IEEE Big Data. After college I worked on the AutoML infrastructure at Amazon before leaving to work in startups. I believe I create the highest quality software content so that’s what I’m doing now. Drop a comment to let me know!

One-Time
Monthly
Yearly

Make a one-time donation

Make a monthly donation

Make a yearly donation

Choose an amount

$5.00
$15.00
$100.00
$5.00
$15.00
$100.00
$5.00
$15.00
$100.00

Or enter a custom amount

$

Your contribution is appreciated.

Your contribution is appreciated.

Your contribution is appreciated.

DonateDonate monthlyDonate yearly
Categories
data structures and algorithms level 1 python

Graph Algorithms: Kruskal’s Algorithm in Python

Data structures and algorithms are a cornerstone of computer science. In our journey so far, we’ve looked at basic data structures like stacks, queues, and dequeues, linked lists and binary trees, and algorithms like sorting algorithms, tree algorithms, and Dijsktra’s algorithm. Now, let’s take a look at another important graph algorithm – Kruskal’s.

Kruskal’s algorithm is an algorithm that finds the minimum spanning tree (MST) of a graph. In this post we’ll cover:

  • Kruskal’s Algorithm Pseudocode
  • Kruskal’s Algorithm in Python
    • Creating a Graph Object
    • Python Union Find Algorithm
    • Implementing Kruskal’s Algorithm in Python
    • Full Python Code for Kruskal’s Graph Algorithm
    • Testing Kruskal’s Algorithm in Python
  • Summary of Kruskal’s Algorithm in Python

Kruskal’s Algorithm Pseudocode

Kruskal’s algorithm uses a greedy approach to build a minimum spanning tree. Let’s take a look at the pseudocode:

  1. Initialize a graph using the shortest (lowest weight) edge
  2. Find the shortest connected edge and add it to the shortest edges so far as long as adding the edge doesn’t create a cycle in the graph
  3. Repeat step 2 until all vertices have been included in the final MST

Kruskal’s Algorithm in Python

Let’s go over how to implement Kruskal’s Algorithm in Python. This implementation of Kruskal’s Algorithm is going to be as a function in a Graph object. We’ll create a Graph object that will hold the number of vertices in the graph as well as an adjacency list that represents the graph. 

Each entry in the adjacency list will have three entries, the two vertices and the weight of the edge between them. We also need to create functions to perform the find and union pieces of the union find algorithm.

Creating a Graph Object in Python

The first thing we’ll need to do is create our Graph object. All the functions we define later in the tutorial are a part of this object. We need an __init__ function and a function to add an edge. The __init__ function takes one parameter, the number of vertices. It sets one of the object properties to the number of vertices and creates an empty adjacency list to represent the edges in the graph.

class Graph(object):
   def __init__(self, num_vertices):
       self.V = num_vertices
       self.graph = []
  
   def add_edge(self, u, v, w):
       self.graph.append([u, v, w])

Python Union Find Algorithm

Union Find is an algorithm to find the sets of connected graphs. This algorithm consists of two separate functions, the find and union functions. The find function needs two parameters, and the union function needs four parameters.

The find function takes a list that keeps track of the minimum spanning tree and a vertex number. If the index in the MST list is equivalent to the passed in vertex, then we return the vertex number. Otherwise, we recursively look for the vertex by calling the find function with the same list, but with the new index corresponding to the value of the index of the vertex in the MST list.

The union function’s four parameters are the MST list, another list that marks the number of disjoint sets and the origin of those sets, and two vertices. First, we look for where the vertices are in terms of the MST. Then, we compare the values of the indices of the set tracking list and change the corresponding value in the MST list depending on the value comparison. If the values in the MST list are different, then the index of the smaller value is set to the higher value and vice versa. If they are the same, then we create a new disjoint set.

   # union find
   def find(self, root, i):
       if root[i] == i:
           return i
       return self.find(root, root[i])
  
   def union(self, root, rank, x, y):
       xroot = self.find(root, x)
       yroot = self.find(root, y)
       if rank[xroot] < rank[yroot]:
           root[xroot] = yroot
       elif rank[xroot] > rank[yroot]:
           root[yroot] = xroot
       else:
           root[yroot] = xroot
           rank[xroot] += 1

Implementing Kruskal’s Algorithm in Python

Now we have our helper functions, let’s take a look at how we can implement Kruskal’s algorithm in Python. We already have the two objects we need to perform Kruskal’s algorithm so this function does not need any parameters.

The first thing we’ll need to do in our Kruskal’s function is initialize the results list, which will contain the MST and will be structured the same as the list of the vertices and edge weights. We also need to initialize the iterations and number of edges added to the MST. Then, we’ll sort the adjacency list representing the graph by the weights of the algorithm.

Now, we’ll initialize the lists that will represent the root nodes of the sets we’ve found (root) and the list of the number of connected sets in the graph represented by the root node (rank). We’ll then populate the two lists.

Next, we’ll run a while loop that runs as long as we haven’t added the expected number of edges to the MST. In the while loop, we’ll start by extracting the vertices and edge weight between them corresponding to the graph index of the iteration we’re in. Now, we’ll use the find function to see if either or both vertices are connected to the graph.

If only one vertex is connected to the graph (x is not equal to y), then we increment the number of edges we’ve found in the MST, add the set of vertices and edge weights to the results list, and run the union algorithm to keep track of the MST and number of sets. When the MST is created, we’ll print it out.

   # applying kruskal's
   def kruskals(self):
       # initialize an empty MST list
       result = []
       # initialize i, the iteration and e, the edges added
       i, e  = 0, 0
       # sort the graph based on edge weights
       self.graph = sorted(self.graph, key = lambda item: item[2])
       # initialize root, which keeps track of the MST
       # and the rank, which keeps track of where each node belongs
       root = []
       rank = []
       for node in range(self.V):
           root.append(node)
           rank.append(0)
 
       # while we haven't yet added each edge
       # increment iterator and run the union find algorithm
       while e < self.V - 1:
           u, v, w = self.graph[i]
           i = i + 1
           x = self.find(root, u)
           y = self.find(root, v)
           print(f"x, y: {x}, {y}")
           if x != y:
               e = e + 1
               result.append([u, v, w])
               self.union(root, rank, x, y)
 
       for u, v, w in result:
           print(f'{u} - {v}: {w}')

Full Kruskal’s Graph Algorithm Python Code

Here’s the full code for Kruskal’s Algorithm in Python implemented with a Graph class:

# kruskal's in Python
class Graph(object):
   def __init__(self, num_vertices):
       self.V = num_vertices
       self.graph = []
  
   def add_edge(self, u, v, w):
       self.graph.append([u, v, w])
  
   # union find
   def find(self, root, i):
       if root[i] == i:
           return i
       print(i, root[i])
       return self.find(root, root[i])
  
   def union(self, root, rank, x, y):
       print(f"root: {root}, rank: {rank}")
       xroot = self.find(root, x)
       yroot = self.find(root, y)
       if rank[xroot] < rank[yroot]:
           root[xroot] = yroot
       elif rank[xroot] > rank[yroot]:
           root[yroot] = xroot
       else:
           root[yroot] = xroot
           rank[xroot] += 1
       print(f"root: {root}, rank: {rank}")
  
   # applying kruskal's
   def kruskals(self):
       # initialize an empty MST list
       result = []
       # initialize i, the iteration and e, the edges added
       i, e  = 0, 0
       # sort the graph based on edge weights
       self.graph = sorted(self.graph, key = lambda item: item[2])
       # initialize root, which keeps track of the MST
       # and the rank, which keeps track of where each node belongs
       root = []
       rank = []
       for node in range(self.V):
           root.append(node)
           rank.append(0)
 
       # while we haven't yet added each edge
       # increment iterator and run the union find algorithm
       while e < self.V - 1:
           u, v, w = self.graph[i]
           i = i + 1
           x = self.find(root, u)
           y = self.find(root, v)
           print(f"x, y: {x}, {y}")
           if x != y:
               e = e + 1
               result.append([u, v, w])
               self.union(root, rank, x, y)
 
       for u, v, w in result:
           print(f'{u} - {v}: {w}')

Testing Kruskal’s Algorithm in Python

Now let’s test Kruskal’s Algorithm. We’ll create the following graph:

Kruskal’s Algorithm Python Test, Initial Graph
g = Graph(6)
g.add_edge(0, 1, 4)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 2)
g.add_edge(1, 0, 4)
g.add_edge(2, 0, 4)
g.add_edge(2, 1, 2)
g.add_edge(2, 3, 3)
g.add_edge(2, 5, 2)
g.add_edge(2, 4, 4)
g.add_edge(3, 2, 3)
g.add_edge(3, 4, 3)
g.add_edge(4, 2, 4)
g.add_edge(4, 3, 3)
g.add_edge(5, 2, 2)
g.add_edge(5, 4, 3)
g.kruskals()

This will print out something like the image below.

Kruskal’s Minimum Spanning Tree Representation

The MST should correspond to this graph:

Kruskal’s Algorithm Python Generated Minimum Spanning Tree Example

Summary of Kruskal’s Algorithm in Python

Kruskal’s algorithm builds a minimum spanning tree of a graph through adding the minimum weighted edges in a greedy manner. We implemented Kruskal’s algorithm in Python by creating a Graph object and adding functions to it to use the union find algorithm to run Kruskal’s algorithm.

Further Reading

Learn More

To learn more, feel free to reach out to me @yujian_tang on Twitter, connect with me on LinkedIn, and join our Discord. Remember to follow the blog to stay updated with cool Python projects and ways to level up your Software and Python skills! If you liked this article, please Tweet it, share it on LinkedIn, or tell your friends!

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.

Yujian Tang

I started my professional software career interning for IBM in high school after winning ACSL two years in a row. I got into AI/ML in college where I published a first author paper to IEEE Big Data. After college I worked on the AutoML infrastructure at Amazon before leaving to work in startups. I believe I create the highest quality software content so that’s what I’m doing now. Drop a comment to let me know!

One-Time
Monthly
Yearly

Make a one-time donation

Make a monthly donation

Make a yearly donation

Choose an amount

$5.00
$15.00
$100.00
$5.00
$15.00
$100.00
$5.00
$15.00
$100.00

Or enter a custom amount

$

Your contribution is appreciated.

Your contribution is appreciated.

Your contribution is appreciated.

DonateDonate monthlyDonate yearly
Categories
data structures and algorithms

Graph Algorithms: Floyd Warshall in Python

Data structures and algorithms are a cornerstone of computer science. In our journey so far, we’ve looked at basic data structures like stacks, queues, and dequeues, linked lists and binary trees, and algorithms like sorting algorithms, tree algorithms, and Dijsktra’s algorithm. Now, let’s take a look at another important graph algorithm – Floyd Warshall.

In this post, we’ll take a look at:

  • Floyd Warshall Pseudocode
  • Floyd Warshall Algorithm in Python
    • Define Constants and Create Examples
    • Implementing Floyd Warshall in Python
    • Testing Floyd Warshall in Python
  • Summary of Floyd Warshall Algorithm in Python

Floyd Warshall Pseudocode

Floyd Warshall is a simple graph algorithm that maps out the shortest path from each vertex to another using an adjacency graph. It takes a brute force approach by looping through each possible vertex that a path between two vertices can go through. 

Let’s take a look at the pseudocode:

  1. Pick a vertex – v
  2. Calculate distance for each set of vertices
  3. If the distance through vertex v is less than the currently recorded distance between two vertices, replace that distance
  4. Repeat steps 1 through 3 for each vertex

Note that Floyd Warshall will not work for any graph with negative edge weights. It’s also useless for unweighted and directed graphs.

Floyd Warshall Algorithm in Python

We’re going to implement the Floyd Warshall Algorithm in Python. First we’re going to define any constants we need and create some example adjacency lists, then we’ll define and implement the Floyd Warshall algorithm, finally we’ll test it.

Define Constants and Create Examples

The only constant we need to define for Floyd Warshall is “infinity”. Technically, we could also import the infinity constant from the math module, but the behavior will be the same as long as we define an infinity that is greater than any individual distance between vertices. Most of the time, we won’t be working with graphs with distances of greater than 99999 between vertices so we’ll use that as our infinity value. 

Then we’ll create two examples. These graphs will have 0 in the diagonal since the distance from a point to itself is 0, and we’ll also throw in some infinities into our adjacency graph to represent unconnected vertices.

# define "infinity"
_inf = 99999
 
# example 1
A = [[0, 5, _inf, _inf],
    [50, 0, 15, 5],
    [30, _inf, 0, 15],
    [15, _inf, 5, 0]]
 
# example 2
B = [[0, 3, _inf, 5],
    [2, 0, _inf, 4],
    [_inf, 1, 0, _inf],
    [_inf, _inf, 2, 0]]

These examples should give us:

[0, 5, 15, 10]
[20, 0, 10, 5]
[30, 35, 0, 15]
[15, 20, 5, 0]

and

[0, 3, 7, 5]
[2, 0, 6, 4]
[3, 1, 0, 5]
[5, 3, 2, 0]

Implementing Floyd Warshall in Python

Now that we’ve defined our constant and created our example, we’ll implement the Floyd Warshall algorithm in Python. First, we’ll get the number of vertices that we’re dealing with by getting the length of the graph. Next, we’ll create our loops. 

We need three layers of for loops that will loop through each vertex three times and replace the entry in the graph by the minimum distance between the direct distance between two vertices and the distance between those vertices that goes through the initially defined vertex (in the outermost loop). Finally, we’ll print out the list of lengths for each row in the graph.

# floyd warshall function
def floyd_warshall(graph):
​​   n = len(graph)
   # stepping loop
   for k in range(n):
       # outer loop
       for i in range(n):
           # inner loop
           for j in range(n):
               # replace direct path with path through k if direct path is longer
               graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
   # print complete graph in a pretty manner
   for row in graph:
       print(row)

Testing Floyd Warshall in Python

Now that we’ve implemented the Floyd Warshall algorithm, let’s take a look at how our algorithm does against the expected solutions we saw above. All we do is call Floyd Warshall on each of the graphs we made and check what the solution prints.

print("Shortest Paths Graph for A")
floyd_warshall(A)
print("Shortest Paths Graph for B")
floyd_warshall(B)

We should see an output like the image below.

Floyd Warshall Algorithm Results

Summary of Floyd Warshall Algorithm in Python

In this post we went over how to implement Floyd Warshall in Python. We walked through the pseudocode and then the actual implementation. The Floyd Warshall algorithm loops through each vertex three times. First it loops through a chosen vertex, then it loops through sets of two vertices that define the distance between them. While looping, it replaces the distance between two vertices with the minimum between the existing distance and the distance between the chosen vertex.

Further Reading

Learn More

To learn more, feel free to reach out to me @yujian_tang on Twitter, connect with me on LinkedIn, and join our Discord. Remember to follow the blog to stay updated with cool Python projects and ways to level up your Software and Python skills! If you liked this article, please Tweet it, share it on LinkedIn, or tell your friends!

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.

Yujian Tang

I started my professional software career interning for IBM in high school after winning ACSL two years in a row. I got into AI/ML in college where I published a first author paper to IEEE Big Data. After college I worked on the AutoML infrastructure at Amazon before leaving to work in startups. I believe I create the highest quality software content so that’s what I’m doing now. Drop a comment to let me know!

One-Time
Monthly
Yearly

Make a one-time donation

Make a monthly donation

Make a yearly donation

Choose an amount

$5.00
$15.00
$100.00
$5.00
$15.00
$100.00
$5.00
$15.00
$100.00

Or enter a custom amount

$

Your contribution is appreciated.

Your contribution is appreciated.

Your contribution is appreciated.

DonateDonate monthlyDonate yearly
Categories
General Python level 1 python

Nested Lists in Python

Nested lists are Python representations of two dimensional arrays. They are used to represent lists of lists. For example, a list of grocery lists for the month or matrices we can multiply. In this post we’re going to go over how to use Python to create and manipulate nested lists.

We’ll go over:

Python Nested Lists

The easiest way to create a nested list in Python is simply to create a list and put one or more lists in that list. In the example below we’ll create two nested lists. First, we’ll create a nested list by putting an empty list inside of another list. Then, we’ll create another nested list by putting two non-empty lists inside a list, separated by a comma as we would with regular list elements.

# create a nested list
nlist1 = [[]]
nlist2 = [[1,2],[3,4,5]]

List Comprehension with Python Nested Lists

We can also create nested lists with list comprehension. List comprehension is a way to create lists out of other lists. In our example below, we’ll create two lists with list comprehension in two ways.

First we’ll create a nested list using three separate list comprehensions. Second, we’ll create a nested list with nest list comprehension.

# create a list with list comprehension
nlist_comp1 = [[i for i in range(5)], [i for i in range(7)], [i for i in range(3)]]
nlist_comp2 = [[i for i in range(n)] for n in range(3)]
print(nlist_comp1)
print(nlist_comp2)

The results of the two lists should be: 

  • [[0, 1, 2, 3, 4], [0, 1, 2, 3, 4, 5, 6], [0, 1, 2]]
  • [[], [0], [0, 1]]

Adding Lists to a Two Dimensional Array

Now that we’ve learned how to create nested lists in Python, let’s take a look at how to add lists to them. We work with nested lists the same way we work with regular lists. We can add an element to a nested list with the append() function. In our example, we create a list and append it to one of our existing lists from above.

# append a list
list1 = [8, 7, 6]
nlist_comp1.append(list1)
print(nlist_comp1)

This should result in this list: [[0, 1, 2, 3, 4], [0, 1, 2, 3, 4, 5, 6], [0, 1, 2], [8, 7, 6]]

Concatenating Two Dimensional Lists in Python

Other than adding a list to our 2D lists, we can also add or concatenate two nested lists together. List concatenation in Python is quite simple, all we need to do is add them with the addition sign. Adding nested lists works the same way as adding plain, unnested lists. In our example, we’ll add the two lists we created using list comprehension together.

# concat nested lists
concat_nlist = nlist_comp1 + nlist_comp2
print(concat_nlist)

The list we should see from this is: [[0, 1, 2, 3, 4], [0, 1, 2, 3, 4, 5, 6], [0, 1, 2], [8, 7, 6], [], [0], [0, 1]]

How to Reverse a Nested List in Python

Now that we’ve created, added to, and concatenated nested lists, let’s reverse them. There are multiple ways to reverse nested lists, including creating a reversed copy or using list comprehension. In this example though, we’ll reverse a list in place using the built-in reverse() function. 

# reverse a nested list
concat_nlist.reverse()
print(concat_nlist)

This should print out the nested list: [[0, 1], [0], [], [8, 7, 6], [0, 1, 2], [0, 1, 2, 3, 4, 5, 6], [0, 1, 2, 3, 4]]

Reversing the Sub Elements of a Nested List

Okay, so we can easily reverse a list using the reverse function. What if we want to reverse the sub elements of a nested list? We can reverse each of the lists in a nested list by looping through each list in the nested list and calling the reverse function on it.

# reverse sub elements of nested list
for _list in concat_nlist:
   _list.reverse()
print(concat_nlist)

If we call the above code on the original concatenated list, we will see this list: [[4, 3, 2, 1, 0], [6, 5, 4, 3, 2, 1, 0], [2, 1, 0], [6, 7, 8], [], [0], [1, 0]]

Reverse the Sub Elements and the Elements of a 2D Python Array

Now we can reverse the elements in a 2D list as well as reverse the elements of each nested list, we can put them together. To reverse the sub elements and the elements of a 2D list in Python, all we do is loop through each of the inside lists and reverse them, and then reverse the outside list after the loop. We can also do it in the reverse order.

# reverse sub elements + elements of a nested list
for _list in concat_nlist:
   _list.reverse()
concat_nlist.reverse()
print(concat_nlist)

Running this on the original concat_nlist should give: [[1, 0], [0], [], [6, 7, 8], [2, 1, 0], [6, 5, 4, 3, 2, 1, 0], [4, 3, 2, 1, 0]]

Turning a 2D List into a Normal List

So far, we’ve learned how to create, add to and together, and reverse a two-dimensional list in Python. Now, let’s take a look at turning that 2D list into a normal or flattened list. In this example, we’ll use list comprehension to extract each element from each sublist in the list.

# flatten list
flat_list = [ele for sublist in concat_nlist for ele in sublist]
print(flat_list)

When running the above code to flatten a list on the original concatenated lists, we should get this list: [0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 8, 7, 6, 0, 0, 1]

Reverse a Flattened Nested List Python

Let’s put it all together. We just flattened our 2D Python array into a one-dimensional list. Earlier, we reversed our 2D list. Now, let’s reverse our flattened list. Just like with the 2D list, all we have to do to reverse our flattened list is run the reverse function on the flattened list.

# reverse elements of a flattened list
flat_list.reverse()
print(flat_list)

After running the reverse function on the list we flattened above, we should get: [1, 0, 0, 6, 7, 8, 2, 1, 0, 6, 5, 4, 3, 2, 1, 0, 4, 3, 2, 1, 0]

Summary of Python Nested Lists

In this post about nested lists in Python we learned how to create, manipulate, and flatten nested lists. First we learned how to simply create nested lists by just putting lists into a list, then we learned how to create nested lists through list comprehension. 

Next, we learned how to do some manipulation of 2D arrays in Python. First, how to append a list, then how to concatenate two lists, and finally, how to reverse them. Lastly, we learned how to flatten a 2D list and reverse it.

Further Reading

Learn More

To learn more, feel free to reach out to me @yujian_tang on Twitter, connect with me on LinkedIn, and join our Discord. Remember to follow the blog to stay updated with cool Python projects and ways to level up your Software and Python skills! If you liked this article, please Tweet it, share it on LinkedIn, or tell your friends!

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.

Yujian Tang

I started my professional software career interning for IBM in high school after winning ACSL two years in a row. I got into AI/ML in college where I published a first author paper to IEEE Big Data. After college I worked on the AutoML infrastructure at Amazon before leaving to work in startups. I believe I create the highest quality software content so that’s what I’m doing now. Drop a comment to let me know!

One-Time
Monthly
Yearly

Make a one-time donation

Make a monthly donation

Make a yearly donation

Choose an amount

$5.00
$15.00
$100.00
$5.00
$15.00
$100.00
$5.00
$15.00
$100.00

Or enter a custom amount

$

Your contribution is appreciated.

Your contribution is appreciated.

Your contribution is appreciated.

DonateDonate monthlyDonate yearly
Categories
General Python level 1 python

Level 1 Python: Pure Python Matrix Multiplication

Level 1 Python projects are projects that are more logically complex or require more libraries than the ones in the Super Simple Python series. Pure Python matrix multiplication is one of the projects that is more logically complex, we won’t be using any external libraries here. Most of these projects should take you between 30 to 45 minutes to build.

Matrix multiplication is an important part of linear algebra and machine learning. It’s actually quite easy to do in Python using the numpy library. However, it’s also useful to understand how matrix multiplication actually works. That’s why we’ll be taking a look at how we can do matrix multiplication with pure Python in this post.

In this post, we’ll cover:

  • Creating Some Example Matrices for Python matrix multiplication
  • Validate Matrices Being Multiplied
  • Pure Python Matrix Multiplication with Lists

Creating Some Example Matrices for Python Matrix Multiplication

In order to do matrix multiplication in pure Python, we’ll need to represent the matrices using native Python types. We’ll represent the matrices with lists of lists. Each entry in the outside list corresponds to a row in the matrix. Each entry in the inside list corresponds to a value in the matrix. 

For our example, we’ll create some square matrices to multiply for example. We’ll create two four by four matrices and two two by two matrices and multiply the four by fours by each other and the two by twos by each other.

mat_a = [[1, 2, 3, 4],
        [2, 4, 1, 3],
        [4, 2, 3, 1],
        [3, 1, 4, 2]]
 
mat_b = [[4, 2, 1, 3],
        [3, 4, 1, 2],
        [1, 2, 4, 3],
        [2, 1, 3, 4]]
 
# expected result:
# [[21, 20, 27, 32],
#  [27, 25, 19, 29],
#  [27, 23, 21, 29],
#  [23, 20, 26, 31]]
 
mat_c = [[1, 2],
        [2, 1]]
 
mat_d = [[3, 4],
        [4, 3]]
 
# expected result:
# [[11, 10],
#  [10, 11]]

Validate Matrices Being Multiplied

Before we attempt matrix multiplication, we should validate that it’s possible to multiply the matrices. An n x m matrix can only be multiplied by an m x p matrix. That means that the number of rows in the first matrix must be equal to the number of columns in the second matrix. This is due to the way that matrix multiplication works. When we multiply matrices, we sum the products of each row multiplied by each column.

We’ll create a validation function that takes two parameters. The first parameter is the first matrix and the second parameter is the second matrix. It’s important that these are in order because matrix multiplication is not commutative.

def validate(mat_a, mat_b):
   len_a = len(mat_a)
   len_b = len(mat_b[0])
   assert len_a == len_b

Pure Python Matrix Multiplication with Lists

Now that we’ve got some example matrices and a validation function, let’s create the function to actually do the matrix multiplication. Our matrix multiplication function will take two parameters. The first thing we’ll do is validate that the matrices can be multiplied. 

After validation, we’ll make matrix B easier to deal with in multiplication. To do this, we’ll zip it up into a tuple of tuples, and then wrap that in a list so we end up with a list of tuples. This is what allows us to easily access columns of B. 

Next, we’ll use list comprehension to do our pure Python matrix multiplication calculations. We’ll create a list of lists. The internal list is a sum of products for each entry in a row of A and a column of B for each column of B in the zipped iterable of matrix B. The external list is created based on each row of A in matrix A.

def mat_mul(mat_a, mat_b):
   validate(mat_a, mat_b)
   # turn matrix b into a list of tuples
   iterable_b = list(zip(*mat_b))
   return [[sum(a*b for a, b in zip(row_a, col_b)) for col_b in iterable_b] for row_a in mat_a]
 
print(mat_mul(mat_a, mat_b))
print(mat_mul(mat_c, mat_d))

This is what we should see in our output:

Pure Python Matrix Multiplication Results

Summary of Matrix Multiplication in Pure Python

In this post we learned how to do matrix multiplication with pure Python and no libraries. First we created a couple sets of matrices to multiply. Then we created a validation function to ensure that the two matrices passed to the function would be multipliable. Finally, we created a function to do the matrix multiplication using list comprehension and the zip function in Python.

Further Readings

Learn More

To learn more, feel free to reach out to me @yujian_tang on Twitter, connect with me on LinkedIn, and join our Discord. Remember to follow the blog to stay updated with cool Python projects and ways to level up your Software and Python skills! If you liked this article, please Tweet it, share it on LinkedIn, or tell your friends!

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.

Yujian Tang

I started my professional software career interning for IBM in high school after winning ACSL two years in a row. I got into AI/ML in college where I published a first author paper to IEEE Big Data. After college I worked on the AutoML infrastructure at Amazon before leaving to work in startups. I believe I create the highest quality software content so that’s what I’m doing now. Drop a comment to let me know!

One-Time
Monthly
Yearly

Make a one-time donation

Make a monthly donation

Make a yearly donation

Choose an amount

$5.00
$15.00
$100.00
$5.00
$15.00
$100.00
$5.00
$15.00
$100.00

Or enter a custom amount

$

Your contribution is appreciated.

Your contribution is appreciated.

Your contribution is appreciated.

DonateDonate monthlyDonate yearly