This article explains a simple and effective way of computing the factorial in a single line of code.
Problem Formulation & Motivation
Consider the following problem:
- There are 20 football teams in England’s premier league.
- Each team can possibly reach any of the 20 ranks at the end of the season.
- Problem: How many possible rankings exist in the premier league, given 20 fixed teams?
Figure: Example of three possible rankings of the football teams in England’s premier league.
The figure shows three different rankings of the teams. In computer science terminology, you would denote each ranking as a “permutation”.
Definition: A permutation is defined as a specific order of set elements (here: football teams).
Using this terminology, our goal is to find the number of permutations of a given set (the set of all football teams).
Applications: The number of those permutations has important implications in practice such as betting applications, match prediction, and game analysis. For example, when assuming 100 different rankings with equal probability, the probability of a specific ranking is 1/100 = 1%. This can be used as a base probability (a priori probability) for game prediction algorithms. Under these assumptions, a randomly guessed ranking has a 1% probability of being the correct outcome after one season.
How to Calculate the Number of Permutations of a Given Set?
The factorial function n! calculates the number of permutations of a given set of n elements. The factorial is defined as follows:
For example:
Why does the factorial count the number of permutations of a given set of elements? The answer is very straightforward. Say, you have a set of ten elements
S = {s0, s1, ..., s9}
and ten buckets
B = {b0, b1, ..., b9}.
In the football example, there are twenty teams (the elements) and twenty table ranks (the buckets). To get a permutation of S
- First, you take a random element from the set
S. In how many buckets can you place this element? There are ten empty buckets so you have ten options. - Second, you take the next element from the set. In how many buckets can you place this element? There are nine empty buckets so you have nine options.
- … keep doing this until …
- Finally, you take the last element from the set. In how many buckets can you place this element? There is only one empty bucket so you have one option.
In total, you have 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 10! different options. Each option of placing elements into the buckets represents one permutation of the set elements. The number of permutations of a set with n elements is n!.
Python Recursive Factorial
You now know everything you need to know to solve the following problem:
Task: Write a Python one-liner solution that computes the number of permutations n! of a set with n elements.
## One-Liner Factorial Function: factorial = lambda n: n * factorial(n-1) if n > 1 else 1 ## Factorial of 5 print(factorial(5))
Listing: One-liner solution defining the factorial function recursively.
🧩 Exercise: What’s the output of this code?
Python Factorial Explanation
The factorial function can be defined recursively as
with the recursion base cases defined as
The intuition behind these base cases is the following:
- A set with one element has one permutation.
- A set with zero elements has one permutation because there is one way of assigning zero elements to zero buckets.
Algorithm Description:
The code uses this recursive definition.
- It creates a lambda function with one argument
n. - It assigns the lambda function to the name
factorial. - It calls the named function
factorial(n-1)to calculate the result of the function callfactorial(n). By using the solution to the easier problemfactorial(n-1), you can construct the solution of the harder problemfactorial(n)by multiplying it with the input argumentn. - As soon as we reach the recursion base case
n <= 1, we simply return the hard-coded base case solutionfactorial(1) = factorial(0) = 1.
Alternative Ways to Calculate the Factorial [Video]
Conclusion
This algorithm shows how one can often find a simple, concise, and efficient way of solving problems by thoroughly understanding the problem first.
Choosing the simplest solution idea is one of the most important things you can do when creating your own algorithms.
A common problem of beginners is their cluttered and unnecessary complicated code. The recursive definition of the factorial is more readable than an iterative definition (without recursion).
🧩 As a bonus exercise, try to rewrite this one-liner without using a recursive definition and without external libraries – it’s not trivial and certainly not that concise!
This one-liner was taken from my NoStarch book “Python One-Liners”:
Python One-Liners Book: Master the Single Line First!
Python programmers will improve their computer science skills with these useful one-liners.
Python One-Liners will teach you how to read and write “one-liners”: concise statements of useful functionality packed into a single line of code. You’ll learn how to systematically unpack and understand any line of Python code, and write eloquent, powerfully compressed Python like an expert.
The book’s five chapters cover (1) tips and tricks, (2) regular expressions, (3) machine learning, (4) core data science topics, and (5) useful algorithms.
Detailed explanations of one-liners introduce key computer science concepts and boost your coding and analytical skills. You’ll learn about advanced Python features such as list comprehension, slicing, lambda functions, regular expressions, map and reduce functions, and slice assignments.
You’ll also learn how to:
- Leverage data structures to solve real-world problems, like using Boolean indexing to find cities with above-average pollution
- Use NumPy basics such as array, shape, axis, type, broadcasting, advanced indexing, slicing, sorting, searching, aggregating, and statistics
- Calculate basic statistics of multidimensional data arrays and the K-Means algorithms for unsupervised learning
- Create more advanced regular expressions using grouping and named groups, negative lookaheads, escaped characters, whitespaces, character sets (and negative characters sets), and greedy/nongreedy operators
- Understand a wide range of computer science topics, including anagrams, palindromes, supersets, permutations, factorials, prime numbers, Fibonacci numbers, obfuscation, searching, and algorithmic sorting
By the end of the book, you’ll know how to write Python at its most refined, and create concise, beautiful pieces of “Python art” in merely a single line.