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.

1
2
3
4
5
6
7
8
9

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,

1
2
3
4

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.

1
2
3
4

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.

1
2
3
4
5
6

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.

1
2
3
4
5

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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!