Teaching Kids Programming – Introduction to Cartesian Product (Math) | ninjasquad

**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

–EOF (The Ultimate Computing & Technology Blog) —

**GD Star Rating***loading…*

677 words

**Last Post**: Teaching Kids Programming – Recursive Depth First Search Algorithm to Evaluate the Boolean Binary Tree **Next Post**: Teaching Kids Programming – Floyd Warshall Multi-source/All Pairs Shortest Path Algorithm (Sum of Costs in a Directed Unweighted Graph)

Source: Internet