{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    },
    "tags": [
     "remove-cell"
    ]
   },
   "source": [
    "**CS1302 Introduction to Computer Programming**\n",
    "___"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Permutation using Recursion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "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 \n",
    "\n",
    "$$\n",
    "(a_{i_0},\\dots,a_{i_{k-1}})\n",
    "$$ \n",
    "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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "For examples:\n",
    "- The list of ($3$-)permutations of `1,2,3` is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:23:14.051413Z",
     "start_time": "2020-11-08T05:23:14.035846Z"
    },
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- The list of $2$-permutations of `1,2,3` is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:23:14.073916Z",
     "start_time": "2020-11-08T05:23:14.066404Z"
    },
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "In the above, we used\n",
    "- a `tuple` delimited by `()` such as `(1,2,3)` to store items of a permutation, and \n",
    "- 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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Generating permutations is a fundamental problem in computing and combinatorics.  \n",
    "A simple way to generate permutations is by recursion. (There are also [other algorithms](https://www.topcoder.com/generating-permutations/).)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Recurrence relation (Line 10):**  \n",
    "- Removing the first element of a $k$-permutation of $n$ objects gives a different $(k-1)$-permutation of the remaining $n-1$ objects.\n",
    "\n",
    "$$ (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} ) $$\n",
    "- Reversing the above removal process gives a way of constructing a $k$-permutation from a $(k-1)$-permutation.  \n",
    "  E.g., the permutations of $1,2,3$ can be constructed as follows:\n",
    "\n",
    "$$[\\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$.} }]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The following is an implementation of the recursion `permutation(*a,k=None)` that\n",
    "- takes in a variable number $n$ of objects as positional arguments (in `a`),\n",
    "- takes in an integer $k$ using a keyword argument (`k`, with the default `k=None` for $k=n$), and\n",
    "- returns the list of all $k$-permutations represented as ordered tuples of the $n$ objects."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:31:59.448981Z",
     "start_time": "2020-11-08T05:31:59.438704Z"
    },
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def permutation(*a, k=None):\n",
    "    '''Returns the list of (k-)permutations of the position arguments.'''\n",
    "    n = len(a)\n",
    "    output = []\n",
    "    if k is None:\n",
    "        k = n\n",
    "    if 0 < k <= n:\n",
    "        for i in range(n):\n",
    "            output.extend([(a[i], ) + p for p in permutation(*a[:i], *a[i + 1:], k=k - 1)])\n",
    "    elif k == 0:\n",
    "        return [()]\n",
    "    return output\n",
    "\n",
    "print(permutation(1, 2, 3))\n",
    "print(permutation(1, 2, 3, k=2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The recurrence is implemented by the for loop:\n",
    "```Python\n",
    "        ...\n",
    "        for i in range(n):\n",
    "            output.extend([(a[i], ) + p\n",
    "                           for p in permutation(*a[:i], *a[i + 1:], k=k - 1)])\n",
    "        ...\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "In the above code, `(a[i], ) + p` creates a $k$-permutation of the items in `a` by concatenating for each index `i`\n",
    "- a singleton tuple `(a[i], )` and \n",
    "- a $k-1$ permutation `p` of all elements but `a[i]`.\n",
    "\n",
    "(See the example in the recurrence relation described earlier.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Note that:\n",
    "- The comma in `(a[i], )` is not a typo. Without commas, `(...)` does not create a tuple. \n",
    "- `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`. \n",
    "- Similarly, `*a[i + 1:]` provides items as separate arguments starting from `a[i + 1]` until the last item in `a`.\n",
    "- `[... for ...]` generates a list of $k$-permutations, and `output.extend([...])` added the list to the end of the `output` list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "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": "-"
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Number of permutations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Computing permutations using recursion is slow. Why?  \n",
    "There are simply too many permutations even for a reasonably small $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:23:15.737284Z",
     "start_time": "2020-11-08T05:23:14.336599Z"
    },
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "n = 9\n",
    "output = permutation(*range(1,n+1))\n",
    "print('# permutations:',len(output))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Surprisingly, the number $P_n$ of ($n-$)permutations of $n$ items can be calculated much faster without enumerating all the permutations. It satisfies the following recurrence:\n",
    "\n",
    "$$\n",
    "P_n = \\begin{cases}\n",
    "n P_{n-1} & n>0\\\\\n",
    "1 & n=0\\\\\n",
    "0 & \\text{otherwise.}\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "This quantity is fundamental in the field of [combinatorics](https://en.wikipedia.org/wiki/Combinatorics) with enormous applications."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Exercise** Implement the above recurrence equation as a recursion `num_permutation(n)` which\n",
    "- takes in an integer `n`, and\n",
    "- returns the number of permutations of `n` items.\n",
    "\n",
    "*Hint: Ensure all base cases are covered, and can run efficiently for large $n$.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:23:15.742351Z",
     "start_time": "2020-11-08T05:23:15.739557Z"
    },
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "4573ab58a28a125941b002bd3420087c",
     "grade": false,
     "grade_id": "num_permutations",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    },
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def num_permutation(n):\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:23:15.753767Z",
     "start_time": "2020-11-08T05:23:15.744017Z"
    },
    "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": "-"
    }
   },
   "outputs": [],
   "source": [
    "# tests\n",
    "assert num_permutation(10) == 3628800\n",
    "assert num_permutation(0) == 1\n",
    "assert num_permutation(-1) == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Exercise** Extend the function to `num_permutation(n,k=None)` which\n",
    "- takes in an additional optional keyword argument `k`, and\n",
    "- returns the INTEGER number of `k`-permutations of `n` items.\n",
    "\n",
    "The number is given by the formula\n",
    "\n",
    "$$P_{n,k} = \\begin{cases}\n",
    "\\frac{P_n}{P_{n-k}} & 0\\leq k \\leq n\\\\\n",
    "0 & \\text{otherwise.}\n",
    "\\end{cases}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-19T01:47:17.090744Z",
     "start_time": "2020-11-19T01:47:17.082966Z"
    },
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "2d7e2a37a6b0275c2274acec3c404a02",
     "grade": false,
     "grade_id": "num_permutation_k",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def num_permutation(n,k=None):\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-19T01:47:19.697600Z",
     "start_time": "2020-11-19T01:47:19.667316Z"
    },
    "code_folding": [],
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "562dde90372dde2c282deb9f83a86c2d",
     "grade": true,
     "grade_id": "test-num_permutation_k",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# tests\n",
    "assert isinstance(num_permutation(0), int)\n",
    "assert num_permutation(3) == 6\n",
    "assert num_permutation(3,0) == 1\n",
    "assert num_permutation(3,2) == 6\n",
    "assert num_permutation(10,5) == 30240"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Permutation using Iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "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)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:23:15.796091Z",
     "start_time": "2020-11-08T05:23:15.779609Z"
    },
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def permutation_sequence(*a):\n",
    "    '''Returns a generator for the k-permuations of the positional arguments\n",
    "    for k from 0 to len(a).'''\n",
    "    n = len(a)\n",
    "    output, idx_left = [()], [tuple(range(n))]\n",
    "    for k in range(0, n + 1):\n",
    "        yield output\n",
    "        next_output, next_idx_left = [], []\n",
    "        for m in range(len(idx_left)):\n",
    "            for j in range(len(idx_left[m])):\n",
    "                i = idx_left[m][j]\n",
    "                next_output.append(output[m] + (a[i], ))\n",
    "                next_idx_left.append(idx_left[m][:j] + idx_left[m][j + 1:])\n",
    "        output, idx_left = next_output, next_idx_left\n",
    "\n",
    "\n",
    "for permutation_list in permutation_sequence(1, 2, 3):\n",
    "    print(permutation_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:23:15.805651Z",
     "start_time": "2020-11-08T05:23:15.797675Z"
    }
   },
   "outputs": [],
   "source": [
    "a=tuple(range(3))\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Unlike the recursion `permutation`, the above generates a $k$-permutation $(a_{i_0},\\dots,a_{i_{k-1}})$ of $n$ object iteratively by \n",
    "- choosing $i_j$ for $j$ from $0$ to $k-1$ such that\n",
    "- $i_j$ is not already chosen, i.e., $i_j\\not\\in \\{i_0,\\dots,i_{j-1}\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "E.g., the permutations of $1,2,3$ is generated iteratively as follows:\n",
    "- 1\n",
    " - 1,2\n",
    "   - **(1,2,3)**\n",
    " - 1,3\n",
    "   - **(1,3,2)**\n",
    "- 2\n",
    " - 2,1\n",
    "   - **(2,1,3)**\n",
    " - 2,3\n",
    "   - **(2,3,1)**\n",
    "- 3\n",
    " - 3,1\n",
    "   - **(3,1,2)**\n",
    " - 3,2\n",
    "   - **(3,2,1)**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Invariance maintained at the beginning of iteration:**\n",
    "- `output` is the list of $k$-permutations, and\n",
    "- `idx_left[m]` is the list of indices of arguments not yet in `output[m]`. \n",
    "\n",
    "A $(k+1)$-permutation (in `next_output`) can then be generated by (Line 10) appending an argument (with an index from `idx_left`) to a $k$-permutation (in `output`)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Is iteration significantly faster?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:23:16.624234Z",
     "start_time": "2020-11-08T05:23:15.807673Z"
    },
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "n = 9\n",
    "for k, permutation_list in enumerate(permutation_sequence(*range(1,n+1))):\n",
    "    print('# {}-permutations of {} items: {}'.format(k, n, len(permutation_list)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "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:\n",
    "\n",
    "For $k$ from $0$ to $n$,\n",
    "\n",
    "$$\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.}}.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**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`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:23:16.628325Z",
     "start_time": "2020-11-08T05:23:16.625621Z"
    },
    "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": "-"
    }
   },
   "outputs": [],
   "source": [
    "def num_permutation_sequence(n):\n",
    "    output = 1\n",
    "    for k in range(0, n + 1):\n",
    "        # YOUR CODE HERE\n",
    "        raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:23:16.817514Z",
     "start_time": "2020-11-08T05:23:16.629520Z"
    },
    "code_folding": [
     4
    ],
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "c1ad5f69bb41dbbb9e2b180b03fe6424",
     "grade": true,
     "grade_id": "test-num_permutation_sequence",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    },
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "# tests\n",
    "assert [m for m in num_permutation_sequence(3)] == [1, 3, 6, 6]\n",
    "assert [m for m in num_permutation_sequence(10)] == [1, 10, 90, 720, 5040, 30240, 151200, 604800, 1814400, 3628800, 3628800]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Exercise (Challenge)** 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$,\n",
    "\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$$\n",
    "where $\\to$ without labels is the normal transition without calling the `send` method.\n",
    "\n",
    "*Hint:*\n",
    "\n",
    "$$P_{n+1,k}=P_{n,k} \\times \\frac{n+1}{n-k+1}.$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:23:16.831006Z",
     "start_time": "2020-11-08T05:23:16.818789Z"
    },
    "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": "-"
    }
   },
   "outputs": [],
   "source": [
    "def num_permutation_sequence(n):\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:23:16.844281Z",
     "start_time": "2020-11-08T05:23:16.832251Z"
    },
    "code_folding": [],
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ba2e294773c3fb924b4cf8aef6671311",
     "grade": true,
     "grade_id": "test-num_permutation_sequence_send",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    },
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "# tests\n",
    "g = num_permutation_sequence(3)\n",
    "assert (next(g), next(g), g.send(0), next(g), next(g), next(g), g.send(0)) == (1, 3, 4, 12, 24, 24, 120)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Deduplication using Decorator"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "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.,  \n",
    "`permutation(1,1,2)` returns `[(1, 1, 2), (1, 2, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 1, 1)]`  \n",
    "where each distinct permutation appears twice."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "To remove duplicates from a list, we can \n",
    "- convert the list to a `set` (which automatically remove duplicates),\n",
    "- and then convert the set back to a list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:23:16.856904Z",
     "start_time": "2020-11-08T05:23:16.845712Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print('Deduplicated:',list(set(permutation(1,1,2))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Using a decorator, we can fix `permutation` without rewriting the function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:23:16.882201Z",
     "start_time": "2020-11-08T05:23:16.859357Z"
    },
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import functools\n",
    "\n",
    "\n",
    "def deduplicate_output(f):\n",
    "    '''Takes in a function f that returns a list possibly with duplicates,\n",
    "    returns a decorator that remove duplicates from the output list.'''\n",
    "    @functools.wraps(f)\n",
    "    def wrapper(*args, **kwargs):\n",
    "        return list(set(f(*args, **kwargs)))\n",
    "\n",
    "    return wrapper\n",
    "\n",
    "\n",
    "permutation = deduplicate_output(permutation)\n",
    "print('Deduplicated: ', permutation(1, 1, 2))\n",
    "permutation = permutation.__wrapped__\n",
    "print('Original: ', permutation(1, 1, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Exercise:** Create a decorator to eliminate duplicate input positional arguments instead of the ouput, i.e.,  \n",
    "`permutation(1,1,2)` will return the same result as `permutation(1,2)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:23:20.674436Z",
     "start_time": "2020-11-08T05:23:20.668018Z"
    },
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "34f77d1a96354fb05bc0ae0c94e1b48d",
     "grade": false,
     "grade_id": "deduplicate_input",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    },
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def deduplicate_input(f):\n",
    "    '''Takes in a function f that takes a variable number of arguments \n",
    "    possibly with duplicates, returns a decorator that remove duplicates \n",
    "    in the positional argument.'''\n",
    "    @functools.wraps(f)\n",
    "    def wrapper(*args, **kwargs):\n",
    "        # YOUR CODE HERE\n",
    "        raise NotImplementedError()\n",
    "\n",
    "    return wrapper"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-08T05:23:22.747464Z",
     "start_time": "2020-11-08T05:23:22.732090Z"
    },
    "code_folding": [],
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "da5adcc6913f64d54e4c800dcf5654bb",
     "grade": true,
     "grade_id": "test-deduplicate_input",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    },
    "slideshow": {
     "slide_type": "-"
    },
    "solution": "hidden"
   },
   "outputs": [],
   "source": [
    "# tests\n",
    "permutation = deduplicate_input(permutation)\n",
    "assert set(permutation(1,1,2)) == set([(1, 2), (2, 1)])\n",
    "permutation = permutation.__wrapped__"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.7",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
