Understanding Cartesian Products

Recreating the Cartesian Product in Python

7 min readMay 5, 2019

This blog is about the results of our studies exploring
Computer Algorithms at
Make School
.

The Golden Ratio can pop up in the most unexpected places.

In my attempt to understand 3D geometry as it relates to the web, I stumbled upon an interesting subject in mathematics: Cartesian products. These products are sort of a multiplicative operation between zero or more sets.

Just What is a Cartesian product?

Wikipedia’s Definition

In set theory (and, usually, in other parts of mathematics), a Cartesian product is a mathematical operation that returns a set (or product set or simply product) from multiple sets. That is, for sets A and B, the Cartesian product
A × B is the set of all ordered pairs (a,b) where a ∈ A and b ∈ B.

Don’t worry about the squiggly looking E, that symbol just means “in”. For example, in an object A, it could have a parameter “a”.

In so many words… If you have a bunch of items in an set A, and a bunch of items in set B, you pair each item in set A with every item in set B. This leaves you with a number of pairs equal to the number of items in A times the number of items in B.

For example… If set A has the items A = [a,b,c], and set B has the items
B = [1,2,3], the Cartesian product of both would be:
A × B = [a,1],[a,2],[a,3],[b,1],[b,2],[b,3],[c,1],[c,2],[c,3]].

Notice how there are 3 items in A, 3 items in B, and 9 items in A × B.
3 times 3 is 9. This is not a coincidence; if our set A had instead 5 items,
A × B would have 5 times 3 items in the product, or 15 items.

It is easier to envision what a Cartesian product does with a simple table. If you understand how a table in a spreadsheet works, you can understand how a Cartesian product works. Moreover, you can visually break down this seemingly complex definition into a basic idea.

Taking It to the Next Level

Great — now that we have a basic understanding of the Cartesian product, we can expand on our definition. The Cartesian product will work for a set of any valid size (not something ridiculous like a size of –5).

Take for example the empty set, ∅. The empty set is the only set with exactly zero items in it. If you take the Cartesian product of the empty set and literally any other set, your result will always be the empty set itself. This checks out with our earlier analogy; 0 times anything is always 0.

Why do Cartesian Products Matter?

My personal interest in Cartesian products stems from mapping symmetrical 3D shapes to javascript libraries like THREE.js, which can render 3D scenes on the web. The module requires a list of vertices to compute shape.

An icosahedron has 20 sides and 12 vertices.

While certain shapes—like a cube or icosahedron—have boilerplate functions that I can call to generate a scene, other more complicated symmetrical shapes that I am interested in don’t have that luxury. Even so, it is likely best to start by understanding the simplest shapes.

To understand this, a few definitions need to be understood…after reading these four definitions below, try looking at the illustrations to fully comprehend them.

A polyhedron is another name for a 3D shape.
A vertex is a point in space at which three or more edges come to meet.
An edge is a straight line at which two flat faces meet & pivot.
Cartesian coordinates are different than Cartesian products. These coordinates are mathematical shorthand notations of tracking the coordinates of a shape’s vertices

This last definition is a little confusing, so we are going to step through how we convert a set of Cartesian coordinates into a list of vertices, which can be further expressed as theX, Y, Z coordinates of a 3D shape in space. Usually a vertices’ coordinates is denoted in a tuple, like (X,Y,Z).

a single vertex is synonymous with a point in space.

Cartesian Coordinates Examined

Bare with me, this gets a bit dense. I’ll try to explain it as best I can by taking it apart into chronological, numbered steps. Let’s do this with the regular icosahedron, a 20 sided figure with 12 vertices.

Cartesian coordinates are sort of magical in how they are found. They are complicated, and still go a bit over my head. For now, we’ll just use Wikipedia and other sources to find a shape’s coordinates.
I have found that an icosahedron has the coordinates [0, ±1, ±φ], where φ is the golden ratio; 1.61803398875.
Take the circular permutations of [0, ±1, ±φ], where we get
[0, ±1, ±φ]
[±φ, 0, ±1]
[±1, ±φ, 0]
Before we do anything else, we have to remove the ± symbol and replace it with a list of two values — one negative and one positive. As for the single value items, it would be best to keep them alone in a list as well for consistency. We are left with:
[[0], [1,-1], [φ,-φ]]
[[φ,-φ], [0], [1,-1]]
[[1,-1], [φ,-φ], [0]]
We take the Cartesian product of each circular permutation to get:
[[0, 1, φ],[0, -1, φ],[0, 1, -φ],[0, -1, -φ]]
[[φ, 0, 1],[φ, 0, -1],[-φ, 0, 1],[-φ, 0, -1]]
[[1, φ, 0],[-1, φ, 0],[1, -φ, 0],[-1, -φ, 0]]
The wonderful thing is, we just got our list of vertices here!
The only thing we must do now is combine these three lists of lists into a single list of lists to get our result…

vertices = [
    [0, 1, φ],[0, -1, φ],[0, 1, -φ],[0, -1, -φ],
    [φ, 0, 1],[φ, 0, -1],[-φ, 0, 1],[-φ, 0, -1],
    [1, φ, 0],[-1, φ, 0],[1, -φ, 0],[-1, -φ, 0]
]# each item in the list stands for a single vertex:
# [X, Y, Z]
vertices = [
    [0, 1, φ],
    [0, -1, φ],
    [0, 1, -φ],
    [0, -1, -φ],
    [φ, 0, 1],
    [φ, 0, -1],
    [-φ, 0, 1],
    [-φ, 0, -1],
    [1, φ, 0],
    [-1, φ, 0],
    [1, -φ, 0],
    [-1, -φ, 0]
]

Whew! That was a lot, let’s reel it in a bit…

In Pursuit of Conceptual Clarity

That’s all well and good, but we need to convert this morsel of information into code! Well, to be frank, Cartesian products have already been immensely examined and developed within so many pieces of code. After all, the very first thing I did (before even writing this article) was checking some
top results on Google and on Stack Overflow.

However, these implementations are very difficult for me to follow or understand on a conceptual level…which is why I set out to create my own Cartesian product function from scratch in Python.

def cartesian_product(array):
    '''
    Vocabulary:
    - a collection is an array of arrays
    - a group is an array within a collection
    - old is the user's input
    - new is the transformed output
    - tmp is data not added to new for technical reasons
    
    Variable Names:
    - old_collection is the user's input
    - old_group is a nested array in old_collection
    - new_collection is the expected output
    - new_group is a nested array in new_collection
    - tmp_collection is data not yet added to new_collection
    - tmp_group is data not yet added to tmp_collection
    '''
    
    # new_collection starts as an empty array
    # old_collection equals the input array parameter
    new_collection = [[]]
    old_collection = array
    
    # start by iterating over the groups in old_collection
    for old_group in old_collection:
    
        # new_collection can't be modified while in a loop
        # tmp_collection will store a subset of new data
        # it will be added to new_collection after the next loop
        tmp_collection = []
        
        # iterate over new_collections
        # it will start with just an array with one empty array
        # every time we go through another old_group it fills up
        for new_group in new_collection:
            
            # finally, look through the data in old_group
            # this data is important;
            #    its what we need to transfer to the new structure
            for data in old_group:
                
                # new_group contains a set of important data
                # there is still yet more data to append to it...
                # ...set tmp_group to new_group and add data to it
                tmp_group = new_group.copy()
                tmp_group.append(data)
                
                # now transfer the data to our tmp_collection
                # it will be added to the new_collection to output
                tmp_collection.append(tmp_group)
            
            # exit old_group loop
            pass
        
        # exit new_collection loop
        pass
        
        # an item can't be changed while being looped over;
        #    we are no longer looping over new_collection
        new_collection = tmp_collection
    
    # exit old_collection loop
    pass
    
    # after the loops are over, we can return the result
    return new_collection
# if the program is run directly...
if __name__ == '__main__':
    X={'X'}
    Y={'Y'}
    Z={'Z'}    simple_array = [[1,2,3],['a','b','c'],[X,Y,Z]]
    result = cartesian_product(simple_array)    for group in result:
        print(group)

To better grasp an algorithm, the best thing to do is to recreate it yourself from scratch. That is what I have done here. The first step in doing so is writing up pseudocode.

Next, a developer can step through their pseudocode with an input in their mind, and write down expected results as they go. While the developer does this, they can update and fix unexpected results.

Once this process is done, the developer can transfer their pseudocode into code! Keeping the pseudocode handy makes the comments almost write themselves; it's much harder to get lost in the code.

After some time behind the keyboard, my implementation is completed. Check out the results of my studies in my github repository!

noltron000/cartesian-product

a semantic python file that outputs a cartesian product - noltron000/cartesian-product

github.co

Conclusion

I hope you have learned something from this medium article! Clap, share, and connect with me on Linkedin if you feel the urge to do so! 👏