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