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

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:

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:

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.

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:

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:

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) —