Combinatorics in python – a pygraz presentation

# “Combinatorics in python”

![pygraz.org](resource/py.svg "Python Usergroup Graz") <br/>
<span style="font-family:Averia; text-shadow: 0pt 25pt 8pt grey">4th of Mar 2014, Lukas Prokop</span> <br/>
<span style="font-family:Averia; text-shadow: 0pt 15pt 5pt grey">Bugfixed and extended afterwards</span>

---

“The kind of programming I like best”

(Don Knuth, TAOCP Vol 4, inofficial subtitle)

---

“Enumerative Combinatorics” <br />
by <span style="color:#999">Robert P. Stanley</span>

---

Whenever a programmer cries <br />
"Grml, my math skills aren't good enough to tackle this problem" <br />
… he has come across combinatorics.

---

## Overview

1. Combinatorics by example
2. Simple problems
3. Cheatsheet
4. Combinatorics in python
5. My 50-minutes project

---

## Introduction

- Counting problems
- Given … How many … exist?
- We programmers come across discrete values all the time
- We often have to specify boundaries
- We often want to generate all possibilities (efficiently)

```python
count = len(range(20, 1234, 5))
```

---

- python's `range` is half-open (start inclusive, end exclusive)
- we don't discuss this design here, but I think it's awesome 😇
- 0 to 1234 = 1235 elements
- 1 to 1234 = 1234 elements
- 20 to 1234 = 1215 elements

---

- 1215 / 5 = <mark>243 elements</mark>

---

## Grids and lattice paths

![Vim adventures](resource/game.png "VIM adventures")

---

## Grids and lattice paths

![Path #1](resource/game_path1.png "Path #1")

---

## Grids and lattice paths

![Path #2](resource/game_path2.png "Path #2")

---

## Grids and lattice paths

![Path #2](resource/game_grid.png "Game grid")

---

## Grids and lattice paths

- Only possible moves are either "south" or "west".
- 7 moves must be south, 11 must be west (7×11 grid).
- We can encode paths also as "wwsswwwwwsswsswsww".
- Solution is the number of permutations of those words.

---

- Permutations? This thingy where factorials are involved.

… which gives us <mark>31824</mark>.

---

## Catalan numbers

- For the special case of a n×n grid.
- C<sub>n</sub> is the
  - number of paths along the edges of a n×n grid.
  - number of ways of associating <code>n</code> applications of a binary operator.
  - number of different ways <var>n</var> + 1 factors can be completely parenthesized; eg. ((ab)c)d
  - number of Dyck words of length 2n
- Dyck word means that the number of "w" and "s" is balanced.

Another classic: Number of paths which do not cross the diagonal… is C<sub>n</sub>

---

## Graph theory in general

General graphs

Bipartite graph <span class="smallfont">(sets M and N of vertices, edges only combine elements of different sets)</span>:

---

## Rubik's Cube

<math>
  <mrow>
    <mn>8</mn>
    <mo lspace="0">!</mo>
    <mo>·</mo>
    <msup>
      <mn>3</mn>
      <mn>7</mn>
    </msup>
    <mo>·</mo>
    <mfrac>
      <mrow><mn>12</mn><mo lspace="0">!</mo></mrow>
      <mn>2</mn>
    </mfrac>
    <mo>·</mo>
    <msup>
      <mn>2</mn>
      <mn>11</mn>
    </msup>
    <mspace width="20pt" />
    <ms lquote="" rquote="">configurations</ms>
  </mrow>
</math>

---

## Probability theory

When all events occur with the same probability,
the analysis of positive cases reduces to combinatorial problems.

Throwing a dice, what is the probability …

- that an even number is the result?
- that a number smaller 3 is the result?

---

## Coding theory

Binary alphabet

---

## Coding theory

Binary alphabet

---

## Coding theory

Binary alphabet

---

## Coding theory

Binary alphabet

---

## Coding theory

Binary alphabet

---

## Coding theory

Binary alphabet

---

## Coding theory

Binary alphabet

---

## Coding theory

Binary alphabet

---

## Coding theory

Binary alphabet

---

- size of alphabet to the power of number of digits
- here: <math><msup><mn>2</mn><mn>3</mn></msup> <mo>=</mo> <mn>8</mn></math>

<div class="center">
  <math>
    <msup>
      <mfenced open="|" close="|"><mi>alphabet</mi></mfenced>
      <mfenced open="|" close="|"><mi>digits</mi></mfenced>
    </msup>
  </math>
</div>

---

## Lotto

In Austria: (basically) 6 out of 45.

---

## Groups

How many combinations are there to distribute <var>m</var> seats among <var>n</var> groups?

---

Okay, enough examples…

The following model is incomplete, but easy to remember.

---

## Cheatsheet

<var>n</var> = size of origin set, <var>r</var> = elements of this set

<table id="cheatsheet">
  <thead>
    <tr>
      <th></th>
      <th>with repetition</th>
      <th>w/o repetition</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>Variation</td>
      <td><math class="smallfont">
        <msub><mi>V</mi><mi>r</mi></msub><mo>⁡</mo><mfenced><mi>n</mi><mi>r</mi></mfenced>
        <mo>=</mo>
        <msup><mi>n</mi><mi>r</mi></msup>
      </math></td>
      <td><math class="smallfont">
        <mi>V</mi><mo>⁡</mo><mfenced><mi>n</mi><mi>r</mi></mfenced>
        <mo>=</mo>
        <mfenced>
          <mrow>
            <mfrac>
              <mrow><mi>n</mi><mo lspace="0">!</mo></mrow>
              <mrow><mfenced><mrow><mi>n</mi><mo>-</mo><mi>r</mi></mfenced><mo lspace="0">!</mo></mrow>
            </mfrac>
          </mrow>
        </mfenced>
      </math></td>
    </tr>
    <tr>
      <td>Combination</td>
      <td><math class="smallfont">
        <msub><mi>C</mi><mi>r</mi></msub><mo>⁡</mo><mfenced><mi>n</mi><mi>r</mi></mfenced>
        <mo>=</mo>
        <mfenced><mfrac linethickness="0"><mrow><mi>n</mi><mo>+</mo><mi>r</mi><mo>-</mo><mn>1</mn></mrow><mi>r</mi></mfrac></mfenced>
      </math></td>
      <td><math class="smallfont">
        <mi>C</mi><mo>⁡</mo><mfenced><mi>n</mi><mi>r</mi></mfenced>
        <mo>=</mo>
        <mfenced><mfrac linethickness="0"><mi>n</mi><mi>r</mi></mfrac></mfenced>
      </math></td>
    </tr>
  </tbody>
</table>

---

### 2 questions in this model

- Is the order relevant?
  - Yes ⇒ variation
  - No ⇒ combination
- Do elements of the origin set repeat?
  - Yes ⇒ with repetition
  - No ⇒ w/o repetition

---

### Example sets

<var>n</var> = {1,2,3} or its cardinality <br />
<var>r</var> = 2

---

### Example 1

Running competition. How many possible TOP3 rankings are there for <var>10</var> competitors?

---

(order matters, no repetition of competitors)

---

### Example 2

<var>20</var> non-distinguishable balls are put into <var>5</var> numbered boxes.
How many possibilities?

---

(order does not matter, non-distinguishable = with repetition)

---

And now something completely different!

---

## What have we seen so far?

- factorials
- some binomial coefficients
- tools called combinations, permutations and variations

---

## python: math

factorials?

```python
In [1]: import math

In [2]: math.factorial(20)
Out[2]: 2432902008176640000

In [3]: math.factorial(-20)
-------------------------------------------------------
ValueError            Traceback (most recent call last)
<ipython-input-4-9c48d7150995> in <module>()
----> 1 math.factorial(-20)

ValueError: factorial() not defined for negative values
```

No particular differences between CPython and PyPy for large inputs.

---

## python: itertools

Combinatoric generators:

- `itertools.product(p, q, …, repeat=N)`
- `itertools.permutations(p, r=N)`
- `itertools.combinations(p, r=N)`
- `itertools.combinations_with_replacement(p, r=N)`

```python
In [1]: import itertools

In [2]: itertools.product('01', repeat=3)
Out[2]: <itertools.product at 0x25a2320>

In [3]: list(itertools.product('01', repeat=3))
Out[3]: 
[('0', '0', '0'), ('0', '0', '1'), ('0', '1', '0'),
 ('0', '1', '1'), ('1', '0', '0'), ('1', '0', '1'),
 ('1', '1', '0'), ('1', '1', '1')]
```

---

<hr />

- V<sub>r</sub>(n, r) is exactly `itertools.product(n, repeat=r)`
- C(n, r) is exactly `itertools.combinations(n, r)`
- V(n, r) is exactly `itertools.permutations(n, r)`
- C<sub>r</sub>(n, r) is exactly `itertools.combinations_with_replacement(n, r)`

---

## python in general

### Combinatorics 1.4.2

A nicely engineered Combinatorics package is available at PyPI.
I won't present it here, but it shows APIs for other combinatorial
problems. It's useful for particular usecases; not general theory.

### stdlib

Shall we provide other combinatorial stuff in the stdlib?
Binomial coefficients?

- Yes, I am missing binomial coefficients.
- No, there are many sequences which only make sense for small values.
  Greater values take long to compute and occur very seldom.
- No, they are part of numpy/scipy anyways.

---

### yield

Python's yield makes it easy to uncouple control flow from return values.

```python
In [1]: def func(x):
   ...:     for i in range(20):
   ...:         yield x + i
   ...:

In [2]: func(3)
Out[2]: <generator object func at 0x25df500>

In [3]: list(func(3))
Out[3]: [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
         14, 15, 16, 17, 18, 19, 20, 21, 22]
```

yield does **not** provide a performance tuning!

---

## python's expressiveness

Via [Nas Banov](http://stackoverflow.com/a/3027128)

```python
from operator import mul    # or mul=lambda x,y:x*y
from fractions import Fraction

def nCk(n, k):
  return int(reduce(mul, (Fraction(n-i, i+1)
      for i in range(k)), 1))

for n in range(5):
    print ' '.join('%5d' % nCk(n, k)
                   for k in range(n+1)).center(50)

1                       
               1     1                    
            1     2     1                 
         1     3     3     1              
      1     4     6     4     1
```

---

Let's get a bit crazy…

---

## My 50 minutes project

12th of Dec 2013.

<table>
  <tr><td>08:15</td><td>Lecture starts.</td></tr>
  <tr><td>09:30</td><td>We discuss an exercise I did not look at so far.</td></tr>
  <tr><td>10:00</td><td>End of lecture. Time to hack.</td></tr>
  <tr><td>10:50</td><td>Implementation done. Results ready.</td></tr>
</table>

### The problem

<blockquote>
<p>
  Given is a matrix n×m. Each cell of this matrix is colored with one
  of two colors. We can span a rectangle and each corner touches a
  different cell.
</p>

<p>
  Show that there exists n and m such that: an arbitrary 2-colouring
  of an n×m matrix contains the 9 squares of a monochromatic
  (axe-parallel) 2×2 subgrid.
</p>
</blockquote>

---

## Example

---

## Example

---

## Example

---

## Example

---

Thus, there is some 2-coloring for 4×5 such that a monochromatic rectangle is contained.

---

## Example

Also there is some 2-coloring for 4×5 such that a monochromatic rectangle is **not** contained.

---

## Example 4×6

There is some 2-coloring for 4×6 such that **no** monochromatic rectangle is contained.

---

### The solution approach

Yes, you can generate all colorings… with *exponential* runtime.
Do you remember how variations grow (alphabet to the power of digits)?

Well, we don't know any better algorithm. So let's do it the most efficient way ⇒ SAT solvers!

1. Represent the problem as boolean equation.
2. SAT solver finds satisfying assignment.
3. SAT solver tells you how this equation is satisfied (SAT)
   or that it is impossible (UNSAT).

- Difficult for complex encodings.
- Easy if problem is akin to boolean algebra; like here.

---

## SAT problem

- 2 coloring? The boolean values are our colors!
- A rectangle {a,b,c,d} is non-monochromatic iff

- We generate all rectangles and define this clause for every rectangle.
  Generate? Yes, generate. The generation of all rectangles is seriously a problem for large input sizes.
- The conjunction of those clauses are the input for the SAT solver.
- SAT solver tells us valid solutions or UNSAT.

---

## SAT solver in python?

pycosat is a binding for PicoSAT.

```python
In [1]: import pycosat

In [2]: pycosat.solve([[1, 2, 3], [-1, -2, 3]])
Out[2]: [-1, -2, 3]

In [3]:
```

I could rant about C++ interfaces so much.

---

## Python implementation \[[0](resource/2colors.orig.py) [1](resource/2colors.general.py)]

```python
comb = itertools.combinations

def solve(size, height, width):
  cnf = []

for xs in comb(range(0, width), r=size):
    for ys in comb(range(0, height), r=size):
      indices = []

for i in range(0, size):
        for j in range(0, size):
          indices.append(ys[i] * width + xs[j] + 1)

cnf.append(indices)
      cnf.append([-i for i in indices])

return pycosat.itersolve(cnf)
```

---

## Results

Given matrix <var>h</var>×<var>w</var>. <var>size</var> = 2. Took <20 sec. Similar to [A007466](https://oeis.org/A007466).

---

## Where to go from here?

1. Always have this cheatsheet with you.
   I guess you can cover 90% of all combinatorial problems you are facing.
2. Otherwise study the problem and evaluate it for small inputs.
   Then match the sequence with [Sloane/OEIS](http://oeis.org/).
3. Solutions where we generate all variations and skip the ones which do
   not satisfy all conditions are generally slow.

You want to practice?

- [projecteuler](http://projecteuler.net/) is built of such problems.
  My Catalan numbers example is incidentally exercise 15 "Lattice paths".
- Tackle problems in probability theory.
- What about playing combinatorial games?
- What about visualizing combinatorial graph solutions?

---

Thanks guys

… and thank you, python 😎