Teaching Kids Programming – Introduction to Cartesian Product (Math)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Cartesian Product is a math operation that is applied on two or more sets. It is:

where A and B are sets.

For example:

A = {1, 2}, B = {3, 4} and the Cartesian Product of A and B noted as A x B is {{1, 3}, {1, 4}, {2, 3}, {2, 4}}.

The Cardinality (the number of the elements in the set) for the Cartesian Product can be computed as:

As for each element in set A, we pair it with each element in set B.

Cartesian Product can be applied to multiple sets:

And the Cardinality is the product of the sizes of all sets:

Clearly, the commutative rule does not stand:

except when B is empty e.g.

Cartesian Product in Python

We can import the product function from itertools package:

1

from itertools import product

from itertools import product

The product method returns an iterator – and we can convert it to list:

1
2
3
4

A = (1, 2)
B = (3, 4)
C = list(product(A, B))
# C = [(1, 3), (1, 4), (2, 3), (2, 4)]

A = (1, 2)
B = (3, 4)
C = list(product(A, B))
# C = [(1, 3), (1, 4), (2, 3), (2, 4)]

The product function can be specified the repeat parameter:

1
2

for k, i, j in product(range(n), repeat=3):
    pass

for k, i, j in product(range(n), repeat=3):
    pass

This is the same as the following O(N^3) loops:

1
2
3
4

for k in range(n):
    for i in range(n):
        for j in range(n):
            pass

for k in range(n):
    for i in range(n):
        for j in range(n):
            pass

See also: Teaching Kids Programming – Implementation of Cartesian Product in Python via Depth First Search Algorithm

–EOF (The Ultimate Computing & Technology Blog) —