{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "90fffcef",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20feb551",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    },
    "tags": [
     "remove-cell"
    ]
   },
   "source": [
    "**CS1302 Introduction to Computer Programming**\n",
    "___"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d734e490",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Permutation using Recursion"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e61b7fbb",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "````{prf: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 simply called a permutation of $n$ objects.\n",
    "\n",
    "````"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3ef4e38",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "For examples:\n",
    "- The list of ($3$-)permutations of `1,2,3` is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "384fe74d",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "442e6551",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- The list of $2$-permutations of `1,2,3` is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d7a5a6d4",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5317ddb9",
   "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": "e7f08aa3",
   "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": "1f3921f5",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "````{prf: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": "22de721a",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The following implements the recursion:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "420c709b",
   "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": "41296102",
   "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": "02024289",
   "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": "0b498396",
   "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": "6d7bafce",
   "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",
   "id": "a252c258",
   "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",
   "id": "4e51cb65",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Number of permutations"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b35f2193",
   "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": 4,
   "id": "d976b07c",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    },
    "tags": [
     "remove-output"
    ]
   },
   "outputs": [
    {
     "ename": "StdinNotImplementedError",
     "evalue": "raw_input was called, but this frontend does not support input requests.",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mStdinNotImplementedError\u001b[0m                  Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-4-d98f382687d9>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;32mif\u001b[0m \u001b[0minput\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Run? [Y/n]\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlower\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0;34m\"n\"\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      2\u001b[0m     \u001b[0mn\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m10\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0moutput\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mpermutation\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"# permutations:\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0moutput\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/my-conda-envs/jb/lib/python3.8/site-packages/ipykernel/kernelbase.py\u001b[0m in \u001b[0;36mraw_input\u001b[0;34m(self, prompt)\u001b[0m\n\u001b[1;32m    843\u001b[0m         \"\"\"\n\u001b[1;32m    844\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_allow_stdin\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 845\u001b[0;31m             raise StdinNotImplementedError(\n\u001b[0m\u001b[1;32m    846\u001b[0m                 \u001b[0;34m\"raw_input was called, but this frontend does not support input requests.\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    847\u001b[0m             )\n",
      "\u001b[0;31mStdinNotImplementedError\u001b[0m: raw_input was called, but this frontend does not support input requests."
     ]
    }
   ],
   "source": [
    "if input(\"Run? [Y/n]\").lower() != \"n\":\n",
    "    n = 10\n",
    "    output = permutation(*range(1, n + 1))\n",
    "    print(\"# permutations:\", len(output))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "876b5ae8",
   "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": "18c7dfeb",
   "metadata": {},
   "source": [
    "````{prf: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": "ff3dc7b6",
   "metadata": {},
   "source": [
    "This quantity is fundamental in the field of [combinatorics](https://en.wikipedia.org/wiki/Combinatorics) with enormous applications."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ca994cd",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Exercise** Implement the above recurrence equation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "0ac4ad07",
   "metadata": {
    "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"
    ]
   },
   "outputs": [],
   "source": [
    "def num_permutation(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",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d40ea33",
   "metadata": {},
   "source": [
    "````{hint}\n",
    "\n",
    "Ensure all base cases are covered, and can run efficiently for large $n$.\n",
    "\n",
    "````"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "ac59b04b",
   "metadata": {
    "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"
    ]
   },
   "outputs": [
    {
     "ename": "NotImplementedError",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNotImplementedError\u001b[0m                       Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-6-369cc05bef6b>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m# tests\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0mnum_permutation\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m10\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m3628800\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      3\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0mnum_permutation\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0mnum_permutation\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-5-37d13176d58e>\u001b[0m in \u001b[0;36mnum_permutation\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m     13\u001b[0m     \"\"\"\n\u001b[1;32m     14\u001b[0m     \u001b[0;31m# YOUR CODE HERE\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m     \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNotImplementedError\u001b[0m: "
     ]
    }
   ],
   "source": [
    "# tests\n",
    "assert num_permutation(10) == 3628800\n",
    "assert num_permutation(0) == 1\n",
    "assert num_permutation(-1) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "f16f79d4",
   "metadata": {
    "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"
    ]
   },
   "outputs": [],
   "source": [
    "# hidden tests"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66cf96a1",
   "metadata": {},
   "source": [
    "````{prf: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": "90f4377d",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Exercise** Extend the function `num_permutation` to allow for a optional argument `k`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "07e59f2d",
   "metadata": {
    "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"
    ]
   },
   "outputs": [],
   "source": [
    "def num_permutation(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",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "cb6c1a46",
   "metadata": {
    "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"
    ]
   },
   "outputs": [
    {
     "ename": "NotImplementedError",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNotImplementedError\u001b[0m                       Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-9-5ab46554ecb4>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m# tests\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0misinstance\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnum_permutation\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      3\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0mnum_permutation\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m6\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0mnum_permutation\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0mnum_permutation\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m6\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-8-b1c65a21f136>\u001b[0m in \u001b[0;36mnum_permutation\u001b[0;34m(n, k)\u001b[0m\n\u001b[1;32m     16\u001b[0m     \"\"\"\n\u001b[1;32m     17\u001b[0m     \u001b[0;31m# YOUR CODE HERE\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 18\u001b[0;31m     \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNotImplementedError\u001b[0m: "
     ]
    }
   ],
   "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": "code",
   "execution_count": 10,
   "id": "925207ea",
   "metadata": {
    "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"
    ]
   },
   "outputs": [],
   "source": [
    "# hidden tests"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6e88b23",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Permutation using Iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b7eceacd",
   "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": 11,
   "id": "93f6b067",
   "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-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(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": "ee88a7e9",
   "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": "ccbf8ca3",
   "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": "819bb479",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "````{prf: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": "052136e8",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Is iteration significantly faster?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "1b797ec8",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    },
    "tags": [
     "remove-output"
    ]
   },
   "outputs": [
    {
     "ename": "StdinNotImplementedError",
     "evalue": "raw_input was called, but this frontend does not support input requests.",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mStdinNotImplementedError\u001b[0m                  Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-12-87524c36f0c0>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;32mif\u001b[0m \u001b[0minput\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Run? [Y/n]\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlower\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0;34m\"n\"\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      2\u001b[0m     \u001b[0mn\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m10\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0;32mfor\u001b[0m \u001b[0mk\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mpermutation_list\u001b[0m \u001b[0;32min\u001b[0m \u001b[0menumerate\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpermutation_sequence\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m         \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"# {}-permutations of {} items: {}\"\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpermutation_list\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/my-conda-envs/jb/lib/python3.8/site-packages/ipykernel/kernelbase.py\u001b[0m in \u001b[0;36mraw_input\u001b[0;34m(self, prompt)\u001b[0m\n\u001b[1;32m    843\u001b[0m         \"\"\"\n\u001b[1;32m    844\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_allow_stdin\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 845\u001b[0;31m             raise StdinNotImplementedError(\n\u001b[0m\u001b[1;32m    846\u001b[0m                 \u001b[0;34m\"raw_input was called, but this frontend does not support input requests.\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    847\u001b[0m             )\n",
      "\u001b[0;31mStdinNotImplementedError\u001b[0m: raw_input was called, but this frontend does not support input requests."
     ]
    }
   ],
   "source": [
    "if input(\"Run? [Y/n]\").lower() != \"n\":\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)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fcfc7e46",
   "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": "b7a7eaef",
   "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": 13,
   "id": "800ec67d",
   "metadata": {
    "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"
    ]
   },
   "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": 14,
   "id": "b4e66bf3",
   "metadata": {
    "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"
    ]
   },
   "outputs": [
    {
     "ename": "NotImplementedError",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNotImplementedError\u001b[0m                       Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-14-7434d08e1512>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m# tests\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mm\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mm\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mnum_permutation_sequence\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m3\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m6\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m6\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      3\u001b[0m assert [m for m in num_permutation_sequence(10)] == [\n\u001b[1;32m      4\u001b[0m     \u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m     \u001b[0;36m10\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-13-faee169f9f62>\u001b[0m in \u001b[0;36mnum_permutation_sequence\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0;32mfor\u001b[0m \u001b[0mk\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m         \u001b[0;31m# YOUR CODE HERE\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m         \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNotImplementedError\u001b[0m: "
     ]
    }
   ],
   "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)] == [\n",
    "    1,\n",
    "    10,\n",
    "    90,\n",
    "    720,\n",
    "    5040,\n",
    "    30240,\n",
    "    151200,\n",
    "    604800,\n",
    "    1814400,\n",
    "    3628800,\n",
    "    3628800,\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "724ea58d",
   "metadata": {
    "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"
    ]
   },
   "outputs": [],
   "source": [
    "# hidden tests"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7437a5a2",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**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$,\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": "code",
   "execution_count": 16,
   "id": "6272963e",
   "metadata": {
    "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"
    ]
   },
   "outputs": [],
   "source": [
    "def num_permutation_sequence(n):\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5ab23dd",
   "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": 17,
   "id": "c81b9758",
   "metadata": {
    "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"
    ]
   },
   "outputs": [
    {
     "ename": "NotImplementedError",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNotImplementedError\u001b[0m                       Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-17-8e0189c8ff84>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m# tests\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mg\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mnum_permutation_sequence\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      3\u001b[0m assert (next(g), next(g), g.send(0), next(g), next(g), next(g), g.send(0)) == (\n\u001b[1;32m      4\u001b[0m     \u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m     \u001b[0;36m3\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-16-85a3d3ee48c4>\u001b[0m in \u001b[0;36mnum_permutation_sequence\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mnum_permutation_sequence\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m     \u001b[0;31m# YOUR CODE HERE\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m     \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNotImplementedError\u001b[0m: "
     ]
    }
   ],
   "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)) == (\n",
    "    1,\n",
    "    3,\n",
    "    4,\n",
    "    12,\n",
    "    24,\n",
    "    24,\n",
    "    120,\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "bd8d04af",
   "metadata": {
    "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"
    ]
   },
   "outputs": [],
   "source": [
    "# hidden tests"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4029fa4c",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Deduplication using Decorator"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ff0c7e1",
   "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": "e3d415ad",
   "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": 19,
   "id": "c1f7aac7",
   "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": "2276628b",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Using a decorator, we can fix `permutation` without rewriting the function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "0cd35d8c",
   "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 remove 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": "a6d8817e",
   "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": 21,
   "id": "358d6396",
   "metadata": {
    "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"
    ]
   },
   "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",
    "\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": 22,
   "id": "cc49a03c",
   "metadata": {
    "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"
    ]
   },
   "outputs": [
    {
     "ename": "NotImplementedError",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNotImplementedError\u001b[0m                       Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-22-90839b70afce>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0mpermutation\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdeduplicate_input\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpermutation\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m     \u001b[0;32massert\u001b[0m \u001b[0mset\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpermutation\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0mset\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      5\u001b[0m \u001b[0;32mfinally\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m     \u001b[0mpermutation\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mpermutation\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__wrapped__\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-21-f35f63bb5cf8>\u001b[0m in \u001b[0;36mwrapper\u001b[0;34m(*args, **kwargs)\u001b[0m\n\u001b[1;32m      7\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mwrapper\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0margs\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m**\u001b[0m\u001b[0mkwargs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      8\u001b[0m         \u001b[0;31m# YOUR CODE HERE\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 9\u001b[0;31m         \u001b[0;32mraise\u001b[0m \u001b[0mNotImplementedError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m     \u001b[0;32mreturn\u001b[0m \u001b[0mwrapper\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mNotImplementedError\u001b[0m: "
     ]
    }
   ],
   "source": [
    "# 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__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "8ee8bb29",
   "metadata": {
    "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"
    ]
   },
   "outputs": [],
   "source": [
    "# hidden tests"
   ]
  }
 ],
 "metadata": {
  "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"
  },
  "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.8.8"
  },
  "source_map": [
   14,
   18,
   23,
   27,
   40,
   45,
   53,
   57,
   65,
   71,
   76,
   92,
   96,
   135,
   146,
   154,
   165,
   169,
   173,
   177,
   182,
   194,
   198,
   214,
   218,
   222,
   253,
   261,
   286,
   304,
   319,
   323,
   357,
   382,
   402,
   406,
   410,
   435,
   441,
   460,
   472,
   476,
   488,
   497,
   501,
   524,
   560,
   579,
   586,
   605,
   615,
   647,
   666,
   670,
   676,
   682,
   690,
   694,
   719,
   724,
   753,
   781
  ]
 },
 "nbformat": 4,
 "nbformat_minor": 5
}