Combinatorics and itertools
August 12, 2016 at 6:33 PM by Dr. Drang
Yesterday I ran into an interesting little two-stage combinatorics problem. I solved the math portion of the problem (how many possibilities are there?) with a couple of elementary calculations, and I solved the enumeration portion of the problem (list all the possibilities) by learning how to use a couple of functions in the Python itertools library.
This is the problem:1
Six books are lying on a table in front of you. How many ways can you arrange the books, considering both the left-to-right order of the books and whether they’re set with the front cover facing up or down?
Here are a couple of example arrangements. Other manipulations of the books, like spinning them around or setting them on their spine, are not considered.
The key to solving this problem is recognizing that it’s essentially an overlay of two simple problems. The first is the ordering of the books, which is a permutation problem. Six items can be ordered in different ways. The second is the up-or-down sequence of the six books, which can be done in different ways.
Because each of the 720 orderings of the books can have 64 up/down orientation sequences, the total number of arrangements of this type is .
That’s the easy part. The harder part is listing all the arrangements. My first thought was to write a recursive function or two, but I stopped myself, figuring there must be a Python library that’s already solved this problem. And so there is; I just had to learn how to use it.
The first thing I learned was that the itertools library is, as its name implies, all about iterators. These are Python objects that represent a stream of data, but which don’t provide the entire stream at once. Printing an iterator object gets you a description like this,
<itertools.permutations object at 0x103b9e650>
not the full sequence. You have to step (or iterate) through an iterator to get its contents.
We’ll be using the itertools permutations and product functions.2
python:
from itertools import permutations, product
To make things fit here in the post, I’m going to reduce the size of the problem to three books, which we’ll call A, B, and C. We can define them as the characters in a string. Similarly, we’ll call the orientations of the books u and d.
python:
books = 'ABC'
orient = 'ud'
Let’s start by solving the book-ordering problem by itself. The simplest form of the permutations function does exactly what we want:
python:
for b in permutations(books):
print b
The output is
('A', 'B', 'C')
('A', 'C', 'B')
('B', 'A', 'C')
('B', 'C', 'A')
('C', 'A', 'B')
('C', 'B', 'A')
OK, maybe this isn’t exactly what we want. We gave it a string and it gave us back a sequence of tuples instead of a sequence of strings. Still, it is the permutations we wanted, and we can work with it.
The up/down orientation problem can be solved with product, which returns an iterator of the Cartesian product of the inputs. In a nutshell, what this means is that if you give it a pair of lists, product will return an iterator that walks through every possible pairwise combination of the inputs’ elements. Similarly, if you give it three lists, it returns all the possible triplets.
For our three-book problem, we want something like this:
python:
for p in product(orient, orient, orient):
print p
The output is the sequence of possibilities:
('u', 'u', 'u')
('u', 'u', 'd')
('u', 'd', 'u')
('u', 'd', 'd')
('d', 'u', 'u')
('d', 'u', 'd')
('d', 'd', 'u')
('d', 'd', 'd')
But product doesn’t have to be used in such a naive way. When the same input is repeated, you can tell it so.
python:
for p in product(orient, repeat=3):
print p
Even better, we can make it clear that the number of repeats is equal to the number of books.
python:
for p in product(orient, repeat=len(books)):
print p
The answer is the same sequence as above.
Now that we know how to solve the two individual problems, we can take the Cartesian product of them to get the all the arrangements of the combined problem.
python:
for c in product(permutations(books), product(orient, repeat=len(books))):
print c
This gives all arrangements for this smaller problem.
(('A', 'B', 'C'), ('u', 'u', 'u'))
(('A', 'B', 'C'), ('u', 'u', 'd'))
(('A', 'B', 'C'), ('u', 'd', 'u'))
(('A', 'B', 'C'), ('u', 'd', 'd'))
(('A', 'B', 'C'), ('d', 'u', 'u'))
(('A', 'B', 'C'), ('d', 'u', 'd'))
(('A', 'B', 'C'), ('d', 'd', 'u'))
(('A', 'B', 'C'), ('d', 'd', 'd'))
(('A', 'C', 'B'), ('u', 'u', 'u'))
(('A', 'C', 'B'), ('u', 'u', 'd'))
.
.
.
(('C', 'A', 'B'), ('d', 'd', 'u'))
(('C', 'A', 'B'), ('d', 'd', 'd'))
(('C', 'B', 'A'), ('u', 'u', 'u'))
(('C', 'B', 'A'), ('u', 'u', 'd'))
(('C', 'B', 'A'), ('u', 'd', 'u'))
(('C', 'B', 'A'), ('u', 'd', 'd'))
(('C', 'B', 'A'), ('d', 'u', 'u'))
(('C', 'B', 'A'), ('d', 'u', 'd'))
(('C', 'B', 'A'), ('d', 'd', 'u'))
(('C', 'B', 'A'), ('d', 'd', 'd'))
The presentation is a mess, but we can clean that up easily enough by changing the print statement.
python:
for c in product(permutations(books), product(orient, repeat=len(books))):
print ' '.join(x + y for x,y in zip(*c))
This gives us a more readable output.
Au Bu Cu
Au Bu Cd
Au Bd Cu
Au Bd Cd
Ad Bu Cu
Ad Bu Cd
Ad Bd Cu
Ad Bd Cd
Au Cu Bu
Au Cu Bd
.
.
.
Cd Ad Bu
Cd Ad Bd
Cu Bu Au
Cu Bu Ad
Cu Bd Au
Cu Bd Ad
Cd Bu Au
Cd Bu Ad
Cd Bd Au
Cd Bd Ad
The permutations and product functions can take any sequence type as their arguments, so we could define books and orient this way,
python:
books = ("Cat's Cradle", "Slaughterhouse Five", "Mother Night", "Mr. Rosewater", "Breakfast of Champions", "Monkey House")
orient = ("up", "down")
and save the sequence of arrangements for the full problem as a CSV file:
python:
f = open('arrangements.csv')
for c in product(permutations(books), product(orient, repeat=len(books)):
f.write(','.join(x + ' ' + y for x,y in zip(*c)) + '\n')
f.close()
This gives us the full solution: a 6-column, 48,080-row table with entries that look like this:
Cat's Cradle down
The file can be imported into a spreadsheet or a Pandas data frame for later processing.
Sometimes just knowing how many arrangements are possible is all you need, but when you have to provide the arrangements themselves, itertools has you covered.
-
OK, this isn’t actually the problem. I’m loath to pose it the way it was posed to me because that might betray a confidence. But mathematical features of the problem as posed here is an exact match to those of the original problem. ↩
-
I used Python interactively to explore the itertools functions and solve the problem, so instead of presenting a full script, I’m going to give the solution as a series of steps with narrative in between. I used Jupyter in console mode, but there are other ways to use Python interactively. ↩
