---
jupytext:
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
    jupytext_version: 1.10.3
kernelspec:
  display_name: Python 3 (ipykernel)
  language: python
  name: python3
---

+++ {"slideshow": {"slide_type": "slide"}}

# Combinatorics

+++ {"slideshow": {"slide_type": "-"}, "tags": ["remove-cell"]}

**CS1302 Introduction to Computer Programming**
___

+++ {"slideshow": {"slide_type": "slide"}}

## Permutation using Recursion

+++ {"slideshow": {"slide_type": "subslide"}}

````{prf:definition} 

A [$k$-permutation of $n$](https://en.wikipedia.org/wiki/Permutation#k-permutations_of_n) items $a_0,\dots,a_{n-1}$ is an ordered tuple 

$$
(a_{i_0},\dots,a_{i_{k-1}})
$$ 
of $k$ out of the $n$ objects, where $0\leq i_0,\dots,i_{k-1}<n$ are distinct indices. An $n$-permutation of $n$ objects is simply called a permutation of $n$ objects.

````

+++ {"slideshow": {"slide_type": "fragment"}}

For examples:
- The list of ($3$-)permutations of `1,2,3` is:

```{code-cell} ipython3
---
slideshow:
  slide_type: '-'
---
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
```

+++ {"slideshow": {"slide_type": "fragment"}}

- The list of $2$-permutations of `1,2,3` is:

```{code-cell} ipython3
---
slideshow:
  slide_type: '-'
---
[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
```

+++ {"slideshow": {"slide_type": "fragment"}}

In the above, we used
- a `tuple` delimited by `()` such as `(1,2,3)` to store items of a permutation, and 
- a `list` delimited by `[]` such as `[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]` to store all the permutations.

+++ {"slideshow": {"slide_type": "subslide"}}

Generating permutations is a fundamental problem in computing and combinatorics.  
A simple way to generate permutations is by recursion. (There are also [other algorithms](https://www.topcoder.com/generating-permutations/).)

+++ {"slideshow": {"slide_type": "fragment"}}

````{prf:proposition} 

A $k$-permutation of $n$ satisfies the recurrence relation:  
- Removing the first element of a $k$-permutation of $n$ objects gives a different $(k-1)$-permutation of the remaining $n-1$ objects.

$$ (a_{i_0}, \underbrace{a_{i_1},\dots,a_{i_{k-1}}}_{\text{($k-1$)-permutation of $a_{i_1},\dots,a_{i_{k-1}}$.}\kern-5em} ) $$

- Reversing the above removal process gives a way of constructing a $k$-permutation from a $(k-1)$-permutation.  
  E.g., the permutations of $1,2,3$ can be constructed as follows:

$$[\overbrace{({\color{red} 1}, {\color{blue}{2, 3}}), ({\color{red} 1}, {\color{blue}{3, 2}})}^{\text{prepend 1 to permutations of $2,3$.} }, \overbrace{({\color{red} 2}, {\color{blue}{1, 3}}), ({\color{red} 2}, {\color{blue}{3, 1}})}^{\text{prepend 2 to permutations of $1,3$.} }, \overbrace{({\color{red} 3}, {\color{blue}{1, 2}}), ({\color{red} 3}, {\color{blue}{2, 1}})}^{\text{prepend 3 to permutations of $1,2$.} }]$$

````

+++ {"slideshow": {"slide_type": "fragment"}}

The following implements the recursion:

```{code-cell} ipython3
---
slideshow:
  slide_type: '-'
---
def permutation(*a, k=None):
    """Construct all (k-)permutations of the position arguments.

    Parameters
    ----------
    *a: object, object, ...
        n items specified as positional arguments
    k: int
        Optional argument indicating the size of each permutation. 
        Default: number n of items specified in *a.

    Returns
    -------
    list:
        List of all k-permutations represented as ordered tuples of the n objects.
    """
    n = len(a)
    output = []
    if k is None:
        k = n
    if 0 < k <= n:
        for i in range(n):
            output.extend(
                [(a[i],) + p for p in permutation(*a[:i], *a[i + 1 :], k=k - 1)]
            )
    elif k == 0:
        return [()]
    return output


print(permutation(1, 2, 3))
print(permutation(1, 2, 3, k=2))
```

+++ {"slideshow": {"slide_type": "fragment"}}

The recurrence is implemented by the for loop:
```Python
        ...
        for i in range(n):
            output.extend([(a[i], ) + p
                           for p in permutation(*a[:i], *a[i + 1:], k=k - 1)])
        ...
```

+++ {"slideshow": {"slide_type": "fragment"}}

In the above code, `(a[i],) + p` creates a $k$-permutation of the items in `a` by concatenating for each index `i`
- a singleton tuple `(a[i],)` and 
- a $(k-1)$-permutation `p` of all elements but `a[i]`.

(See the example in the recurrence relation described earlier.)

+++ {"slideshow": {"slide_type": "fragment"}}

````{note}

- The comma in `(a[i],)` is not a typo. Without commas, `(...)` does not create a tuple. 
- `a[:i]` returns a tuple of `a[0]` up to and excluding `a[i]`. `*a[:i]` unpacks the tuple such that its items are separate arguments to `permutation`. 
- Similarly, `*a[i + 1:]` provides items as separate arguments starting from `a[i + 1]` until the last item in `a`.
- `[... for ...]` generates a list of $k$-permutations, and `output.extend([...])` added the list to the end of the `output` list.

````

+++ {"slideshow": {"slide_type": "subslide"}}

**Exercise** One of the base cases of the recusion happens when $k=0$, in which case there is only one $k$-permutation, namely the empty tuple $()$, and so the function returns `[()]`. There is another base case of the recursion. Explain the condition of that base case and its return value.

+++ {"deletable": false, "nbgrader": {"cell_type": "markdown", "checksum": "6065a26e19375f235f176ebfe6fcddee", "grade": true, "grade_id": "base-case", "locked": false, "points": 1, "schema_version": 3, "solution": true, "task": false}, "slideshow": {"slide_type": "-"}}

YOUR ANSWER HERE

+++ {"slideshow": {"slide_type": "slide"}}

## Number of permutations

+++ {"slideshow": {"slide_type": "fragment"}}

Computing permutations using recursion is slow. Why?  
There are simply too many permutations even for a reasonably small $n$.

```{code-cell} ipython3
---
slideshow:
  slide_type: '-'
tags: [remove-output]
---
if input("Run? [Y/n]").lower() != "n":
    n = 10
    output = permutation(*range(1, n + 1))
    print("# permutations:", len(output))
```

+++ {"slideshow": {"slide_type": "subslide"}}

Quite surprisingly, the number of permutations can be calculated significantly faster without enumerating all the permutations.

+++

````{prf:proposition} 

The number $P_n$ of ($n-$)permutations of $n$ items satisfies the following recurrence:

$$
P_n = \begin{cases}
n P_{n-1} & n>0\\
1 & n=0\\
0 & \text{otherwise.}
\end{cases}
$$ (Pn)

````

+++

This quantity is fundamental in the field of [combinatorics](https://en.wikipedia.org/wiki/Combinatorics) with enormous applications.

+++ {"slideshow": {"slide_type": "fragment"}}

**Exercise** Implement the above recurrence equation.

```{code-cell} ipython3
---
deletable: false
nbgrader:
  cell_type: code
  checksum: b7cab2c68db19227e54d22a5b449f9ac
  grade: false
  grade_id: num_permutations
  locked: false
  schema_version: 3
  solution: true
  task: false
slideshow:
  slide_type: '-'
tags: [remove-output]
---
def num_permutation(n):
    """Compute the number of permutations.

    Parameters
    ----------
    n: int
        Number of items.

    Return
    ------
    int:
        Number of permutations of n items.
    """
    # YOUR CODE HERE
    raise NotImplementedError()
```

````{hint}

Ensure all base cases are covered, and can run efficiently for large $n$.

````

```{code-cell} ipython3
---
code_folding: [0]
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: c90e8ca4a1e355604aa2ba8450dbb9f8
  grade: true
  grade_id: test-num_permutations
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
slideshow:
  slide_type: '-'
tags: [remove-output, hide-input]
---
# tests
assert num_permutation(10) == 3628800
assert num_permutation(0) == 1
assert num_permutation(-1) == 0
```

```{code-cell} ipython3
---
code_folding: [0]
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: 538708ebb746bbee1cbfc6f8fda5cb0a
  grade: true
  grade_id: htest-num_permutations
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
tags: [remove-cell]
---
# hidden tests
```

````{prf:proposition} 

The number $P_{n,k}$ of $k$-permutations of $n$ items is given by the formula

$$
P_{n,k} = \begin{cases}
\frac{P_n}{P_{n-k}} & 0\leq k \leq n\\
0 & \text{otherwise.}
\end{cases}
$$ (Pnk)

````

+++ {"slideshow": {"slide_type": "subslide"}}

**Exercise** Extend the function `num_permutation` to allow for a optional argument `k`.

```{code-cell} ipython3
---
deletable: false
nbgrader:
  cell_type: code
  checksum: e51dd57301825d870dd769c5ae762e90
  grade: false
  grade_id: num_permutation_k
  locked: false
  schema_version: 3
  solution: true
  task: false
tags: [remove-output]
---
def num_permutation(n, k=None):
    """Compute the number of k-permutations of n items.

    Parameters
    ----------
    n: int
        Number of items to permute.
    k: int
        Optional argument indicating the size of each permutation.
        Default: n

    Returns
    -------
    int:
        Number of k-permutations of n items.
    """
    # YOUR CODE HERE
    raise NotImplementedError()
```

```{code-cell} ipython3
---
code_folding: [0]
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: 0be258ccdc62a9203d4ef40ca83b3576
  grade: true
  grade_id: test-num_permutation_k
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
tags: [remove-output, hide-input]
---
# tests
assert isinstance(num_permutation(0), int)
assert num_permutation(3) == 6
assert num_permutation(3, 0) == 1
assert num_permutation(3, 2) == 6
assert num_permutation(10, 5) == 30240
```

```{code-cell} ipython3
---
code_folding: [0]
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: 2b965ed10f9c5a88be084179b949465d
  grade: true
  grade_id: htest-num_permutation_k
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
tags: [remove-cell]
---
# hidden tests
```

+++ {"slideshow": {"slide_type": "slide"}}

## Permutation using Iteration

+++ {"slideshow": {"slide_type": "subslide"}}

The following function `permutation_sequence(*a)` returns a generator that generates the list of $k$-permutations one-by-one for $k$ from $0$ to `len(a)`.

```{code-cell} ipython3
---
slideshow:
  slide_type: '-'
---
def permutation_sequence(*a):
    """Returns a generator for the k-permuations of the positional arguments
    for k from 0 to len(a)."""
    n = len(a)
    output, idx_left = [()], [tuple(range(n))]
    for k in range(n + 1):
        yield output
        next_output, next_idx_left = [], []
        for m in range(len(idx_left)):
            for j in range(len(idx_left[m])):
                i = idx_left[m][j]
                next_output.append(output[m] + (a[i],))
                next_idx_left.append(idx_left[m][:j] + idx_left[m][j + 1 :])
        output, idx_left = next_output, next_idx_left


for permutation_list in permutation_sequence(1, 2, 3):
    print(permutation_list)
```

+++ {"slideshow": {"slide_type": "fragment"}}

Unlike the recursive function `permutation`, the above generates a $k$-permutation $(a_{i_0},\dots,a_{i_{k-1}})$ of $n$ items iteratively by 
- choosing $i_j$ for $j$ from $0$ to $k-1$ such that
- $i_j$ is not already chosen, i.e., $i_j\not\in \{i_0,\dots,i_{j-1}\}$.

+++ {"slideshow": {"slide_type": "fragment"}}

E.g., the permutations of $1,2,3$ is generated iteratively as follows:
- 1
 - 1,2
   - **(1,2,3)**
 - 1,3
   - **(1,3,2)**
- 2
 - 2,1
   - **(2,1,3)**
 - 2,3
   - **(2,3,1)**
- 3
 - 3,1
   - **(3,1,2)**
 - 3,2
   - **(3,2,1)**

+++ {"slideshow": {"slide_type": "fragment"}}

````{prf:proposition} 

`permutation_sequence` maintains the following *invariance* at the beginning of each iteration:  
- `output` is the list of $k$-permutations, and
- `idx_left[m]` is the list of indices of arguments not yet in `output[m]`. 

A $(k+1)$-permutation (in `next_output`) can then be generated by appending an argument (with an index from `idx_left`) to a $k$-permutation (in `output`).

````

+++ {"slideshow": {"slide_type": "subslide"}}

Is iteration significantly faster?

```{code-cell} ipython3
---
slideshow:
  slide_type: '-'
tags: [remove-output]
---
if input("Run? [Y/n]").lower() != "n":
    n = 10
    for k, permutation_list in enumerate(permutation_sequence(*range(1, n + 1))):
        print("# {}-permutations of {} items: {}".format(k, n, len(permutation_list)))
```

+++ {"slideshow": {"slide_type": "fragment"}}

Unfortunately, there is not much improvement. Nevertheless, we can efficiently compute the number of $k$-permutations based on the previously computed number of $k-1$-permutations:

For $k$ from $0$ to $n$,

$$
P_{n,k} = \underbrace{\overbrace{n\times  (n-1)\times \cdots }^{P_{n,k-1}\text{  if }k>0}\times(n-k+1)}_{\text{$k$ terms in the product.}}.$$ (Pnk:expanded)

+++ {"slideshow": {"slide_type": "subslide"}}

**Exercise** Use the `yield` statement to write the function `num_permutation_sequence(n)` that returns a generator of $P_{n,k}$ with `k` from `0` to `n`.

```{code-cell} ipython3
---
deletable: false
nbgrader:
  cell_type: code
  checksum: 9e08e8ce2528e86b39e69a97341e658d
  grade: false
  grade_id: num_permutation_sequence
  locked: false
  schema_version: 3
  solution: true
  task: false
slideshow:
  slide_type: '-'
tags: [remove-output]
---
def num_permutation_sequence(n):
    output = 1
    for k in range(0, n + 1):
        # YOUR CODE HERE
        raise NotImplementedError()
```

```{code-cell} ipython3
---
code_folding: [4]
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: a85762cc92101f82bd75abef167a5c94
  grade: true
  grade_id: test-num_permutation_sequence
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
slideshow:
  slide_type: '-'
tags: [remove-output, hide-input]
---
# tests
assert [m for m in num_permutation_sequence(3)] == [1, 3, 6, 6]
assert [m for m in num_permutation_sequence(10)] == [
    1,
    10,
    90,
    720,
    5040,
    30240,
    151200,
    604800,
    1814400,
    3628800,
    3628800,
]
```

```{code-cell} ipython3
---
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: c4a61482dcb54b55ef58f6aebbd93ddf
  grade: true
  grade_id: htest-num_permutation_sequence
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
tags: [remove-cell]
---
# hidden tests
```

+++ {"slideshow": {"slide_type": "subslide"}}

**Exercise** Extend the function `num_permutation_sequence(n)` so that calling `send(0)` method causes the generator to increment $n$ instead of $k$ for the next number to generate. i.e., for $0\leq k \leq n$,

$$\dots P_{n,k-1}\to P_{n,k} \xrightarrow{\text{send(0)}} P_{n+1,k} \to P_{n+1,k+1}\dots$$
where $\to$ without labels is the normal transition without calling the `send` method.

```{code-cell} ipython3
---
deletable: false
nbgrader:
  cell_type: code
  checksum: 92242250b63efa784aef38bdf671edbc
  grade: false
  grade_id: num_permutation_sequence_send
  locked: false
  schema_version: 3
  solution: true
  task: false
slideshow:
  slide_type: '-'
tags: [remove-output]
---
def num_permutation_sequence(n):
    # YOUR CODE HERE
    raise NotImplementedError()
```

````{hint}

By {eq}`Pnk:expanded`,

$$P_{n+1,k}=P_{n,k} \times \frac{n+1}{n-k+1}.$$

````

```{code-cell} ipython3
---
code_folding: []
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: f0d6f42aa98c2988e0b9a135eaa20940
  grade: true
  grade_id: test-num_permutation_sequence_send
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
slideshow:
  slide_type: '-'
tags: [remove-output, hide-input]
---
# tests
g = num_permutation_sequence(3)
assert (next(g), next(g), g.send(0), next(g), next(g), next(g), g.send(0)) == (
    1,
    3,
    4,
    12,
    24,
    24,
    120,
)
```

```{code-cell} ipython3
---
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: 81c9c370c3e5f9429cb4993c07f3489c
  grade: true
  grade_id: htest-num_permutation_sequence_send
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
tags: [remove-cell]
---
# hidden tests
```

+++ {"slideshow": {"slide_type": "slide"}}

## Deduplication using Decorator

+++ {"slideshow": {"slide_type": "subslide"}}

An issue with the function `permutation` is that it regards arguments at different positions as distinct even if they may have the same value. E.g.,  
`permutation(1,1,2)` returns `[(1, 1, 2), (1, 2, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 1, 1)]`  
where each distinct permutation appears twice.

+++ {"slideshow": {"slide_type": "fragment"}}

To remove duplicates from a list, we can  
- convert the list to a `set` (which automatically remove duplicates),
- and then convert the set back to a list.

```{code-cell} ipython3
---
slideshow:
  slide_type: fragment
---
print("Deduplicated:", list(set(permutation(1, 1, 2))))
```

+++ {"slideshow": {"slide_type": "subslide"}}

Using a decorator, we can fix `permutation` without rewriting the function.

```{code-cell} ipython3
---
slideshow:
  slide_type: fragment
---
import functools


def deduplicate_output(f):
    """Takes in a function f that returns a list possibly with duplicates,
    returns a decorator that remove duplicates from the output list."""

    @functools.wraps(f)
    def wrapper(*args, **kwargs):
        return list(set(f(*args, **kwargs)))

    return wrapper


permutation = deduplicate_output(permutation)
print("Deduplicated: ", permutation(1, 1, 2))
permutation = permutation.__wrapped__
print("Original: ", permutation(1, 1, 2))
```

+++ {"slideshow": {"slide_type": "subslide"}}

**Exercise:** Create a decorator to eliminate duplicate input positional arguments instead of the ouput, i.e.,  
`permutation(1,1,2)` will return the same result as `permutation(1,2)`.

```{code-cell} ipython3
---
deletable: false
nbgrader:
  cell_type: code
  checksum: fc23b25ff4c3ab03c48284138fd665f5
  grade: false
  grade_id: deduplicate_input
  locked: false
  schema_version: 3
  solution: true
  task: false
slideshow:
  slide_type: '-'
tags: [remove-output]
---
def deduplicate_input(f):
    """Takes in a function f that takes a variable number of arguments
    possibly with duplicates, returns a decorator that remove duplicates
    in the positional argument."""

    @functools.wraps(f)
    def wrapper(*args, **kwargs):
        # YOUR CODE HERE
        raise NotImplementedError()

    return wrapper
```

```{code-cell} ipython3
---
code_folding: []
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: 884d845656234100fa3e3d36425b3240
  grade: true
  grade_id: test-deduplicate_input
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
slideshow:
  slide_type: '-'
solution: hidden
tags: [remove-output, hide-input]
---
# tests
permutation = deduplicate_input(permutation)
try:
    assert set(permutation(1, 1, 2)) == set([(1, 2), (2, 1)])
finally:
    permutation = permutation.__wrapped__
```

```{code-cell} ipython3
---
deletable: false
editable: false
nbgrader:
  cell_type: code
  checksum: 5c84f05f5de285298f9406347fb887cf
  grade: true
  grade_id: htest-deduplicate_input
  locked: true
  points: 1
  schema_version: 3
  solution: false
  task: false
tags: [remove-cell]
---
# hidden tests
```