Cartesian Product

by Justin Skycak on January 06, 2021

Implementing the Cartesian product provides good practice working with arrays.

This post is a chapter in the book Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. Suggested citation: Skycak, J. (2021). Cartesian Product. Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents. https://justinmath.com/cartesian-product/

Implementing the Cartesian product provides good practice working with arrays. Recall that the Cartesian product constructs all the points whose elements occupy the given ranges. To illustrate:


>>> calc_cartesian_product([
    ['a'],
    [1, 2, 3],
    ['Y', 'Z']
  ])

[
  ['a', 1, 'Y'],
  ['a', 1, 'Z'],
  ['a', 2, 'Y'],
  ['a', 2, 'Z'],
  ['a', 3, 'Y'],
  ['a', 3, 'Z']
]

Implementation

The Cartesian product can be implemented elegantly via the following procedure:

Create an array that will contain all the points in the cartesian product. Initialize it with a single empty point, i.e. points = [[]].
Create a copy of points, and for each copied point, loop through the first range and create an extended point by appending a range item onto the copied point, create a handful of new points. Collect all these extended points and save them to points.
Repeat step 2 for each range.

Below is a worked example.


ranges = [
  ['a'],
  [1, 2, 3],
  ['Y', 'Z']
]

points: [
  []
]

looping through range ['a']:
 - item 'a' --> extended point ['a']

points: [
  ['a']
]

looping through range [1, 2, 3]:
 - item 1 --> extended point ['a', 1]
 - item 2 --> extended point ['a', 2]
 - item 3 --> extended point ['a', 3]

points: [
  ['a', 1],
  ['a', 2],
  ['a', 3]
]

looping through range ['Y', 'Z']:
 - item 'Y' --> extended points ['a', 1, 'Y'], ['a', 2, 'Y'], ['a', 3, 'Y']
 - item 'Z' --> extended points ['a', 1, 'Z'], ['a', 2, 'Z'], ['a', 3, 'Z']

points: [
  ['a', 1, 'Y'], ['a', 2, 'Y'], ['a', 3, 'Y'],
  ['a', 1, 'Z'], ['a', 2, 'Z'], ['a', 3, 'Z']
]

Copying an Array

When copying an array, it’s essential to create an entirely new array, not just reference the original array. Observe that if we just reference the old array, then any new changes to the original array get propagated to the new array.


>>> arr = [1, 2]
>>> arr_copy = arr   # just references the original array

>>> arr.append(3)
>>> print(arr_copy)
[1, 2, 3]   # this is not [1, 2]

To avoid this issue, you need to create an entirely new array:


>>> arr = [1, 2]
>>> arr_copy = []

# create an entirely new array
>>> for item in arr:
      arr_copy.append(item)

>>> arr.append(3)
>>> print(arr_copy)
[1, 2]

Note that if our array contains items that are themselves arrays, then it’s necessary to copy those items as well.

Exercise

Implement calc_cartesian_product, verify that it reproduces the example above, and write a handful of other tests.