This past week, I contemplated a number of math modeling applications for
publication here. Ultimately, I decided to instead write about my *approach* to
implementing math models, specifically in cases where Python’s `itertools`

package can work its magic. The `itertools`

package is part of the
Python standard library
which is itself enormous. Tack on all the high-quality 3rd-party
math packages (e.g. `numpy`

, `pyomo`

, etc.), and finding the *best* tool
for the job often requires more effort than simply using the tools you already
know. This post is a little bit about prefacing future math modeling posts,
but is mostly geared toward expanding your arsenal at a low investigative
cost.

*Nerd Alert: If I recall correctly, itertools behaved differently in older
versions of Python, mainly in that the functions would return list objects. In
contemporary versions, the package instead uses generators. For small
applications, this difference is inconsequential; however, substantial
memory advantages are realized at scale. In some toy code examples, you may
find that itertools functions are wrapped in a list, usually for the sake
of illustrating a result. Be aware that doing so negates the advantage provided
by generators and is generally bad practice.*

Of all the functions provided by `itertools`

, I find myself going back to
`product`

time and time again. It has a clear and straightforward name which
makes it easy to remember and it is highly employable. What does it do?
Formally, it computes the
Cartesian product
of two or more input sets. In layman’s terms, this basically means that given
a few sets of objects, we create all possible combinations that can be made by
picking one object from each set.

Consider this silly example. Suppose that a conflict arises between famous
fictional pirates and 21st century actors, and it is decided that it will be
settled in the only appropriate manner – a vintage video game duel.
Representing the pirates are Long John Silver and Captain Flint,
with Matt Damon and Mark Wahlberg representing the actors.
Yo ho ho and a bottle of rum, how do you like them apples!?
Only one member from each party will participate in the duel, and the duel will
involve a video game – one of Mario Kart 64, Twisted Metal, or NBA Jam.
(*BOOM SHAKA LAKA!*) How many different ways can the duel occur? What are they?

With each party having 2 members, and there being 3 possible competitions,
there are 2 * 2 * 3 = 12 possible duels. This is a small enough number that we
could determine the possibilities with pencil, paper, and a little effort.
But let’s see what `product`

can do.

```
from itertools import product
pirates = ['Long John Silver', 'Captain Flint']
actors = ['Matt Damon', 'Mark Wahlberg']
competitions = ['Mario Kart 64', 'Twisted Metal', 'NBA Jam']
duels = product(pirates, actors, competitions)
for counter, duel in enumerate(duels):
print(counter, duel)
```

We apply `product`

to three sets – pirates, actors, and competitions. Here
are the results.

```
0 ('Long John Silver', 'Matt Damon', 'Mario Kart 64')
1 ('Long John Silver', 'Matt Damon', 'Twisted Metal')
2 ('Long John Silver', 'Matt Damon', 'NBA Jam')
3 ('Long John Silver', 'Mark Wahlberg', 'Mario Kart 64')
4 ('Long John Silver', 'Mark Wahlberg', 'Twisted Metal')
5 ('Long John Silver', 'Mark Wahlberg', 'NBA Jam')
6 ('Captain Flint', 'Matt Damon', 'Mario Kart 64')
7 ('Captain Flint', 'Matt Damon', 'Twisted Metal')
8 ('Captain Flint', 'Matt Damon', 'NBA Jam')
9 ('Captain Flint', 'Mark Wahlberg', 'Mario Kart 64')
10 ('Captain Flint', 'Mark Wahlberg', 'Twisted Metal')
11 ('Captain Flint', 'Mark Wahlberg', 'NBA Jam')
```

As expected, there are 12 possible duels (counting starts at 0) generated by the product. Each combination is comprised of exactly one pirate, one actor, and one competition.

Now suppose that instead of playing just one of the video games, the duel is
changed to a best-of-three competition where each game is played once and in
some predetermined order. Great, now we have to deal with permutations…
But worry not, `itertools`

has got us covered! Building from the previous
example,

```
from itertools import permutations
for duel in product(pirates, actors, permutations(competitions)):
print(duel)
```

And we see now that 24 such duels are possible.

```
('Long John Silver', 'Matt Damon', ('Mario Kart 64', 'Twisted Metal', 'NBA Jam'))
('Long John Silver', 'Matt Damon', ('Mario Kart 64', 'NBA Jam', 'Twisted Metal'))
('Long John Silver', 'Matt Damon', ('Twisted Metal', 'Mario Kart 64', 'NBA Jam'))
('Long John Silver', 'Matt Damon', ('Twisted Metal', 'NBA Jam', 'Mario Kart 64'))
('Long John Silver', 'Matt Damon', ('NBA Jam', 'Mario Kart 64', 'Twisted Metal'))
('Long John Silver', 'Matt Damon', ('NBA Jam', 'Twisted Metal', 'Mario Kart 64'))
('Long John Silver', 'Mark Wahlberg', ('Mario Kart 64', 'Twisted Metal', 'NBA Jam'))
('Long John Silver', 'Mark Wahlberg', ('Mario Kart 64', 'NBA Jam', 'Twisted Metal'))
('Long John Silver', 'Mark Wahlberg', ('Twisted Metal', 'Mario Kart 64', 'NBA Jam'))
('Long John Silver', 'Mark Wahlberg', ('Twisted Metal', 'NBA Jam', 'Mario Kart 64'))
('Long John Silver', 'Mark Wahlberg', ('NBA Jam', 'Mario Kart 64', 'Twisted Metal'))
('Long John Silver', 'Mark Wahlberg', ('NBA Jam', 'Twisted Metal', 'Mario Kart 64'))
('Captain Flint', 'Matt Damon', ('Mario Kart 64', 'Twisted Metal', 'NBA Jam'))
('Captain Flint', 'Matt Damon', ('Mario Kart 64', 'NBA Jam', 'Twisted Metal'))
('Captain Flint', 'Matt Damon', ('Twisted Metal', 'Mario Kart 64', 'NBA Jam'))
('Captain Flint', 'Matt Damon', ('Twisted Metal', 'NBA Jam', 'Mario Kart 64'))
('Captain Flint', 'Matt Damon', ('NBA Jam', 'Mario Kart 64', 'Twisted Metal'))
('Captain Flint', 'Matt Damon', ('NBA Jam', 'Twisted Metal', 'Mario Kart 64'))
('Captain Flint', 'Mark Wahlberg', ('Mario Kart 64', 'Twisted Metal', 'NBA Jam'))
('Captain Flint', 'Mark Wahlberg', ('Mario Kart 64', 'NBA Jam', 'Twisted Metal'))
('Captain Flint', 'Mark Wahlberg', ('Twisted Metal', 'Mario Kart 64', 'NBA Jam'))
('Captain Flint', 'Mark Wahlberg', ('Twisted Metal', 'NBA Jam', 'Mario Kart 64'))
('Captain Flint', 'Mark Wahlberg', ('NBA Jam', 'Mario Kart 64', 'Twisted Metal'))
('Captain Flint', 'Mark Wahlberg', ('NBA Jam', 'Twisted Metal', 'Mario Kart 64'))
```

Suppose yet that all the competitors become hostile toward one another (i.e. Captain Flint and Long John Silver are in dispute as are Damon and Wahlberg). How many ways can pairs of competitors face each in other in a video game round? Some more code.

```
from itertools import chain, combinations
for duel in product(combinations(chain(pirates, actors), r=2), competitions):
print(duel)
```

And some more results.

```
(('Long John Silver', 'Captain Flint'), 'Mario Kart 64')
(('Long John Silver', 'Captain Flint'), 'Twisted Metal')
(('Long John Silver', 'Captain Flint'), 'NBA Jam')
(('Long John Silver', 'Matt Damon'), 'Mario Kart 64')
(('Long John Silver', 'Matt Damon'), 'Twisted Metal')
(('Long John Silver', 'Matt Damon'), 'NBA Jam')
(('Long John Silver', 'Mark Wahlberg'), 'Mario Kart 64')
(('Long John Silver', 'Mark Wahlberg'), 'Twisted Metal')
(('Long John Silver', 'Mark Wahlberg'), 'NBA Jam')
(('Captain Flint', 'Matt Damon'), 'Mario Kart 64')
(('Captain Flint', 'Matt Damon'), 'Twisted Metal')
(('Captain Flint', 'Matt Damon'), 'NBA Jam')
(('Captain Flint', 'Mark Wahlberg'), 'Mario Kart 64')
(('Captain Flint', 'Mark Wahlberg'), 'Twisted Metal')
(('Captain Flint', 'Mark Wahlberg'), 'NBA Jam')
(('Matt Damon', 'Mark Wahlberg'), 'Mario Kart 64')
(('Matt Damon', 'Mark Wahlberg'), 'Twisted Metal')
(('Matt Damon', 'Mark Wahlberg'), 'NBA Jam')
```

As it turns out, there are 18 ways for this absolutely absurd duel to
transpire. Of those duels, the first three listed are pirate-against-pirate
and the last three are actor-against-actor. As the original example expanded to
include permutations, combinations, and the like, the point was to show the
versatility of the `itertools`

package (and not to highlight the compounding
absurdity of my imagination).

Now it’s time to loop back to how this relates to math models, and here’s where it starts to get heavy. Suppose this hypothetical duel is part of some larger scenario that we are modeling, and we need to track which duels occur and which do not. To do so, we introduce a set of indicator variables \(x_{i, j, k}\) to track if pirate \(i\) duels actor \(j\) in competition \(k\). In this context, an indicator variable takes on a value of one if the corresponding event occurs. If not, then the variable is zero. This is also often called a Boolean variable or a 0-1 variable. Below, I show how this set of variables might be created in a constrained programming model built using Google’s OR-Tools.

```
from ortools.sat.python import cp_model
model = cp_model.CpModel()
x = dict()
for i, j, k in product(pirates, actors, competitions):
x[i, j, k] = model.NewBoolVar('x_{},{},{}'.format(i, j, k))
```

“Oh, *sooooo* impressive, Brent. You wrote a for-loop.” Yeah, okay, but let’s
not forget what this would look like without `itertools`

.

```
x = dict()
for i in pirates:
for j in actors:
for k in competitions:
x[i, j, k] = model.NewBoolVar('x_{},{},{}'.format(i, j, k))
```

Functionally, these are equivalent. But in my humble opinion, a single
for-loop is superior to a nested triple for-loop. I understand this could
be perceived as just a matter of style and that there is a (gentle) learning
curve here for novice Python developers. Trust me though, of all`itertools`

functions, `product`

is probably the most simple function to code up yourself.
Take a moment to consider the logic required to mimic a combination, or worse
yet a permutation, and you are sure to realize that it is **not** a matter of
style at all. Having these tools readily available is a blessing.
*Hint: A good implementation of combinations requires loops and conditional
logic; a good implementation of permutations requires the same and might also
use recursion.*

Before wrapping up, I would be remiss not to mention how often I have used
`itertools`

in conjunction with Python’s `multiprocessing`

package,
particularly `multiprocessing.Pool.starmap`

. This function runs a function
multiple times, each time using a different set of parameters. This is useful
for sweeping one or more parameters in a simulation, for example. To
generate the different sets of parameters, `itertools.product`

is awesome.
Returning to the duels, suppose we have a `simulate_duel`

function that takes
one pirate, one actor, and a competition as its parameters. If we wanted
to parallelize the simulation of all possible duels, we could use the following
(standalone) snippet.

```
from itertools import product
from multiprocessing import Pool
pirates = ['Long John Silver', 'Captain Flint']
actors = ['Matt Damon', 'Mark Wahlberg']
competitions = ['Mario Kart 64', 'Twisted Metal', 'NBA Jam']
def simulate_duel(pirate, actor, competition):
# do simulation stuff
...
return result
with Pool(processes=4) as pool:
duels = product(pirates, actors, competitions)
results = pool.starmap(simulate_duel, duels)
```

With just a little effort, we can now save time by running multiple simulations concurrently!

If by now you still do not realize how I feel about the `itertools`

package,
let me just say it outright – it’s frickin’ bodacious. Hopefully, this post
gives you a feel for how it can be used for math modeling and more, and
inspires you to integrate it into your own projects. With certainty, you can
expect to see it in my future work. If you already have a favorite or frequent
application of `itertools`

, please do share in the comments below!