Teaching Kids Programming: Videos on Data Structures and Algorithms
In Python, we have itertools.product that calculates the Cartesian Product of a few list or tuple. For example:
1 2 3 4 5 | from itertools import product a=(1,2) b=('a','b') print(list(product(a, b))) # [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')] |
from itertools import product
a=(1,2)
b=('a','b')
print(list(product(a, b))) # [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]We can easily re-invent this by the following Python function which takes two list or tuples and returns the cartesian product iterator:
1 2 3 4 | def cartesianProduct(a, b): for i in a: for j in b: yield (i, j) |
def cartesianProduct(a, b):
for i in a:
for j in b:
yield (i, j)However, the itertools.product has variant length of arguments, meaning that we can compute the Cartesian product of more than 2 lists or tuples.
1 2 | print(list(itertools.product((1,2),['a','b'],['c','d']))) # [(1, 'a', 'c'), (1, 'a', 'd'), (1, 'b', 'c'), (1, 'b', 'd'), (2, 'a', 'c'), (2, 'a', 'd'), (2, 'b', 'c'), (2, 'b', 'd')] |
print(list(itertools.product((1,2),['a','b'],['c','d']))) # [(1, 'a', 'c'), (1, 'a', 'd'), (1, 'b', 'c'), (1, 'b', 'd'), (2, 'a', 'c'), (2, 'a', 'd'), (2, 'b', 'c'), (2, 'b', 'd')]
We can keep adding this to make it 3 parameters – but this is not flexible:
1 2 3 4 5 | def cartesianProduct(a, b, c): for i in a: for j in b: for k in c: yield (i, j, k) |
def cartesianProduct(a, b, c):
for i in a:
for j in b:
for k in c:
yield (i, j, k)We can use the Depth First Search Algorithm:
1 2 3 4 5 6 7 8 | def cartesianProduct(*a): def dfs(left, cur): if left == len(a): yield tuple(cur) return for i in a[left]: yield from dfs(left + 1, cur + [i]) yield from dfs(0, []) |
def cartesianProduct(*a): def dfs(left, cur): if left == len(a): yield tuple(cur) return for i in a[left]: yield from dfs(left + 1, cur + [i]) yield from dfs(0, [])
See also: Teaching Kids Programming – Introduction to Cartesian Product (Math)
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
379 wordsloading...
Last Post: Java's Function to Merge Byte Arrays into One
Next Post: Java Function to Delete a File/Folder Recursively
