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:
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.
Looking at the same sets A and B, the cartesian product B × A (instead of A × B) gives us:
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.
For two sets A and B, the Cartesian product is defined as:
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.
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!
Here's how to implement a Cartesian product to create a deck of cards using list comprehensions in Python:
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:
Note that we have 52 elements as expected.
Here's how to create a deck of cards using itertools.product:
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:
Here's an implementation of Cartesian products using recursion to create a 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:
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:
This will output all possible combinations, including when the same toy is picked twice:
When 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.
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:
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:
The output is:
As 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.
Here is a simple program that generates all three digit binary combinations:
The output will be:
As 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.
