{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "ca0a7e25",
   "metadata": {
    "deletable": false,
    "editable": false,
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Initialization cell\n",
    "try:  # for CS1302 JupyterLite pyodide kernel\n",
    "    import piplite\n",
    "\n",
    "    with open(\"requirements.txt\") as f:\n",
    "        for package in f:\n",
    "            package = package.strip()\n",
    "            print(\"Installing\", package)\n",
    "            await piplite.install(package)\n",
    "except ModuleNotFoundError:\n",
    "    pass\n",
    "\n",
    "import random\n",
    "import jupytext\n",
    "import otter\n",
    "from ipywidgets import interact\n",
    "\n",
    "grader = otter.Notebook(\"main.ipynb\")\n",
    "%reload_ext divewidgets"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2fac27eb",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e781f84",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    },
    "tags": [
     "remove-cell"
    ]
   },
   "source": [
    "**CS1302 Introduction to Computer Programming**\n",
    "___"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "366a4303",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Permutation using recursion"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "714ccf95",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "---\n",
    "\n",
    "**Definition**\n",
    "\n",
    "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 called a permutation of $n$ objects.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3daceb51",
   "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,
   "id": "7cd10a14",
   "metadata": {
    "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",
   "id": "1581580c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- The list of $2$-permutations of `1,2,3` is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c938725b",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "202bba77",
   "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",
   "id": "f82e1fc9",
   "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",
   "id": "d8f9a59f",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "---\n",
    "\n",
    "**Proposition**\n",
    "\n",
    "A $k$-permutation of $n$ satisfies the recurrence relation:  \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",
    "\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$.} }]$$\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1338df1e",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The following implements the recursion:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "id": "60b829d5",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]\n",
      "[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]\n"
     ]
    }
   ],
   "source": [
    "def permutation(*a, k=None):\n",
    "    \"\"\"Construct all (k-)permutations of the position arguments.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    *a: object, object, ...\n",
    "        n items specified as positional arguments\n",
    "    k: int\n",
    "        Optional argument indicating the size of each permutation. \n",
    "        Default: number n of items specified in *a.\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    list:\n",
    "        List of all k-permutations represented as ordered tuples of the n objects.\n",
    "    \"\"\"\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(\n",
    "                [(a[i],) + p for p in permutation(*a[:i], *a[i + 1 :], k=k - 1)]\n",
    "            )\n",
    "    elif k == 0:\n",
    "        return [()]\n",
    "    return output\n",
    "\n",
    "\n",
    "print(permutation(1, 2, 3))\n",
    "print(permutation(1, 2, 3, k=2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76880935",
   "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",
   "id": "9f2d736c",
   "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",
   "id": "dcdc0836",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "```{note}\n",
    "\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.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef0d6f02",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Exercise** (base)\n",
    "\n",
    "One of the base cases of the recursion 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",
   "id": "3227ddd5",
   "metadata": {},
   "source": [
    "When value of k is equal to n, the function returns as same value when k is none."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3855a37",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Number of permutations"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d3cdcea",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Computing permutations using recursion is slow. Why?  \n",
    "\n",
    "There are too many permutations, even for a reasonably small $n$. Try running the following code in a new console:\n",
    "\n",
    "```python\n",
    "n = 10\n",
    "output = permutation(*range(1, n + 1))\n",
    "print(f\"# {n}-permutations:\", len(output))\n",
    "```\n",
    "\n",
    "```{caution}\n",
    "Avoid creating a new cell to run the above code because auto-grader may refuse to execute code that takes too long to run. To open a new console, right-click anywhere and select `New Console for Notebook`.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0cbc3770",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Quite surprisingly, the number of permutations can be calculated significantly faster without enumerating all the permutations."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7110dc46",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "**Proposition**\n",
    "\n",
    "The number $P_n$ of ($n-$)permutations of $n$ items 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",
    "$$ (Pn)\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a139fe4",
   "metadata": {},
   "source": [
    "The quantity is fundamental in the field of [combinatorics](https://en.wikipedia.org/wiki/Combinatorics) with enormous applications."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b80edd12",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Exercise** (num-permutation)\n",
    "\n",
    "Implement the above recurrence equation."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b883ba1",
   "metadata": {},
   "source": [
    "```{hint}\n",
    "\n",
    "Ensure all base cases are covered, and the code can run efficiently for large $n$.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "ec521d38",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "num_permutations",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    },
    "slideshow": {
     "slide_type": "-"
    },
    "tags": [
     "remove-output"
    ]
   },
   "outputs": [],
   "source": [
    "from math import factorial\n",
    "def num_permutation_v1(n):\n",
    "    \"\"\"Compute the number of permutations.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    n: int\n",
    "        Number of items.\n",
    "\n",
    "    Return\n",
    "    ------\n",
    "    int:\n",
    "        Number of permutations of n items.\n",
    "    \"\"\"\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    elif n > 0:\n",
    "        return factorial(n)\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "cb54d402",
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p><strong><pre style='display: inline;'>num-permutation</pre></strong> passed!</p>"
      ],
      "text/plain": [
       "num-permutation results: All test cases passed!"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grader.check(\"num-permutation\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42d1408e",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "**Proposition**\n",
    "\n",
    "The number $P_{n,k}$ of $k$-permutations of $n$ items is given by the formula\n",
    "\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}\n",
    "$$ (Pnk)\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "95af1647",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Exercise** (optional-argument)\n",
    "\n",
    "Extend the function `num_permutation_v1` to `num_permutation_v2` to allow for a optional argument `k`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "f88a37ae",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "num_permutation_k",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    },
    "tags": [
     "remove-output"
    ]
   },
   "outputs": [],
   "source": [
    "from math import factorial\n",
    "def num_permutation_v2(n, k=None):\n",
    "    \"\"\"Compute the number of k-permutations of n items.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    n: int\n",
    "        Number of items to permute.\n",
    "    k: int\n",
    "        Optional argument indicating the size of each permutation.\n",
    "        Default: n\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    int:\n",
    "        Number of k-permutations of n items.\n",
    "    \"\"\"\n",
    "    if k == None:\n",
    "        return factorial(n)\n",
    "    elif 0 <= k <= n:\n",
    "        return factorial(n)/factorial(n-k)\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "e2bb0884",
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p><strong><pre style='display: inline;'>optional-argument</pre></strong> passed!</p>"
      ],
      "text/plain": [
       "optional-argument results: All test cases passed!"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grader.check(\"optional-argument\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6602415",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Permutation using iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02d75363",
   "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": 15,
   "id": "6c34e777",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[()]\n",
      "[(1,), (2,), (3,)]\n",
      "[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]\n",
      "[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]\n"
     ]
    }
   ],
   "source": [
    "def permutation_sequence(*a):\n",
    "    \"\"\"Returns a generator for the k-permutations 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(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": "markdown",
   "id": "a86a08c6",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Unlike the recursive function `permutation`, the above generates a $k$-permutation $(a_{i_0},\\dots,a_{i_{k-1}})$ of $n$ items 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",
   "id": "20afc527",
   "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",
   "id": "e892ed2b",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "---\n",
    "\n",
    "**Proposition**\n",
    "\n",
    "`permutation_sequence` maintains the following *invariance* at the beginning of each 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 appending an argument (with an index from `idx_left`) to a $k$-permutation (in `output`).\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98772dac",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Is iteration significantly faster?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf988abc",
   "metadata": {},
   "source": [
    "Try running the following code in a new console:\n",
    "\n",
    "```python\n",
    "n = 10\n",
    "for k, permutation_list in enumerate(permutation_sequence(*range(1, n + 1))):\n",
    "    print(\"# {}-permutations of {} items: {}\".format(k, n, len(permutation_list)))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "238c5de8",
   "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.}}.$$ (Pnk:expanded)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d4902ea6",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Exercise** (yield)\n",
    "\n",
    "Use the `yield` statement to write the function `num_permutation_sequence_v1(n)` that returns a generator of $P_{n,k}$ with `k` from `0` to `n`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "f4e5ed4a",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "num_permutation_sequence_v1",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    },
    "slideshow": {
     "slide_type": "-"
    },
    "tags": [
     "remove-output"
    ]
   },
   "outputs": [],
   "source": [
    "from math import factorial\n",
    "def num_permutation_sequence_v1(n):\n",
    "    for k in range(0, n + 1):\n",
    "        yield factorial(n)/factorial(n-k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "06a88c27",
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p><strong><pre style='display: inline;'>yield</pre></strong> passed!</p>"
      ],
      "text/plain": [
       "yield results: All test cases passed!"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grader.check(\"yield\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c0d6923",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Exercise** (send)\n",
    "\n",
    "Extend the function `num_permutation_sequence_v1(n)` to `num_permutation_sequence_v2(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."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c3a2604",
   "metadata": {},
   "source": [
    "```{hint}\n",
    "\n",
    "By {eq}`Pnk:expanded`,\n",
    "\n",
    "$$P_{n+1,k}=P_{n,k} \\times \\frac{n+1}{n-k+1}.$$\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "05a03548",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "num_permutation_sequence_v2_send",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    },
    "slideshow": {
     "slide_type": "-"
    },
    "tags": [
     "remove-output"
    ]
   },
   "outputs": [],
   "source": [
    "from math import factorial\n",
    "def num_permutation_sequence_v2(n,k=-1, output=1):\n",
    "    while True and k <= n:\n",
    "        if output != 0:\n",
    "            k += 1\n",
    "            output = factorial(n)/factorial(n-k)\n",
    "            output = yield output\n",
    "        else:\n",
    "            n += 1\n",
    "            output = factorial(n)/factorial(n-k)\n",
    "            output = yield output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "d6bd4830",
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p><strong><pre style='display: inline;'>send</pre></strong> passed!</p>"
      ],
      "text/plain": [
       "send results: All test cases passed!"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grader.check(\"send\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c6c1df3",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Deduplication using Decorator"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b24373bf",
   "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",
   "id": "d2f89552",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "To remove duplicates from a list, we can  \n",
    "- convert the list to a `set` (which automatically removes duplicates),\n",
    "- and then convert the set back to a list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "e0964b1a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Deduplicated: [(1, 2, 1), (2, 1, 1), (1, 1, 2)]\n"
     ]
    }
   ],
   "source": [
    "print(\"Deduplicated:\", list(set(permutation(1, 1, 2))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9018f18e",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Using a decorator, we can fix `permutation` without rewriting the function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "1fe578e2",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Deduplicated:  [(1, 2, 1), (2, 1, 1), (1, 1, 2)]\n",
      "Original:  [(1, 1, 2), (1, 2, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 1, 1)]\n"
     ]
    }
   ],
   "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 removes duplicates from the output list.\"\"\"\n",
    "\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",
   "id": "b1eb7d5a",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Exercise** (deduplicate-input)\n",
    "\n",
    "Create a decorator to eliminate duplicate input positional arguments instead of the output, i.e.,  \n",
    "`permutation(1,1,2)` will return the same result as `permutation(1,2)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "id": "fdc7d452",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "deduplicate_input",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    },
    "slideshow": {
     "slide_type": "-"
    },
    "tags": [
     "remove-output"
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Deduplicated:  [(1, 2), (2, 1)]\n"
     ]
    }
   ],
   "source": [
    "import functools\n",
    "from collections import OrderedDict\n",
    "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 removes duplicates\n",
    "    in the positional argument.\"\"\"\n",
    "    @functools.wraps(f)\n",
    "    def wrapper(*args, **kwargs):\n",
    "        k=list(set(f(*args, **kwargs)))\n",
    "        for n in range(len(k)):\n",
    "            k[n]= tuple(OrderedDict.fromkeys(k[n]).keys())\n",
    "        return list(set(k))\n",
    "    return wrapper"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "id": "85b9f032",
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p><strong><pre style='display: inline;'>deduplicate-input</pre></strong> passed!</p>"
      ],
      "text/plain": [
       "deduplicate-input results: All test cases passed!"
      ]
     },
     "execution_count": 148,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grader.check(\"deduplicate-input\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b38ebb9",
   "metadata": {
    "editable": false,
    "tags": [
     "remove-cell"
    ]
   },
   "source": [
    "## Submission\n",
    "\n",
    "Make sure you have run all cells in your notebook in order before running the cell below, so that all images/graphs appear in the output. The cell below will generate a zip file for you to submit. **Please save before exporting!**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "id": "6bd9f99b",
   "metadata": {
    "deletable": false,
    "editable": true,
    "tags": []
   },
   "outputs": [],
   "source": [
    "# extra files to submit\n",
    "extra_files = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "id": "b327c256",
   "metadata": {
    "deletable": false,
    "editable": false,
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Generate the source main.py necessary for grading and similarity check.\n",
    "jupytext.write(jupytext.read(\"main.ipynb\"), \"main.py\", fmt=\"py:percent\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "id": "5e6e7d8b",
   "metadata": {
    "deletable": false,
    "editable": false,
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "            <p>Your submission has been exported. Click <a href=\"main_2022_11_07T15_32_16_756830.zip\" download=\"main_2022_11_07T15_32_16_756830.zip\" target=\"_blank\">here</a>\n",
       "            to download the zip file.</p>\n",
       "            "
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Generate the zip file to submit.\n",
    "grader.export(pdf=False, run_tests=False, files=[\"main.py\", *extra_files])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1d1d7c63-da1b-41c1-bd37-43d3dc3dc430",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "58a9caee-976e-49f5-95e5-1be8986b5a79",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.6"
  },
  "otter": {
   "OK_FORMAT": true,
   "tests": {
    "deduplicate-input": {
     "name": "deduplicate-input",
     "points": null,
     "suites": [
      {
       "cases": [
        {
         "code": ">>> # tests\n>>> permutation = deduplicate_input(permutation)\n>>> try:\n...     assert set(permutation(1, 1, 2)) == set([(1, 2), (2, 1)])\n... finally:\n...     permutation = permutation.__wrapped__\n",
         "hidden": false,
         "locked": false
        }
       ],
       "scored": true,
       "setup": "",
       "teardown": "",
       "type": "doctest"
      }
     ]
    },
    "num-permutation": {
     "name": "num-permutation",
     "points": null,
     "suites": [
      {
       "cases": [
        {
         "code": ">>> # tests\n>>> assert num_permutation_v1(10) == 3628800\n>>> assert num_permutation_v1(0) == 1\n>>> assert num_permutation_v1(-1) == 0\n",
         "hidden": false,
         "locked": false
        }
       ],
       "scored": true,
       "setup": "",
       "teardown": "",
       "type": "doctest"
      }
     ]
    },
    "optional-argument": {
     "name": "optional-argument",
     "points": null,
     "suites": [
      {
       "cases": [
        {
         "code": ">>> # tests\n>>> assert isinstance(num_permutation_v2(0), int)\n>>> assert num_permutation_v2(3) == 6\n>>> assert num_permutation_v2(3, 0) == 1\n>>> assert num_permutation_v2(3, 2) == 6\n>>> assert num_permutation_v2(10, 5) == 30240\n",
         "hidden": false,
         "locked": false
        }
       ],
       "scored": true,
       "setup": "",
       "teardown": "",
       "type": "doctest"
      }
     ]
    },
    "send": {
     "name": "send",
     "points": null,
     "suites": [
      {
       "cases": [
        {
         "code": ">>> # tests\n>>> g = num_permutation_sequence_v2(3)\n>>> assert (next(g), next(g), g.send(0), next(g), next(g), next(g), g.send(0)) == (\n...     1,\n...     3,\n...     4,\n...     12,\n...     24,\n...     24,\n...     120)\n",
         "hidden": false,
         "locked": false
        }
       ],
       "scored": true,
       "setup": "",
       "teardown": "",
       "type": "doctest"
      }
     ]
    },
    "yield": {
     "name": "yield",
     "points": null,
     "suites": [
      {
       "cases": [
        {
         "code": ">>> # tests\n>>> assert [m for m in num_permutation_sequence_v1(3)] == [1, 3, 6, 6]\n>>> assert [m for m in num_permutation_sequence_v1(10)] == [\n...     1,\n...     10,\n...     90,\n...     720,\n...     5040,\n...     30240,\n...     151200,\n...     604800,\n...     1814400,\n...     3628800,\n...     3628800]\n",
         "hidden": false,
         "locked": false
        }
       ],
       "scored": true,
       "setup": "",
       "teardown": "",
       "type": "doctest"
      }
     ]
    }
   }
  },
  "widgets": {
   "application/vnd.jupyter.widget-state+json": {
    "state": {},
    "version_major": 2,
    "version_minor": 0
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}