Kodeclik Blog
The Cartesian Product and its Generalizations
The Cartesian product is a fundamental mathematical operation that creates a set of all possible ordered pairs from two or more sets.
When two sets A and B are involved, their Cartesian product A × B contains all possible pairs where the first element comes from A and the second from B.
For instance, consider that the set A is {123, 456, 789} and the set B is {‘Main Street’, ‘Corner Avenue’, and ‘Turner Road’}. Then the Cartesian product A X B is given by:
(123, 'Main Street')
(123, 'Corner Avenue')
(123, 'Turner Road')
(456, 'Main Street')
(456, 'Corner Avenue')
(456, 'Turner Road')
(789, 'Main Street')
(789, 'Corner Avenue')
(789, 'Turner Road')In other words, this represents all possible ordered pairs where the first element comes from set A (house numbers) and the second element comes from set B (street names), effectively creating all possible address combinations from these components.
The Cartesian Product is not commutative
Looking at the same sets A and B, the cartesian product B × A (instead of A × B) gives us:
('Main Street', 123)
('Main Street', 456)
('Main Street', 789)
('Corner Avenue', 123)
('Corner Avenue', 456)
('Corner Avenue', 789)
('Turner Road', 123)
('Turner Road', 456)
('Turner Road', 789)Notice how this differs from A × B in that the street names now come first in each ordered pair, followed by the house numbers. This illustrates why Cartesian products are not commutative - the order of the sets matters in determining which elements appear first in the resulting ordered pairs.
Mathematical Definition of Cartesian Product
For two sets A and B, the Cartesian product is defined as:
Example 1: Deck of Playing Cards
A standard deck of playing cards is a perfect example of a Cartesian product between two sets: the set of suits {♠,♥,♦,♣} and the set of ranks {2,3,4,5,6,7,8,9,10,J,Q,K,A}. The Cartesian product of these sets creates all possible combinations of suit and rank, resulting in 52 unique cards (4 suits × 13 ranks = 52 cards).
Each card in the deck represents exactly one ordered pair from this Cartesian product. For example, the Jack of Hearts is the ordered pair (♥,J), while the Two of Spades is (♠,2). Every possible combination of a suit and a rank exists exactly once in the deck, making it a complete Cartesian product where no combinations are missing or repeated.
This mathematical structure explains why we can systematically count and organize cards - there are precisely four cards of each rank (one in each suit) and thirteen cards of each suit (one of each rank). The Cartesian product structure also explains why we can uniquely identify any card by specifying just two pieces of information: its suit and its rank.
Example 2: Cartesian Coordinate System
A two-dimensional coordinate system, also known as the Cartesian plane, is fundamentally a Cartesian product of two number lines (typically the real numbers ℝ × ℝ). Each point in the plane is uniquely defined by an ordered pair (x,y) where x comes from the horizontal number line (x-axis) and y comes from the vertical number line (y-axis). This creates the set of all possible ordered pairs of real numbers, written mathematically as ℝ².
The power of this representation lies in how it maps every possible point in the plane to exactly one ordered pair, and every ordered pair to exactly one point. For instance, the point (3,4) represents the unique location found by moving 3 units along the x-axis and 4 units along the y-axis. The order matters - the point (4,3) would be in a different location, demonstrating the non-commutative nature of Cartesian products.
This structure allows us to translate geometric concepts into algebraic ones and vice versa. When we graph a line, parabola, or any other function, we're actually visualizing a subset of this Cartesian product - specifically, the set of all ordered pairs (x,y) that satisfy the function's equation. The Cartesian product structure of the coordinate plane forms the foundation for analytic geometry and serves as the bridge between algebra and geometry.
Let us now look at methods to explore Cartesian products in Python. There are at least three ways to do so!
Implementing Cartesian Products in Python using list comprehensions
Here's how to implement a Cartesian product to create a deck of cards using list comprehensions in Python:
# Define the sets for suits and ranks
suits = ['♠', '♥', '♦', '♣']
ranks = ['2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K', 'A']
# Create the deck using list comprehension
deck_of_cards = [(rank, suit) for suit in suits for rank in ranks]
print(deck_of_cards)
print(len(deck_of_cards))The list comprehension [(rank, suit) for suit in suits for rank in ranks] creates ordered pairs by i) iterating through each suit in the outer loop; ii) for each suit, iterating through all ranks in the inner loop, and iii) creating tuples of (rank, suit) for each combination.
This generates all 52 cards in the deck (4 suits × 13 ranks = 52 cards). Each card is represented as a tuple containing its rank and suit. The resulting deck_of_cards list contains all possible combinations, starting with all ranks of Spades, then Hearts, Diamonds, and finally Clubs.
The output will be:
[('2', '♠'), ('3', '♠'), ('4', '♠'), ('5', '♠'), ('6', '♠'), ('7', '♠'), ('8', '♠'), ('9', '♠'), ('10', '♠'), ('J', '♠'), ('Q', '♠'), ('K', '♠'), ('A', '♠'), ('2', '♥'), ('3', '♥'), ('4', '♥'), ('5', '♥'), ('6', '♥'), ('7', '♥'), ('8', '♥'), ('9', '♥'), ('10', '♥'), ('J', '♥'), ('Q', '♥'), ('K', '♥'), ('A', '♥'), ('2', '♦'), ('3', '♦'), ('4', '♦'), ('5', '♦'), ('6', '♦'), ('7', '♦'), ('8', '♦'), ('9', '♦'), ('10', '♦'), ('J', '♦'), ('Q', '♦'), ('K', '♦'), ('A', '♦'), ('2', '♣'), ('3', '♣'), ('4', '♣'), ('5', '♣'), ('6', '♣'), ('7', '♣'), ('8', '♣'), ('9', '♣'), ('10', '♣'), ('J', '♣'), ('Q', '♣'), ('K', '♣'), ('A', '♣')]
52Note that we have 52 elements as expected.
Implementing Cartesian Products in Python using itertools
Here's how to create a deck of cards using itertools.product:
from itertools import product
# Define the sets for suits and ranks
suits = ['♠', '♥', '♦', '♣']
ranks = ['2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K', 'A']
# Create the deck using itertools.product
deck_of_cards = list(product(ranks, suits))
print(deck_of_cards)
print(len(deck_of_cards))The itertools.product() function provides a more efficient and cleaner way to generate Cartesian products compared to list comprehensions. It creates an iterator that generates tuples containing all possible combinations of input iterables. In this case, it pairs each rank with each suit, creating all 52 possible combinations that represent a complete deck of cards.
The function works by systematically generating combinations in a memory-efficient manner, and when we convert the result to a list, we get all 52 cards organized by rank first, then by suit. Notice how in the output, all four suits are generated for each rank before moving to the next rank - first all suits for '2', then all suits for '3', and so on until the Aces. This systematic organization makes it easy to verify that all combinations are present and that the deck is complete.
The output will be as before:
[('2', '♠'), ('2', '♥'), ('2', '♦'), ('2', '♣'), ('3', '♠'), ('3', '♥'), ('3', '♦'), ('3', '♣'), ('4', '♠'), ('4', '♥'), ('4', '♦'), ('4', '♣'), ('5', '♠'), ('5', '♥'), ('5', '♦'), ('5', '♣'), ('6', '♠'), ('6', '♥'), ('6', '♦'), ('6', '♣'), ('7', '♠'), ('7', '♥'), ('7', '♦'), ('7', '♣'), ('8', '♠'), ('8', '♥'), ('8', '♦'), ('8', '♣'), ('9', '♠'), ('9', '♥'), ('9', '♦'), ('9', '♣'), ('10', '♠'), ('10', '♥'), ('10', '♦'), ('10', '♣'), ('J', '♠'), ('J', '♥'), ('J', '♦'), ('J', '♣'), ('Q', '♠'), ('Q', '♥'), ('Q', '♦'), ('Q', '♣'), ('K', '♠'), ('K', '♥'), ('K', '♦'), ('K', '♣'), ('A', '♠'), ('A', '♥'), ('A', '♦'), ('A', '♣')]
52Implementing Cartesian products in Python using recursion
Here's an implementation of Cartesian products using recursion to create a deck of cards:
def cartesian_product(sets):
if not sets:
yield ()
else:
for item in sets[0]:
for prod in cartesian_product(sets[1:]):
yield (item,) + prod
# Define the sets for suits and ranks
suits = ['♠', '♥', '♦', '♣']
ranks = ['2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K', 'A']
# Create the deck using recursion
deck_of_cards = list(cartesian_product([ranks, suits]))
print(deck_of_cards)
print(len(deck_of_cards))The recursive implementation works by breaking down the problem into smaller subproblems. The base case occurs when the input list is empty, yielding an empty tuple. For each recursive call, the function takes the first set from the input list and combines each of its elements with all possible combinations of the remaining sets. The yield statement allows for memory-efficient generation of values, creating an iterator that produces one card combination at a time rather than storing all combinations in memory at once.
When we convert the iterator to a list, we get all 52 cards organized systematically, with each rank paired with all suits before moving to the next rank. This recursive approach, while more complex than using itertools.product(), provides a deeper understanding of how Cartesian products are constructed.
The output will be as usual:
[('2', '♠'), ('2', '♥'), ('2', '♦'), ('2', '♣'), ('3', '♠'), ('3', '♥'), ('3', '♦'), ('3', '♣'), ('4', '♠'), ('4', '♥'), ('4', '♦'), ('4', '♣'), ('5', '♠'), ('5', '♥'), ('5', '♦'), ('5', '♣'), ('6', '♠'), ('6', '♥'), ('6', '♦'), ('6', '♣'), ('7', '♠'), ('7', '♥'), ('7', '♦'), ('7', '♣'), ('8', '♠'), ('8', '♥'), ('8', '♦'), ('8', '♣'), ('9', '♠'), ('9', '♥'), ('9', '♦'), ('9', '♣'), ('10', '♠'), ('10', '♥'), ('10', '♦'), ('10', '♣'), ('J', '♠'), ('J', '♥'), ('J', '♦'), ('J', '♣'), ('Q', '♠'), ('Q', '♥'), ('Q', '♦'), ('Q', '♣'), ('K', '♠'), ('K', '♥'), ('K', '♦'), ('K', '♣'), ('A', '♠'), ('A', '♥'), ('A', '♦'), ('A', '♣')]
52Cartesian product of a set with itself
You can take a cartesian product of a set with itself. For instance, suppose you are allowed to pick two toys from a toy store. The itertools.product() function has a repeat parameter that comes in handy for this purpose:
# Define the set of available toys
toys = ['car', 'doll', 'ball', 'robot']
# Get all possible combinations of picking two toys
two_toy_combinations = list(product(toys, repeat=2))
# Print each combination on a new line
for combo in two_toy_combinations:
print(combo)
print(len(two_toy_combinations))This will output all possible combinations, including when the same toy is picked twice:
('car', 'car')
('car', 'doll')
('car', 'ball')
('car', 'robot')
('doll', 'car')
('doll', 'doll')
('doll', 'ball')
('doll', 'robot')
('ball', 'car')
('ball', 'doll')
('ball', 'ball')
('ball', 'robot')
('robot', 'car')
('robot', 'doll')
('robot', 'ball')
('robot', 'robot')
16When taking a Cartesian product of a set with itself, we get n² combinations where n is the size of the original set. In this case, with 4 toys, we get 16 possible combinations (4² = 16). This includes cases where the same toy is selected twice (like ('car', 'car')) because in this scenario, order matters and repetition is allowed. If we wanted combinations without repetition or where order doesn't matter, we would need to use different tools like combinations() or permutations() from the itertools module.
Note that if you do such checks for repetitions or orders, what you are computing is not the cartesian product anymore: a cartesian product blindly multiples every element of a set with every element of another set.
Properties of the Cartesian product
Recall that the cartesian product is not commutative:
It is also not associative:
But it does satisfy this property:
You can see why that is true by the following diagram:
Generalized Cartesian product
The generalized Cartesian product extends the concept of Cartesian product to any number of sets, not just two.
As mentioned earlier, in Python, the itertools.product() function efficiently handles generalized Cartesian products:
from itertools import product
# Example with three sets
set1 = [1, 2]
set2 = ['A', 'B']
set3 = ['X', 'Y']
result = list(product(set1, set2, set3))
print(result)
print(len(result))The output is:
[(1, 'A', 'X'), (1, 'A', 'Y'), (1, 'B', 'X'), (1, 'B', 'Y'), (2, 'A', 'X'), (2, 'A', 'Y'), (2, 'B', 'X'), (2, 'B', 'Y')]
8As mentioned earlier, for cases where you want to take the Cartesian product of the same set multiple times, you can use the repeat parameter. Earlier we used a repeat parameter value of 2, but you could use 3 or anything greater.
Finding all three digit binary combinations using generalized Cartesian product
Here is a simple program that generates all three digit binary combinations:
from itertools import product
# Generate all 3-digit binary numbers
binary_digits = [0, 1]
binary_numbers = list(product(binary_digits, repeat=3))
print(binary_numbers)
print(len(binary_numbers))The output will be:
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]
8As expected there are 8 combinations, i.e., the 8 corners of a (three dimensional) cube.
In summary, there is nothing magical about the generalized Cartesian product. It is simply an extension of the basic concept to handle multiple sets at once. Instead of just creating ordered pairs from two sets, it creates n-tuples from n sets, following the same fundamental principle: take one element from each set to form an ordered combination.
For n sets X₁, X₂, ..., Xₙ, each element in the resulting product is an n-tuple (x₁, x₂, ..., xₙ) where each xᵢ comes from its corresponding set Xᵢ1. The result contains all possible combinations of elements, just as with the two-set version, but with more components in each tuple.
The only real difference is that instead of working with pairs, we're working with longer sequences of elements, maintaining the same systematic way of combining elements from each input set.
In summary, generalized Cartesian product extends beyond pairs to create ordered n-tuples from multiple sets, finding applications in numerous areas of computer science such as database operations, coordinate systems, and digital imaging. Mastering this simple mathematical concept can help you solve complex real-world problems through systematic combination of elements.
Enjoy this blogpost? Want to learn Python with us? Sign up for 1:1 or small group classes.
