Colab_Codes/chapter_combinatorial_search.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "chapter_combinatorial_search.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZhL7pFlp8gTD",
        "colab_type": "text"
      },
      "source": [
        "## Backtracking\n",
        "\n",
        "1.   Permutation\n",
        "2.   Combination\n",
        "3.    All Paths\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "I7Xx9UKaXO7e",
        "colab_type": "text"
      },
      "source": [
        "### Template"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JZvh1XD8XQYN",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def backtrack():\n",
        "  # initialization\n",
        "  A #a working data structure, either a list of candidates or a graph or a matrix representing a board\n",
        "  state_tracker = []*n\n",
        "  assist_state_tracker\n",
        "  # main backtracking\n",
        "  def dfs(d, n):\n",
        "    '''d: depth representing level in the tree'''\n",
        "    if d == n:\n",
        "      return\n",
        "    candidates = generate_candidates(state_tracker, assist_state_tracker)\n",
        "    for c in candidates: \n",
        "      set_state(state_tracker, assist_state_tracker, c)\n",
        "      dfs(d+1, n)\n",
        "      reset_state(state_tracler, assist_state_tracker, c)\n",
        "      \n",
        "  dfs(0, n)\n",
        "      "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xGT9qW47yghc",
        "colab_type": "text"
      },
      "source": [
        "### Permutations\n",
        "How many ways to permutate an $n$-set? For example {1, 2, 3}: ???\n",
        "* Enumerate by position This helps us to enumerate permuation with **backtracking**\n",
        "```\n",
        "{}\n",
        "i=0: {1}, {2}, {3}\n",
        "i=1: {1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3,2}\n",
        "i=2: {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}.\n",
        "```\n",
        "The recurrence relation is:\n",
        "\\begin{align}\n",
        "d(i) = (n-i)*d(i-1)\n",
        "\\end{align}\n",
        "Such that\n",
        "```\n",
        "d(0) = 3 * 1 = 3\n",
        "d(1) = 2 * 3 = 6\n",
        "d(2) = 1 * 6 = 6\n",
        "```\n",
        "*  Additionally, can enumerate by iterating elements, and then enumerate all possible positions that it can go.\n",
        "```\n",
        ": {}\n",
        "1: {1}\n",
        "2: {1, 2}, {2, 1} : can find i position to insert 2\n",
        "3: {3, 1, 2}, {1, 3, 2}, {1, 2, 3}| {3, 2, 1}, {2, 3, 1}, {2, 1, 3}\n",
        "```\n",
        "\\begin{align}\n",
        "d(i) = i*d(i-1)\n",
        "\\end{align}\n",
        "Such that:\n",
        "```\n",
        "d(0) = 1 * 1 = 1\n",
        "d(1) = 2 * 1 = 2\n",
        "d(2) = 3 * 2 = 6\n",
        "```\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UJWteGFF6dSI",
        "colab_type": "code",
        "outputId": "023cb8ca-329e-46e7-c39e-34745b79c3c0",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 367
        }
      },
      "source": [
        "from graphviz import Digraph\n",
        "dot = Digraph(comment='The Round Table', format='png')\n",
        "dot.node_attr['shape']='box'\n",
        "#print(get_methods(Digraph))\n",
        "#print(Digraph.__dict__)\n",
        "nodes = ['[]', '[1]', '[2]', '[3]', '[1, 2]', '[1, 3]', '[2, 1]', '[2, 3]', '[3, 1]', '[3, 2]', '[1, 2, 3]', '[1, 3, 2]', '[2, 1, 3]', '[2, 3, 1]', '[3, 1, 2]', '[3, 2, 1]']\n",
        "for i, node in enumerate(nodes):\n",
        "  dot.node(str(i), label=node)\n",
        "edges = [('0', '1'), ('0', '2'), ('0', '3'), ('1', '4'), ('1', '5'), ('2', '6'), ('2', '7'), ('3', '8'), ('3', '9'), ('4', '10'), ('5', '11'), ('6', '12'), ('7', '13'), ('8', '14'), ('9', '15')]\n",
        "for n1, n2 in edges:\n",
        "  dot.edge(n1, n2)\n",
        "# dot.edge('0', '1', _attributes={'label': '4'})\n",
        "# dot.edge('S', 'B', _attributes={'label': '5'})\n",
        "# dot.edge('A', 'G', _attributes={'label': '7'})\n",
        "# dot.edge('B', 'G', _attributes={'label': '3'})\n",
        "dot.render('test-output/permutation', view=True) \n",
        "\n",
        "dot"
      ],
      "execution_count": 145,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7fac751a5f28>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: %3 Pages: 1 -->\n<svg width=\"476pt\" height=\"260pt\"\n viewBox=\"0.00 0.00 476.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\n<title>%3</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-256 472,-256 472,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"257.5,-252 203.5,-252 203.5,-216 257.5,-216 257.5,-252\"/>\n<text text-anchor=\"middle\" x=\"230.5\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[]</text>\n</g>\n<!-- 1 -->\n<g id=\"node2\" class=\"node\">\n<title>1</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"139.5,-180 85.5,-180 85.5,-144 139.5,-144 139.5,-180\"/>\n<text text-anchor=\"middle\" x=\"112.5\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1]</text>\n</g>\n<!-- 0&#45;&gt;1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M203.4284,-217.4817C187.2046,-207.5825 166.3715,-194.8707 148.7407,-184.113\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"150.2137,-180.9117 139.8542,-178.6907 146.5676,-186.8872 150.2137,-180.9117\"/>\n</g>\n<!-- 2 -->\n<g id=\"node3\" class=\"node\">\n<title>2</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"257.5,-180 203.5,-180 203.5,-144 257.5,-144 257.5,-180\"/>\n<text text-anchor=\"middle\" x=\"230.5\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2]</text>\n</g>\n<!-- 0&#45;&gt;2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>0&#45;&gt;2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M230.5,-215.8314C230.5,-208.131 230.5,-198.9743 230.5,-190.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"234.0001,-190.4132 230.5,-180.4133 227.0001,-190.4133 234.0001,-190.4132\"/>\n</g>\n<!-- 3 -->\n<g id=\"node4\" class=\"node\">\n<title>3</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"382.5,-180 328.5,-180 328.5,-144 382.5,-144 382.5,-180\"/>\n<text text-anchor=\"middle\" x=\"355.5\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3]</text>\n</g>\n<!-- 0&#45;&gt;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>0&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M257.6231,-218.3771C275.8052,-207.9042 299.9431,-194.0007 319.6985,-182.6216\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"321.5114,-185.6166 328.4298,-177.5924 318.0175,-179.5508 321.5114,-185.6166\"/>\n</g>\n<!-- 4 -->\n<g id=\"node5\" class=\"node\">\n<title>4</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"62.5,-108 8.5,-108 8.5,-72 62.5,-72 62.5,-108\"/>\n<text text-anchor=\"middle\" x=\"35.5\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 2]</text>\n</g>\n<!-- 1&#45;&gt;4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>1&#45;&gt;4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M93.0696,-143.8314C83.768,-135.1337 72.4796,-124.5783 62.3714,-115.1265\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"64.6189,-112.4363 54.9241,-108.1628 59.8379,-117.5493 64.6189,-112.4363\"/>\n</g>\n<!-- 5 -->\n<g id=\"node6\" class=\"node\">\n<title>5</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"139.5,-108 85.5,-108 85.5,-72 139.5,-72 139.5,-108\"/>\n<text text-anchor=\"middle\" x=\"112.5\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 3]</text>\n</g>\n<!-- 1&#45;&gt;5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>1&#45;&gt;5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M112.5,-143.8314C112.5,-136.131 112.5,-126.9743 112.5,-118.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"116.0001,-118.4132 112.5,-108.4133 109.0001,-118.4133 116.0001,-118.4132\"/>\n</g>\n<!-- 6 -->\n<g id=\"node7\" class=\"node\">\n<title>6</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"222.5,-108 168.5,-108 168.5,-72 222.5,-72 222.5,-108\"/>\n<text text-anchor=\"middle\" x=\"195.5\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 1]</text>\n</g>\n<!-- 2&#45;&gt;6 -->\n<g id=\"edge6\" class=\"edge\">\n<title>2&#45;&gt;6</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M221.668,-143.8314C217.8014,-135.8771 213.1794,-126.369 208.9032,-117.5723\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"211.9707,-115.8768 204.4509,-108.4133 205.6751,-118.9371 211.9707,-115.8768\"/>\n</g>\n<!-- 7 -->\n<g id=\"node8\" class=\"node\">\n<title>7</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"297.5,-108 243.5,-108 243.5,-72 297.5,-72 297.5,-108\"/>\n<text text-anchor=\"middle\" x=\"270.5\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 3]</text>\n</g>\n<!-- 2&#45;&gt;7 -->\n<g id=\"edge7\" class=\"edge\">\n<title>2&#45;&gt;7</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M240.5937,-143.8314C245.0597,-135.7925 250.4075,-126.1666 255.3379,-117.2918\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"258.4735,-118.8546 260.2704,-108.4133 252.3544,-115.4551 258.4735,-118.8546\"/>\n</g>\n<!-- 8 -->\n<g id=\"node9\" class=\"node\">\n<title>8</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"382.5,-108 328.5,-108 328.5,-72 382.5,-72 382.5,-108\"/>\n<text text-anchor=\"middle\" x=\"355.5\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 1]</text>\n</g>\n<!-- 3&#45;&gt;8 -->\n<g id=\"edge8\" class=\"edge\">\n<title>3&#45;&gt;8</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M355.5,-143.8314C355.5,-136.131 355.5,-126.9743 355.5,-118.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"359.0001,-118.4132 355.5,-108.4133 352.0001,-118.4133 359.0001,-118.4132\"/>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"458.5,-108 404.5,-108 404.5,-72 458.5,-72 458.5,-108\"/>\n<text text-anchor=\"middle\" x=\"431.5\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 2]</text>\n</g>\n<!-- 3&#45;&gt;9 -->\n<g id=\"edge9\" class=\"edge\">\n<title>3&#45;&gt;9</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M374.678,-143.8314C383.8588,-135.1337 395.0006,-124.5783 404.9776,-115.1265\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"407.4757,-117.5811 412.3281,-108.1628 402.6615,-112.4995 407.4757,-117.5811\"/>\n</g>\n<!-- 10 -->\n<g id=\"node11\" class=\"node\">\n<title>10</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"63,-36 0,-36 0,0 63,0 63,-36\"/>\n<text text-anchor=\"middle\" x=\"31.5\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 2, 3]</text>\n</g>\n<!-- 4&#45;&gt;10 -->\n<g id=\"edge10\" class=\"edge\">\n<title>4&#45;&gt;10</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M34.4906,-71.8314C34.0628,-64.131 33.5541,-54.9743 33.0787,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"36.5724,-46.2037 32.523,-36.4133 29.5831,-46.592 36.5724,-46.2037\"/>\n</g>\n<!-- 11 -->\n<g id=\"node12\" class=\"node\">\n<title>11</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"144,-36 81,-36 81,0 144,0 144,-36\"/>\n<text text-anchor=\"middle\" x=\"112.5\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 3, 2]</text>\n</g>\n<!-- 5&#45;&gt;11 -->\n<g id=\"edge11\" class=\"edge\">\n<title>5&#45;&gt;11</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M112.5,-71.8314C112.5,-64.131 112.5,-54.9743 112.5,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"116.0001,-46.4132 112.5,-36.4133 109.0001,-46.4133 116.0001,-46.4132\"/>\n</g>\n<!-- 12 -->\n<g id=\"node13\" class=\"node\">\n<title>12</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"225,-36 162,-36 162,0 225,0 225,-36\"/>\n<text text-anchor=\"middle\" x=\"193.5\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 1, 3]</text>\n</g>\n<!-- 6&#45;&gt;12 -->\n<g id=\"edge12\" class=\"edge\">\n<title>6&#45;&gt;12</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M194.9953,-71.8314C194.7814,-64.131 194.5271,-54.9743 194.2894,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"197.7879,-46.3122 194.0115,-36.4133 190.7906,-46.5066 197.7879,-46.3122\"/>\n</g>\n<!-- 13 -->\n<g id=\"node14\" class=\"node\">\n<title>13</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"306,-36 243,-36 243,0 306,0 306,-36\"/>\n<text text-anchor=\"middle\" x=\"274.5\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 3, 1]</text>\n</g>\n<!-- 7&#45;&gt;13 -->\n<g id=\"edge13\" class=\"edge\">\n<title>7&#45;&gt;13</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M271.5094,-71.8314C271.9372,-64.131 272.4459,-54.9743 272.9213,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"276.4169,-46.592 273.477,-36.4133 269.4276,-46.2037 276.4169,-46.592\"/>\n</g>\n<!-- 14 -->\n<g id=\"node15\" class=\"node\">\n<title>14</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"387,-36 324,-36 324,0 387,0 387,-36\"/>\n<text text-anchor=\"middle\" x=\"355.5\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 1, 2]</text>\n</g>\n<!-- 8&#45;&gt;14 -->\n<g id=\"edge14\" class=\"edge\">\n<title>8&#45;&gt;14</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M355.5,-71.8314C355.5,-64.131 355.5,-54.9743 355.5,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"359.0001,-46.4132 355.5,-36.4133 352.0001,-46.4133 359.0001,-46.4132\"/>\n</g>\n<!-- 15 -->\n<g id=\"node16\" class=\"node\">\n<title>15</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"468,-36 405,-36 405,0 468,0 468,-36\"/>\n<text text-anchor=\"middle\" x=\"436.5\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 2, 1]</text>\n</g>\n<!-- 9&#45;&gt;15 -->\n<g id=\"edge15\" class=\"edge\">\n<title>9&#45;&gt;15</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M432.7617,-71.8314C433.2965,-64.131 433.9323,-54.9743 434.5266,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"438.02,-46.6317 435.2213,-36.4133 431.0368,-46.1467 438.02,-46.6317\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 145
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AYWVQ1YckUzX",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def p_n_m(a, n, m, d, used, curr, ans):\n",
        "  print(curr, end='->')\n",
        "  if d == m: #end condition\n",
        "    ans.append(curr[::]) \n",
        "    return\n",
        "  \n",
        "  for i in range(n):\n",
        "    if not used[i]:\n",
        "      # generate the next solution from curr\n",
        "      curr.append(a[i])\n",
        "      used[i] = True\n",
        "      \n",
        "      # move to the next solution\n",
        "      p_n_m(a, n, m, d + 1, used, curr, ans)\n",
        "      #backtrack to previous partial state\n",
        "      curr.pop()\n",
        "      print('backtrack:', curr)\n",
        "      used[i] = False\n",
        "  return"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zoBmGC8IkXsp",
        "colab_type": "code",
        "outputId": "d58d7762-32fc-4534-a9a6-7007fffb9384",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 311
        }
      },
      "source": [
        "a = [1, 2, 3]\n",
        "n = len(a)\n",
        "ans = [[None]]\n",
        "used = [False] * len(a)\n",
        "ans = []\n",
        "p_n_m(a, n, n, 0, used, [], ans)\n",
        "print(ans)"
      ],
      "execution_count": 147,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[]->[1]->[1, 2]->[1, 2, 3]->backtrack: [1, 2]\n",
            "backtrack: [1]\n",
            "[1, 3]->[1, 3, 2]->backtrack: [1, 3]\n",
            "backtrack: [1]\n",
            "backtrack: []\n",
            "[2]->[2, 1]->[2, 1, 3]->backtrack: [2, 1]\n",
            "backtrack: [2]\n",
            "[2, 3]->[2, 3, 1]->backtrack: [2, 3]\n",
            "backtrack: [2]\n",
            "backtrack: []\n",
            "[3]->[3, 1]->[3, 1, 2]->backtrack: [3, 1]\n",
            "backtrack: [3]\n",
            "[3, 2]->[3, 2, 1]->backtrack: [3, 2]\n",
            "backtrack: [3]\n",
            "backtrack: []\n",
            "[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iJlzXjqjwfsn",
        "colab_type": "text"
      },
      "source": [
        "###Swapping Method\n",
        "\n",
        "Extention: Johnson-Trotter algorithm, \n",
        "* https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm\n",
        "* "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dxYiveMB6lnz",
        "colab_type": "code",
        "outputId": "605a8015-6ffe-4568-9a37-12933b355e7e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 427
        }
      },
      "source": [
        "from graphviz import Digraph\n",
        "dot = Digraph(comment='The Round Table', format='png')\n",
        "dot.node_attr['shape']='box'\n",
        "#print(get_methods(Digraph))\n",
        "#print(Digraph.__dict__)\n",
        "nodes = ['[1, 2, 3]', '[1, 2, 3]', '[2, 1, 3]', '[3, 2, 1]', '[1, 2, 3]', '[1, 3, 2]', '[2, 1, 3]', '[2, 3, 1]', '[3, 2, 1]', '[3, 1, 2]', \n",
        "         '[1, 2, 3]', '[1, 3, 2]', '[2, 1, 3]', '[2, 3, 1]', '[3, 2, 1]', '[3, 1, 2]']\n",
        "for i, node in enumerate(nodes):\n",
        "  dot.node(str(i), label=node)\n",
        "edges = [('0', '1', '(0, 0)'), ('0', '2', '(0, 1)'), ('0', '3', '(0, 2)'), ('1', '4', '(1, 1)'), ('1', '5', '(1, 2)'), ('2', '6', '(1, 1)'), ('2', '7', '(1, 2)'), \n",
        "         ('3', '8', '(1, 1)'), ('3', '9', '(1, 2)'), ('4', '10', '(2, 2)'), ('5', '11', '(2, 2)'), ('6', '12', '(2, 2)'), ('7', '13', '(2, 2)'), \n",
        "         ('8', '14', '(2, 2)'), ('9', '15', '(2, 2)')]\n",
        "for n1, n2, l in edges:\n",
        "  dot.edge(n1, n2,  _attributes={'label': l})\n",
        "# dot.edge('0', '1', _attributes={'label': '4'})\n",
        "# dot.edge('S', 'B', _attributes={'label': '5'})\n",
        "# dot.edge('A', 'G', _attributes={'label': '7'})\n",
        "# dot.edge('B', 'G', _attributes={'label': '3'})\n",
        "dot.render('test-output/permutation_swap', view=True) \n",
        "\n",
        "dot"
      ],
      "execution_count": 148,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7fac751ab358>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: %3 Pages: 1 -->\n<svg width=\"477pt\" height=\"305pt\"\n viewBox=\"0.00 0.00 476.50 305.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 301)\">\n<title>%3</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-301 472.5,-301 472.5,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"273,-297 210,-297 210,-261 273,-261 273,-297\"/>\n<text text-anchor=\"middle\" x=\"241.5\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 2, 3]</text>\n</g>\n<!-- 1 -->\n<g id=\"node2\" class=\"node\">\n<title>1</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"144,-210 81,-210 81,-174 144,-174 144,-210\"/>\n<text text-anchor=\"middle\" x=\"112.5\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 2, 3]</text>\n</g>\n<!-- 0&#45;&gt;1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M214.7711,-260.9735C195.3125,-247.8503 168.7725,-229.9512 147.6052,-215.6756\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"149.4424,-212.6931 139.1946,-210.0034 145.5284,-218.4966 149.4424,-212.6931\"/>\n<text text-anchor=\"middle\" x=\"200.5\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">(0, 0)</text>\n</g>\n<!-- 2 -->\n<g id=\"node3\" class=\"node\">\n<title>2</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"273,-210 210,-210 210,-174 273,-174 273,-210\"/>\n<text text-anchor=\"middle\" x=\"241.5\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 1, 3]</text>\n</g>\n<!-- 0&#45;&gt;2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>0&#45;&gt;2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M241.5,-260.9735C241.5,-249.1918 241.5,-233.5607 241.5,-220.1581\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"245.0001,-220.0033 241.5,-210.0034 238.0001,-220.0034 245.0001,-220.0033\"/>\n<text text-anchor=\"middle\" x=\"257.5\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">(0, 1)</text>\n</g>\n<!-- 3 -->\n<g id=\"node4\" class=\"node\">\n<title>3</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"387,-210 324,-210 324,-174 387,-174 387,-210\"/>\n<text text-anchor=\"middle\" x=\"355.5\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 2, 1]</text>\n</g>\n<!-- 0&#45;&gt;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>0&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M265.1209,-260.9735C282.0876,-248.0253 305.1465,-230.4276 323.726,-216.2485\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"326.0832,-218.8525 331.9094,-210.0034 321.8365,-213.2878 326.0832,-218.8525\"/>\n<text text-anchor=\"middle\" x=\"320.5\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">(0, 2)</text>\n</g>\n<!-- 4 -->\n<g id=\"node5\" class=\"node\">\n<title>4</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"63,-123 0,-123 0,-87 63,-87 63,-123\"/>\n<text text-anchor=\"middle\" x=\"31.5\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 2, 3]</text>\n</g>\n<!-- 1&#45;&gt;4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>1&#45;&gt;4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M93.9615,-173.9033C88.2831,-168.2429 82.0678,-161.9266 76.5,-156 68.981,-147.9964 60.9862,-139.0772 53.8536,-130.964\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"56.2723,-128.4127 47.058,-123.1832 51.0001,-133.0174 56.2723,-128.4127\"/>\n<text text-anchor=\"middle\" x=\"92.5\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">(1, 1)</text>\n</g>\n<!-- 5 -->\n<g id=\"node6\" class=\"node\">\n<title>5</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"144,-123 81,-123 81,-87 144,-87 144,-123\"/>\n<text text-anchor=\"middle\" x=\"112.5\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 3, 2]</text>\n</g>\n<!-- 1&#45;&gt;5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>1&#45;&gt;5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M112.5,-173.9735C112.5,-162.1918 112.5,-146.5607 112.5,-133.1581\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"116.0001,-133.0033 112.5,-123.0034 109.0001,-133.0034 116.0001,-133.0033\"/>\n<text text-anchor=\"middle\" x=\"128.5\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">(1, 2)</text>\n</g>\n<!-- 6 -->\n<g id=\"node7\" class=\"node\">\n<title>6</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"225,-123 162,-123 162,-87 225,-87 225,-123\"/>\n<text text-anchor=\"middle\" x=\"193.5\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 1, 3]</text>\n</g>\n<!-- 2&#45;&gt;6 -->\n<g id=\"edge6\" class=\"edge\">\n<title>2&#45;&gt;6</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M230.032,-173.8473C226.5562,-168.1846 222.7897,-161.8811 219.5,-156 215.2229,-148.3536 210.8083,-139.9257 206.8582,-132.1612\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"209.9297,-130.4785 202.3107,-123.1164 203.6757,-133.6229 209.9297,-130.4785\"/>\n<text text-anchor=\"middle\" x=\"235.5\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">(1, 1)</text>\n</g>\n<!-- 7 -->\n<g id=\"node8\" class=\"node\">\n<title>7</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"306,-123 243,-123 243,-87 306,-87 306,-123\"/>\n<text text-anchor=\"middle\" x=\"274.5\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 3, 1]</text>\n</g>\n<!-- 2&#45;&gt;7 -->\n<g id=\"edge7\" class=\"edge\">\n<title>2&#45;&gt;7</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M248.3376,-173.9735C252.8951,-161.9585 258.971,-145.9401 264.1203,-132.3646\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"267.397,-133.5947 267.6711,-123.0034 260.852,-131.112 267.397,-133.5947\"/>\n<text text-anchor=\"middle\" x=\"275.5\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">(1, 2)</text>\n</g>\n<!-- 8 -->\n<g id=\"node9\" class=\"node\">\n<title>8</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"387,-123 324,-123 324,-87 387,-87 387,-123\"/>\n<text text-anchor=\"middle\" x=\"355.5\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 2, 1]</text>\n</g>\n<!-- 3&#45;&gt;8 -->\n<g id=\"edge8\" class=\"edge\">\n<title>3&#45;&gt;8</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M355.5,-173.9735C355.5,-162.1918 355.5,-146.5607 355.5,-133.1581\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"359.0001,-133.0033 355.5,-123.0034 352.0001,-133.0034 359.0001,-133.0033\"/>\n<text text-anchor=\"middle\" x=\"371.5\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">(1, 1)</text>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"468,-123 405,-123 405,-87 468,-87 468,-123\"/>\n<text text-anchor=\"middle\" x=\"436.5\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 1, 2]</text>\n</g>\n<!-- 3&#45;&gt;9 -->\n<g id=\"edge9\" class=\"edge\">\n<title>3&#45;&gt;9</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M374.0385,-173.9033C379.7169,-168.2429 385.9322,-161.9266 391.5,-156 399.019,-147.9964 407.0138,-139.0772 414.1464,-130.964\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"416.9999,-133.0174 420.942,-123.1832 411.7277,-128.4127 416.9999,-133.0174\"/>\n<text text-anchor=\"middle\" x=\"419.5\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">(1, 2)</text>\n</g>\n<!-- 10 -->\n<g id=\"node11\" class=\"node\">\n<title>10</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"63,-36 0,-36 0,0 63,0 63,-36\"/>\n<text text-anchor=\"middle\" x=\"31.5\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 2, 3]</text>\n</g>\n<!-- 4&#45;&gt;10 -->\n<g id=\"edge10\" class=\"edge\">\n<title>4&#45;&gt;10</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M31.5,-86.9735C31.5,-75.1918 31.5,-59.5607 31.5,-46.1581\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"35.0001,-46.0033 31.5,-36.0034 28.0001,-46.0034 35.0001,-46.0033\"/>\n<text text-anchor=\"middle\" x=\"47.5\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">(2, 2)</text>\n</g>\n<!-- 11 -->\n<g id=\"node12\" class=\"node\">\n<title>11</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"144,-36 81,-36 81,0 144,0 144,-36\"/>\n<text text-anchor=\"middle\" x=\"112.5\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 3, 2]</text>\n</g>\n<!-- 5&#45;&gt;11 -->\n<g id=\"edge11\" class=\"edge\">\n<title>5&#45;&gt;11</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M112.5,-86.9735C112.5,-75.1918 112.5,-59.5607 112.5,-46.1581\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"116.0001,-46.0033 112.5,-36.0034 109.0001,-46.0034 116.0001,-46.0033\"/>\n<text text-anchor=\"middle\" x=\"128.5\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">(2, 2)</text>\n</g>\n<!-- 12 -->\n<g id=\"node13\" class=\"node\">\n<title>12</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"225,-36 162,-36 162,0 225,0 225,-36\"/>\n<text text-anchor=\"middle\" x=\"193.5\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 1, 3]</text>\n</g>\n<!-- 6&#45;&gt;12 -->\n<g id=\"edge12\" class=\"edge\">\n<title>6&#45;&gt;12</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M193.5,-86.9735C193.5,-75.1918 193.5,-59.5607 193.5,-46.1581\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"197.0001,-46.0033 193.5,-36.0034 190.0001,-46.0034 197.0001,-46.0033\"/>\n<text text-anchor=\"middle\" x=\"209.5\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">(2, 2)</text>\n</g>\n<!-- 13 -->\n<g id=\"node14\" class=\"node\">\n<title>13</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"306,-36 243,-36 243,0 306,0 306,-36\"/>\n<text text-anchor=\"middle\" x=\"274.5\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 3, 1]</text>\n</g>\n<!-- 7&#45;&gt;13 -->\n<g id=\"edge13\" class=\"edge\">\n<title>7&#45;&gt;13</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M274.5,-86.9735C274.5,-75.1918 274.5,-59.5607 274.5,-46.1581\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"278.0001,-46.0033 274.5,-36.0034 271.0001,-46.0034 278.0001,-46.0033\"/>\n<text text-anchor=\"middle\" x=\"290.5\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">(2, 2)</text>\n</g>\n<!-- 14 -->\n<g id=\"node15\" class=\"node\">\n<title>14</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"387,-36 324,-36 324,0 387,0 387,-36\"/>\n<text text-anchor=\"middle\" x=\"355.5\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 2, 1]</text>\n</g>\n<!-- 8&#45;&gt;14 -->\n<g id=\"edge14\" class=\"edge\">\n<title>8&#45;&gt;14</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M355.5,-86.9735C355.5,-75.1918 355.5,-59.5607 355.5,-46.1581\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"359.0001,-46.0033 355.5,-36.0034 352.0001,-46.0034 359.0001,-46.0033\"/>\n<text text-anchor=\"middle\" x=\"371.5\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">(2, 2)</text>\n</g>\n<!-- 15 -->\n<g id=\"node16\" class=\"node\">\n<title>15</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"468,-36 405,-36 405,0 468,0 468,-36\"/>\n<text text-anchor=\"middle\" x=\"436.5\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 1, 2]</text>\n</g>\n<!-- 9&#45;&gt;15 -->\n<g id=\"edge15\" class=\"edge\">\n<title>9&#45;&gt;15</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M436.5,-86.9735C436.5,-75.1918 436.5,-59.5607 436.5,-46.1581\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"440.0001,-46.0033 436.5,-36.0034 433.0001,-46.0034 440.0001,-46.0033\"/>\n<text text-anchor=\"middle\" x=\"452.5\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">(2, 2)</text>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 148
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QUrTCuJLhBwK",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# permutation by swapping\n",
        "ans = []\n",
        "def permutate(a, d):\n",
        "  global ans\n",
        "  \n",
        "  if d == len(a):\n",
        "    ans.append(a[::])\n",
        "  for i in range(d, len(a)):\n",
        "    a[i], a[d] = a[d], a[i]\n",
        "    print(a, '(', d, i, ')')\n",
        "    permutate(a, d+1)\n",
        "    a[i], a[d] = a[d], a[i]\n",
        "  return"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iFPDsOYwDLau",
        "colab_type": "code",
        "outputId": "5f62032f-0b5f-4999-c311-fdd86a264d97",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 311
        }
      },
      "source": [
        "a = [1, 2, 3]\n",
        "permutate(a, 0)\n",
        "ans"
      ],
      "execution_count": 150,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[1, 2, 3] ( 0 0 )\n",
            "[1, 2, 3] ( 1 1 )\n",
            "[1, 2, 3] ( 2 2 )\n",
            "[1, 3, 2] ( 1 2 )\n",
            "[1, 3, 2] ( 2 2 )\n",
            "[2, 1, 3] ( 0 1 )\n",
            "[2, 1, 3] ( 1 1 )\n",
            "[2, 1, 3] ( 2 2 )\n",
            "[2, 3, 1] ( 1 2 )\n",
            "[2, 3, 1] ( 2 2 )\n",
            "[3, 2, 1] ( 0 2 )\n",
            "[3, 2, 1] ( 1 1 )\n",
            "[3, 2, 1] ( 2 2 )\n",
            "[3, 1, 2] ( 1 2 )\n",
            "[3, 1, 2] ( 2 2 )\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 150
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "guKxb4JXI8rg",
        "colab_type": "text"
      },
      "source": [
        "When there are duplicates, for example, \n",
        "https://www.geeksforgeeks.org/distinct-permutations-string-set-2/"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ujwVtrk3Dqs2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# permutation by swapping and there might be having duplicates\n",
        "ans = []\n",
        "def checkSwap(a, d, cur):\n",
        "  for i in range(d, cur):\n",
        "    if a[i] == a[cur]:\n",
        "      return False\n",
        "  return True\n",
        "def permutate(a, d):\n",
        "  global ans\n",
        "  if d == len(a):\n",
        "    ans.append(a[::])\n",
        "  for i in range(d, len(a)):\n",
        "    if not checkSwap(a, d, i):\n",
        "      continue\n",
        "    a[i], a[d] = a[d], a[i]\n",
        "    permutate(a, d+1)\n",
        "    a[i], a[d] = a[d], a[i]\n",
        "  return"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8qLIzNL2EDXC",
        "colab_type": "code",
        "outputId": "e2e38d1b-a0ef-4ee2-ee93-c5a71c8f80cb",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 237
        }
      },
      "source": [
        "a = [1,2, 2, 3]\n",
        "permutate(a, 0)\n",
        "ans"
      ],
      "execution_count": 152,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[[1, 2, 2, 3],\n",
              " [1, 2, 3, 2],\n",
              " [1, 3, 2, 2],\n",
              " [2, 1, 2, 3],\n",
              " [2, 1, 3, 2],\n",
              " [2, 2, 1, 3],\n",
              " [2, 2, 3, 1],\n",
              " [2, 3, 2, 1],\n",
              " [2, 3, 1, 2],\n",
              " [3, 2, 2, 1],\n",
              " [3, 2, 1, 2],\n",
              " [3, 1, 2, 2]]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 152
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xhrZMOANBdF-",
        "colab_type": "text"
      },
      "source": [
        "#### Questions to ponder\n",
        "1. What if there are duplicates in the input list? How to count and how to enumerate all possible permutations? [1, 2, 3, 2]\n",
        "\n",
        "We have a way to count:\n",
        "\\begin{align}\n",
        "\\frac{P(n, n)}{c_1!c_2!...}\n",
        "\\end{align}\n",
        "\n",
        "Resources\n",
        "* https://www.cs.sfu.ca/~ggbaker/zju/math/perm-comb-more.html\n",
        "\n",
        "[47. Permutations II](https://leetcode.com/problems/permutations-ii/)\n",
        "\n",
        "* first sort it as [1, 2, 2, 3]. We can draw the process\n",
        "```\n",
        "{}\n",
        "i=0: {1}, {2}, *{2}*,  {3} = 3\n",
        "i=1: {1, 2}, *{1, 2}*,  {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3,2}, *{3, 2}*\n",
        "i=2: {1, 2, 2}, {1, 2, 3}, \n",
        "```\n",
        "Exactlyt the same process except that we skip the duplicates. \n",
        "We can not find a recurrence relation to this. This depends on how many duplicates we have. \n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8i2y2Ri-Bc_w",
        "colab_type": "code",
        "outputId": "7a572b00-7f89-4e2d-ee51-21af5bc1578b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 483
        }
      },
      "source": [
        "from graphviz import Digraph\n",
        "dot = Digraph(comment='The Round Table', format='png')\n",
        "dot.node_attr['shape']='box'\n",
        "#print(get_methods(Digraph))\n",
        "#print(Digraph.__dict__)\n",
        "nodes = [('0', '[]'), ('1', '[1]'), ('2', '[2]'), ('3', '[2]'), ('4', '[3]'), \n",
        "         ('5', '[1, 2]'), ('6', '[1, 2]'), ('7', '[1, 3]'), \n",
        "         ('8', '[2, 1]'), ('9', '[2, 2]'), ('10', '[2, 3]'), \n",
        "         ('11', '[3, 1]'), ('12', '[3, 2]'), ('12_1', '[3, 2]'), \n",
        "         ('13', '[1, 2, 2]'), ('14', '[1, 2, 3]'), \n",
        "         ('15', '[1, 3, 2]'), \n",
        "         ('16', '[2, 1, 2]'), ('17', '[2, 1, 3]'),\n",
        "         ('18', '[2, 2, 1]'), ('19', '[2, 2, 3]'),\n",
        "         ('20', '[2, 3, 1]'), ('21', '[2, 3, 2]'),\n",
        "         ('22', '[3, 1, 2]'), ('22_1', '[3, 1, 2]') ,\n",
        "         ('23', '[3, 2, 1]'), ('24', '[3, 2, 2]'),\n",
        "         ('25', '[1, 2, 2, 3]'), \n",
        "         ('26', '[1, 2, 3, 2]'), \n",
        "         ('27', '[1, 3, 2, 2]'), \n",
        "         ('28', '[2, 1, 2, 3]'), \n",
        "         ('29', '[2, 1, 3, 2]'),\n",
        "         ('30', '[2, 2, 1, 3]'), \n",
        "         ('31', '[2, 2, 3, 1]'), \n",
        "         ('32', '[2, 3, 1, 2]'), \n",
        "         ('33', '[2, 3, 2, 1]'), \n",
        "         ('34', '[3, 1, 2, 2]'), \n",
        "         ('35', '[3, 2, 1, 2]'), \n",
        "         ('36', '[3, 2, 2, 1]')]\n",
        "for i, node in nodes:\n",
        "  dot.node(i, label=node)\n",
        "edges = [('0', '1'), ('0', '2'), ('0', '3'), ('0', '4'),\n",
        "         ('1', '5'), ('1', '6'), ('1', '7'),\n",
        "         ('2', '8'), ('2', '9'), ('2', '10'),\n",
        "         ('4', '11'), ('4', '12'),('4', '12_1'),\n",
        "         ('5', '13'), ('5', '14'),\n",
        "         ('7', '15'),\n",
        "         ('8', '16'), ('8', '17'),\n",
        "         ('9', '18'), ('9', '19'),\n",
        "         ('10', '20'), ('10', '21'),\n",
        "         ('11', '22'), ('11', '22_1'),\n",
        "         ('12', '23'),('12', '24'),\n",
        "         ('13', '25'),('14', '26'), ('15', '27'),('16', '28'), ('17', '29'),('18', '30'), \n",
        "         ('19', '31'),('20', '32'), ('21', '33'),('22', '34'), ('23', '35'),('24', '36')]\n",
        "for n1, n2 in edges:\n",
        "  dot.edge(n1, n2)\n",
        "# dot.edge('0', '1', _attributes={'label': '4'})\n",
        "# dot.edge('S', 'B', _attributes={'label': '5'})\n",
        "# dot.edge('A', 'G', _attributes={'label': '7'})\n",
        "# dot.edge('B', 'G', _attributes={'label': '3'})\n",
        "dot.render('test-output/permutation_repeat', view=True) \n",
        "\n",
        "dot"
      ],
      "execution_count": 153,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7fac75194dd8>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: %3 Pages: 1 -->\n<svg width=\"1206pt\" height=\"332pt\"\n viewBox=\"0.00 0.00 1206.00 332.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 328)\">\n<title>%3</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-328 1202,-328 1202,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"640,-324 586,-324 586,-288 640,-288 640,-324\"/>\n<text text-anchor=\"middle\" x=\"613\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[]</text>\n</g>\n<!-- 1 -->\n<g id=\"node2\" class=\"node\">\n<title>1</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"243,-252 189,-252 189,-216 243,-216 243,-252\"/>\n<text text-anchor=\"middle\" x=\"216\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1]</text>\n</g>\n<!-- 0&#45;&gt;1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M585.7126,-301.0511C516.2194,-288.4479 332.4757,-255.1241 253.2366,-240.7532\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"253.6794,-237.2765 243.2153,-238.9358 252.4302,-244.1642 253.6794,-237.2765\"/>\n</g>\n<!-- 2 -->\n<g id=\"node3\" class=\"node\">\n<title>2</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"604,-252 550,-252 550,-216 604,-216 604,-252\"/>\n<text text-anchor=\"middle\" x=\"577\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2]</text>\n</g>\n<!-- 0&#45;&gt;2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>0&#45;&gt;2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M603.9157,-287.8314C599.9385,-279.8771 595.1845,-270.369 590.7861,-261.5723\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"593.8093,-259.7923 586.2066,-252.4133 587.5483,-262.9228 593.8093,-259.7923\"/>\n</g>\n<!-- 3 -->\n<g id=\"node4\" class=\"node\">\n<title>3</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"676,-252 622,-252 622,-216 676,-216 676,-252\"/>\n<text text-anchor=\"middle\" x=\"649\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2]</text>\n</g>\n<!-- 0&#45;&gt;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>0&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M622.0843,-287.8314C626.0615,-279.8771 630.8155,-270.369 635.2139,-261.5723\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"638.4517,-262.9228 639.7934,-252.4133 632.1907,-259.7923 638.4517,-262.9228\"/>\n</g>\n<!-- 4 -->\n<g id=\"node5\" class=\"node\">\n<title>4</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"1049,-252 995,-252 995,-216 1049,-216 1049,-252\"/>\n<text text-anchor=\"middle\" x=\"1022\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3]</text>\n</g>\n<!-- 0&#45;&gt;4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>0&#45;&gt;4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M640.1524,-301.2201C711.2692,-288.7008 903.0907,-254.9327 984.5706,-240.589\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"985.6155,-243.959 994.8572,-238.7782 984.4018,-237.065 985.6155,-243.959\"/>\n</g>\n<!-- 5 -->\n<g id=\"node6\" class=\"node\">\n<title>5</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"135,-180 81,-180 81,-144 135,-144 135,-180\"/>\n<text text-anchor=\"middle\" x=\"108\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 2]</text>\n</g>\n<!-- 1&#45;&gt;5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>1&#45;&gt;5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M188.747,-215.8314C175.0611,-206.7074 158.3085,-195.539 143.6173,-185.7449\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"145.5062,-182.7977 135.2442,-180.1628 141.6233,-188.6221 145.5062,-182.7977\"/>\n</g>\n<!-- 6 -->\n<g id=\"node7\" class=\"node\">\n<title>6</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"207,-180 153,-180 153,-144 207,-144 207,-180\"/>\n<text text-anchor=\"middle\" x=\"180\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 2]</text>\n</g>\n<!-- 1&#45;&gt;6 -->\n<g id=\"edge6\" class=\"edge\">\n<title>1&#45;&gt;6</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M206.9157,-215.8314C202.9385,-207.8771 198.1845,-198.369 193.7861,-189.5723\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"196.8093,-187.7923 189.2066,-180.4133 190.5483,-190.9228 196.8093,-187.7923\"/>\n</g>\n<!-- 7 -->\n<g id=\"node8\" class=\"node\">\n<title>7</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"279,-180 225,-180 225,-144 279,-144 279,-180\"/>\n<text text-anchor=\"middle\" x=\"252\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 3]</text>\n</g>\n<!-- 1&#45;&gt;7 -->\n<g id=\"edge7\" class=\"edge\">\n<title>1&#45;&gt;7</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M225.0843,-215.8314C229.0615,-207.8771 233.8155,-198.369 238.2139,-189.5723\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"241.4517,-190.9228 242.7934,-180.4133 235.1907,-187.7923 241.4517,-190.9228\"/>\n</g>\n<!-- 8 -->\n<g id=\"node9\" class=\"node\">\n<title>8</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"460,-180 406,-180 406,-144 460,-144 460,-180\"/>\n<text text-anchor=\"middle\" x=\"433\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 1]</text>\n</g>\n<!-- 2&#45;&gt;8 -->\n<g id=\"edge8\" class=\"edge\">\n<title>2&#45;&gt;8</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M549.9147,-220.4574C527.2307,-209.1153 494.6433,-192.8217 469.6319,-180.316\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"470.963,-177.0684 460.4534,-175.7267 467.8325,-183.3294 470.963,-177.0684\"/>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"604,-180 550,-180 550,-144 604,-144 604,-180\"/>\n<text text-anchor=\"middle\" x=\"577\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 2]</text>\n</g>\n<!-- 2&#45;&gt;9 -->\n<g id=\"edge9\" class=\"edge\">\n<title>2&#45;&gt;9</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M577,-215.8314C577,-208.131 577,-198.9743 577,-190.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"580.5001,-190.4132 577,-180.4133 573.5001,-190.4133 580.5001,-190.4132\"/>\n</g>\n<!-- 10 -->\n<g id=\"node11\" class=\"node\">\n<title>10</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"748,-180 694,-180 694,-144 748,-144 748,-180\"/>\n<text text-anchor=\"middle\" x=\"721\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 3]</text>\n</g>\n<!-- 2&#45;&gt;10 -->\n<g id=\"edge10\" class=\"edge\">\n<title>2&#45;&gt;10</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M604.0853,-220.4574C626.7693,-209.1153 659.3567,-192.8217 684.3681,-180.316\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"686.1675,-183.3294 693.5466,-175.7267 683.037,-177.0684 686.1675,-183.3294\"/>\n</g>\n<!-- 11 -->\n<g id=\"node12\" class=\"node\">\n<title>11</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"1013,-180 959,-180 959,-144 1013,-144 1013,-180\"/>\n<text text-anchor=\"middle\" x=\"986\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 1]</text>\n</g>\n<!-- 4&#45;&gt;11 -->\n<g id=\"edge11\" class=\"edge\">\n<title>4&#45;&gt;11</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1012.9157,-215.8314C1008.9385,-207.8771 1004.1845,-198.369 999.7861,-189.5723\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"1002.8093,-187.7923 995.2066,-180.4133 996.5483,-190.9228 1002.8093,-187.7923\"/>\n</g>\n<!-- 12 -->\n<g id=\"node13\" class=\"node\">\n<title>12</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"1089,-180 1035,-180 1035,-144 1089,-144 1089,-180\"/>\n<text text-anchor=\"middle\" x=\"1062\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 2]</text>\n</g>\n<!-- 4&#45;&gt;12 -->\n<g id=\"edge12\" class=\"edge\">\n<title>4&#45;&gt;12</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1032.0937,-215.8314C1036.5597,-207.7925 1041.9075,-198.1666 1046.8379,-189.2918\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"1049.9735,-190.8546 1051.7704,-180.4133 1043.8544,-187.4551 1049.9735,-190.8546\"/>\n</g>\n<!-- 12_1 -->\n<g id=\"node14\" class=\"node\">\n<title>12_1</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"1161,-180 1107,-180 1107,-144 1161,-144 1161,-180\"/>\n<text text-anchor=\"middle\" x=\"1134\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 2]</text>\n</g>\n<!-- 4&#45;&gt;12_1 -->\n<g id=\"edge13\" class=\"edge\">\n<title>4&#45;&gt;12_1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1049.1121,-216.5708C1063.8606,-207.0896 1082.2904,-195.2419 1098.2056,-185.0107\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"1100.2303,-187.87 1106.7494,-179.5182 1096.4449,-181.9817 1100.2303,-187.87\"/>\n</g>\n<!-- 13 -->\n<g id=\"node15\" class=\"node\">\n<title>13</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"74.5,-108 11.5,-108 11.5,-72 74.5,-72 74.5,-108\"/>\n<text text-anchor=\"middle\" x=\"43\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 2, 2]</text>\n</g>\n<!-- 5&#45;&gt;13 -->\n<g id=\"edge14\" class=\"edge\">\n<title>5&#45;&gt;13</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M91.5978,-143.8314C83.9585,-135.3694 74.7317,-125.1489 66.3793,-115.8971\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"68.9221,-113.4906 59.6231,-108.4133 63.7262,-118.1813 68.9221,-113.4906\"/>\n</g>\n<!-- 14 -->\n<g id=\"node16\" class=\"node\">\n<title>14</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"159.5,-108 96.5,-108 96.5,-72 159.5,-72 159.5,-108\"/>\n<text text-anchor=\"middle\" x=\"128\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 2, 3]</text>\n</g>\n<!-- 5&#45;&gt;14 -->\n<g id=\"edge15\" class=\"edge\">\n<title>5&#45;&gt;14</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M113.0468,-143.8314C115.2094,-136.0463 117.7853,-126.7729 120.1848,-118.1347\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"123.581,-118.9852 122.8852,-108.4133 116.8364,-117.1117 123.581,-118.9852\"/>\n</g>\n<!-- 15 -->\n<g id=\"node17\" class=\"node\">\n<title>15</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"277.5,-108 214.5,-108 214.5,-72 277.5,-72 277.5,-108\"/>\n<text text-anchor=\"middle\" x=\"246\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 3, 2]</text>\n</g>\n<!-- 7&#45;&gt;15 -->\n<g id=\"edge16\" class=\"edge\">\n<title>7&#45;&gt;15</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M250.4859,-143.8314C249.8442,-136.131 249.0812,-126.9743 248.3681,-118.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"251.8529,-118.088 247.5344,-108.4133 244.8771,-118.6694 251.8529,-118.088\"/>\n</g>\n<!-- 16 -->\n<g id=\"node18\" class=\"node\">\n<title>16</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"375.5,-108 312.5,-108 312.5,-72 375.5,-72 375.5,-108\"/>\n<text text-anchor=\"middle\" x=\"344\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 1, 2]</text>\n</g>\n<!-- 8&#45;&gt;16 -->\n<g id=\"edge17\" class=\"edge\">\n<title>8&#45;&gt;16</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M410.5415,-143.8314C399.5795,-134.9632 386.2301,-124.1637 374.3735,-114.5718\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"376.4271,-111.7313 366.4513,-108.1628 372.0245,-117.1734 376.4271,-111.7313\"/>\n</g>\n<!-- 17 -->\n<g id=\"node19\" class=\"node\">\n<title>17</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"464.5,-108 401.5,-108 401.5,-72 464.5,-72 464.5,-108\"/>\n<text text-anchor=\"middle\" x=\"433\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 1, 3]</text>\n</g>\n<!-- 8&#45;&gt;17 -->\n<g id=\"edge18\" class=\"edge\">\n<title>8&#45;&gt;17</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M433,-143.8314C433,-136.131 433,-126.9743 433,-118.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"436.5001,-118.4132 433,-108.4133 429.5001,-118.4133 436.5001,-118.4132\"/>\n</g>\n<!-- 18 -->\n<g id=\"node20\" class=\"node\">\n<title>18</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"564.5,-108 501.5,-108 501.5,-72 564.5,-72 564.5,-108\"/>\n<text text-anchor=\"middle\" x=\"533\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 2, 1]</text>\n</g>\n<!-- 9&#45;&gt;18 -->\n<g id=\"edge19\" class=\"edge\">\n<title>9&#45;&gt;18</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M565.8969,-143.8314C560.9326,-135.7079 554.9778,-125.9637 549.5072,-117.0118\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"552.4536,-115.121 544.2526,-108.4133 546.4806,-118.7712 552.4536,-115.121\"/>\n</g>\n<!-- 19 -->\n<g id=\"node21\" class=\"node\">\n<title>19</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"652.5,-108 589.5,-108 589.5,-72 652.5,-72 652.5,-108\"/>\n<text text-anchor=\"middle\" x=\"621\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 2, 3]</text>\n</g>\n<!-- 9&#45;&gt;19 -->\n<g id=\"edge20\" class=\"edge\">\n<title>9&#45;&gt;19</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M588.1031,-143.8314C593.0674,-135.7079 599.0222,-125.9637 604.4928,-117.0118\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"607.5194,-118.7712 609.7474,-108.4133 601.5464,-115.121 607.5194,-118.7712\"/>\n</g>\n<!-- 20 -->\n<g id=\"node22\" class=\"node\">\n<title>20</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"752.5,-108 689.5,-108 689.5,-72 752.5,-72 752.5,-108\"/>\n<text text-anchor=\"middle\" x=\"721\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 3, 1]</text>\n</g>\n<!-- 10&#45;&gt;20 -->\n<g id=\"edge21\" class=\"edge\">\n<title>10&#45;&gt;20</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M721,-143.8314C721,-136.131 721,-126.9743 721,-118.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"724.5001,-118.4132 721,-108.4133 717.5001,-118.4133 724.5001,-118.4132\"/>\n</g>\n<!-- 21 -->\n<g id=\"node23\" class=\"node\">\n<title>21</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"840.5,-108 777.5,-108 777.5,-72 840.5,-72 840.5,-108\"/>\n<text text-anchor=\"middle\" x=\"809\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 3, 2]</text>\n</g>\n<!-- 10&#45;&gt;21 -->\n<g id=\"edge22\" class=\"edge\">\n<title>10&#45;&gt;21</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M743.2061,-143.8314C754.045,-134.9632 767.2444,-124.1637 778.9678,-114.5718\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"781.2777,-117.2041 786.801,-108.1628 776.845,-111.7864 781.2777,-117.2041\"/>\n</g>\n<!-- 22 -->\n<g id=\"node24\" class=\"node\">\n<title>22</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"936.5,-108 873.5,-108 873.5,-72 936.5,-72 936.5,-108\"/>\n<text text-anchor=\"middle\" x=\"905\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 1, 2]</text>\n</g>\n<!-- 11&#45;&gt;22 -->\n<g id=\"edge23\" class=\"edge\">\n<title>11&#45;&gt;22</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M965.5603,-143.8314C955.6795,-135.0485 943.6676,-124.3712 932.955,-114.8489\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"935.2326,-112.1906 925.4332,-108.1628 930.582,-117.4224 935.2326,-112.1906\"/>\n</g>\n<!-- 22_1 -->\n<g id=\"node25\" class=\"node\">\n<title>22_1</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"1017.5,-108 954.5,-108 954.5,-72 1017.5,-72 1017.5,-108\"/>\n<text text-anchor=\"middle\" x=\"986\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 1, 2]</text>\n</g>\n<!-- 11&#45;&gt;22_1 -->\n<g id=\"edge24\" class=\"edge\">\n<title>11&#45;&gt;22_1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M986,-143.8314C986,-136.131 986,-126.9743 986,-118.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"989.5001,-118.4132 986,-108.4133 982.5001,-118.4133 989.5001,-118.4132\"/>\n</g>\n<!-- 23 -->\n<g id=\"node26\" class=\"node\">\n<title>23</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"1098.5,-108 1035.5,-108 1035.5,-72 1098.5,-72 1098.5,-108\"/>\n<text text-anchor=\"middle\" x=\"1067\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 2, 1]</text>\n</g>\n<!-- 12&#45;&gt;23 -->\n<g id=\"edge25\" class=\"edge\">\n<title>12&#45;&gt;23</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1063.2617,-143.8314C1063.7965,-136.131 1064.4323,-126.9743 1065.0266,-118.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"1068.52,-118.6317 1065.7213,-108.4133 1061.5368,-118.1467 1068.52,-118.6317\"/>\n</g>\n<!-- 24 -->\n<g id=\"node27\" class=\"node\">\n<title>24</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"1186.5,-108 1123.5,-108 1123.5,-72 1186.5,-72 1186.5,-108\"/>\n<text text-anchor=\"middle\" x=\"1155\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 2, 2]</text>\n</g>\n<!-- 12&#45;&gt;24 -->\n<g id=\"edge26\" class=\"edge\">\n<title>12&#45;&gt;24</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1085.4678,-143.8314C1097.0327,-134.8779 1111.1404,-123.9558 1123.6183,-114.2955\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"1125.775,-117.0521 1131.5397,-108.1628 1121.4898,-111.5171 1125.775,-117.0521\"/>\n</g>\n<!-- 25 -->\n<g id=\"node28\" class=\"node\">\n<title>25</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"78,-36 0,-36 0,0 78,0 78,-36\"/>\n<text text-anchor=\"middle\" x=\"39\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 2, 2, 3]</text>\n</g>\n<!-- 13&#45;&gt;25 -->\n<g id=\"edge27\" class=\"edge\">\n<title>13&#45;&gt;25</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M41.9906,-71.8314C41.5628,-64.131 41.0541,-54.9743 40.5787,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"44.0724,-46.2037 40.023,-36.4133 37.0831,-46.592 44.0724,-46.2037\"/>\n</g>\n<!-- 26 -->\n<g id=\"node29\" class=\"node\">\n<title>26</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"174,-36 96,-36 96,0 174,0 174,-36\"/>\n<text text-anchor=\"middle\" x=\"135\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 2, 3, 2]</text>\n</g>\n<!-- 14&#45;&gt;26 -->\n<g id=\"edge28\" class=\"edge\">\n<title>14&#45;&gt;26</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M129.7664,-71.8314C130.515,-64.131 131.4053,-54.9743 132.2373,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"135.7256,-46.7051 133.2098,-36.4133 128.7585,-46.0276 135.7256,-46.7051\"/>\n</g>\n<!-- 27 -->\n<g id=\"node30\" class=\"node\">\n<title>27</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"280,-36 202,-36 202,0 280,0 280,-36\"/>\n<text text-anchor=\"middle\" x=\"241\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[1, 3, 2, 2]</text>\n</g>\n<!-- 15&#45;&gt;27 -->\n<g id=\"edge29\" class=\"edge\">\n<title>15&#45;&gt;27</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M244.7383,-71.8314C244.2035,-64.131 243.5677,-54.9743 242.9734,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"246.4632,-46.1467 242.2787,-36.4133 239.48,-46.6317 246.4632,-46.1467\"/>\n</g>\n<!-- 28 -->\n<g id=\"node31\" class=\"node\">\n<title>28</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"376,-36 298,-36 298,0 376,0 376,-36\"/>\n<text text-anchor=\"middle\" x=\"337\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 1, 2, 3]</text>\n</g>\n<!-- 16&#45;&gt;28 -->\n<g id=\"edge30\" class=\"edge\">\n<title>16&#45;&gt;28</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M342.2336,-71.8314C341.485,-64.131 340.5947,-54.9743 339.7627,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"343.2415,-46.0276 338.7902,-36.4133 336.2744,-46.7051 343.2415,-46.0276\"/>\n</g>\n<!-- 29 -->\n<g id=\"node32\" class=\"node\">\n<title>29</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"472,-36 394,-36 394,0 472,0 472,-36\"/>\n<text text-anchor=\"middle\" x=\"433\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 1, 3, 2]</text>\n</g>\n<!-- 17&#45;&gt;29 -->\n<g id=\"edge31\" class=\"edge\">\n<title>17&#45;&gt;29</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M433,-71.8314C433,-64.131 433,-54.9743 433,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"436.5001,-46.4132 433,-36.4133 429.5001,-46.4133 436.5001,-46.4132\"/>\n</g>\n<!-- 30 -->\n<g id=\"node33\" class=\"node\">\n<title>30</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"568,-36 490,-36 490,0 568,0 568,-36\"/>\n<text text-anchor=\"middle\" x=\"529\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 2, 1, 3]</text>\n</g>\n<!-- 18&#45;&gt;30 -->\n<g id=\"edge32\" class=\"edge\">\n<title>18&#45;&gt;30</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M531.9906,-71.8314C531.5628,-64.131 531.0541,-54.9743 530.5787,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"534.0724,-46.2037 530.023,-36.4133 527.0831,-46.592 534.0724,-46.2037\"/>\n</g>\n<!-- 31 -->\n<g id=\"node34\" class=\"node\">\n<title>31</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"664,-36 586,-36 586,0 664,0 664,-36\"/>\n<text text-anchor=\"middle\" x=\"625\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 2, 3, 1]</text>\n</g>\n<!-- 19&#45;&gt;31 -->\n<g id=\"edge33\" class=\"edge\">\n<title>19&#45;&gt;31</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M622.0094,-71.8314C622.4372,-64.131 622.9459,-54.9743 623.4213,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"626.9169,-46.592 623.977,-36.4133 619.9276,-46.2037 626.9169,-46.592\"/>\n</g>\n<!-- 32 -->\n<g id=\"node35\" class=\"node\">\n<title>32</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"760,-36 682,-36 682,0 760,0 760,-36\"/>\n<text text-anchor=\"middle\" x=\"721\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 3, 1, 2]</text>\n</g>\n<!-- 20&#45;&gt;32 -->\n<g id=\"edge34\" class=\"edge\">\n<title>20&#45;&gt;32</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M721,-71.8314C721,-64.131 721,-54.9743 721,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"724.5001,-46.4132 721,-36.4133 717.5001,-46.4133 724.5001,-46.4132\"/>\n</g>\n<!-- 33 -->\n<g id=\"node36\" class=\"node\">\n<title>33</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"856,-36 778,-36 778,0 856,0 856,-36\"/>\n<text text-anchor=\"middle\" x=\"817\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[2, 3, 2, 1]</text>\n</g>\n<!-- 21&#45;&gt;33 -->\n<g id=\"edge35\" class=\"edge\">\n<title>21&#45;&gt;33</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M811.0187,-71.8314C811.8743,-64.131 812.8917,-54.9743 813.8426,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"817.3283,-46.7386 814.9541,-36.4133 810.3711,-45.9656 817.3283,-46.7386\"/>\n</g>\n<!-- 34 -->\n<g id=\"node37\" class=\"node\">\n<title>34</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"952,-36 874,-36 874,0 952,0 952,-36\"/>\n<text text-anchor=\"middle\" x=\"913\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 1, 2, 2]</text>\n</g>\n<!-- 22&#45;&gt;34 -->\n<g id=\"edge36\" class=\"edge\">\n<title>22&#45;&gt;34</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M907.0187,-71.8314C907.8743,-64.131 908.8917,-54.9743 909.8426,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"913.3283,-46.7386 910.9541,-36.4133 906.3711,-45.9656 913.3283,-46.7386\"/>\n</g>\n<!-- 35 -->\n<g id=\"node38\" class=\"node\">\n<title>35</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"1102,-36 1024,-36 1024,0 1102,0 1102,-36\"/>\n<text text-anchor=\"middle\" x=\"1063\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 2, 1, 2]</text>\n</g>\n<!-- 23&#45;&gt;35 -->\n<g id=\"edge37\" class=\"edge\">\n<title>23&#45;&gt;35</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1065.9906,-71.8314C1065.5628,-64.131 1065.0541,-54.9743 1064.5787,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"1068.0724,-46.2037 1064.023,-36.4133 1061.0831,-46.592 1068.0724,-46.2037\"/>\n</g>\n<!-- 36 -->\n<g id=\"node39\" class=\"node\">\n<title>36</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"1198,-36 1120,-36 1120,0 1198,0 1198,-36\"/>\n<text text-anchor=\"middle\" x=\"1159\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">[3, 2, 2, 1]</text>\n</g>\n<!-- 24&#45;&gt;36 -->\n<g id=\"edge38\" class=\"edge\">\n<title>24&#45;&gt;36</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M1156.0094,-71.8314C1156.4372,-64.131 1156.9459,-54.9743 1157.4213,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"1160.9169,-46.592 1157.977,-36.4133 1153.9276,-46.2037 1160.9169,-46.592\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 153
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2sHYXlHKUcnN",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from collections import Counter\n",
        "def permuteDup(nums, k):\n",
        "    ans = []\n",
        "    def permutate(d, n, k, curr, tracker):  \n",
        "      nonlocal ans \n",
        "      if d == k:\n",
        "          ans.append(curr)\n",
        "          return\n",
        "      for i in range(n):\n",
        "          if tracker[nums[i]] == 0:\n",
        "            #print('continue')\n",
        "            continue\n",
        "          if i - 1 >= 0 and nums[i] == nums[i-1]:\n",
        "              continue\n",
        "          tracker[nums[i]] -= 1\n",
        "          curr.append(nums[i])\n",
        "          #print(curr)\n",
        "          permutate(d+1, n, k, curr[:], tracker)\n",
        "          curr.pop()\n",
        "          tracker[nums[i]] += 1\n",
        "      return\n",
        "    \n",
        "    nums.sort()\n",
        "    permutate(0, len(nums), k, [], Counter(nums))\n",
        "    return ans\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tJUz6YWsX71M",
        "colab_type": "code",
        "outputId": "ae2e236c-dac1-45fb-c8c0-25984d02db9b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "nums = [1,2, 2, 3]\n",
        "ans = permuteDup(nums, 4)\n",
        "print(len(ans), ans)"
      ],
      "execution_count": 155,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "12 [[1, 2, 2, 3], [1, 2, 3, 2], [1, 3, 2, 2], [2, 1, 2, 3], [2, 1, 3, 2], [2, 2, 1, 3], [2, 2, 3, 1], [2, 3, 1, 2], [2, 3, 2, 1], [3, 1, 2, 2], [3, 2, 1, 2], [3, 2, 2, 1]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HikETMOQcM7H",
        "colab_type": "text"
      },
      "source": [
        "### Combination"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jHP31tpmjrod",
        "colab_type": "code",
        "outputId": "07b3cbd7-85be-4b83-eab3-947102fbd109",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 367
        }
      },
      "source": [
        "from graphviz import Digraph\n",
        "dot = Digraph(comment='The Round Table', format='png')\n",
        "dot.node_attr['shape']='box'\n",
        "#print(get_methods(Digraph))\n",
        "#print(Digraph.__dict__)\n",
        "nodes = ['{}', '{1}', '{2}', '{3}', '{1, 2}', '{1, 3}',  '{2, 3}',  '{1, 2, 3}']\n",
        "for i, node in enumerate(nodes):\n",
        "  dot.node(str(i), label=node)\n",
        "edges = [('0', '1'), ('0', '2'), ('0', '3'), ('1', '4'), ('1', '5'), ('2', '6'), ('4', '7')]\n",
        "for n1, n2 in edges:\n",
        "  dot.edge(n1, n2)\n",
        "dot.render('test-output/combination', view=True) \n",
        "dot"
      ],
      "execution_count": 156,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7fac751948d0>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: %3 Pages: 1 -->\n<svg width=\"285pt\" height=\"260pt\"\n viewBox=\"0.00 0.00 285.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\n<title>%3</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-256 281,-256 281,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"205,-252 151,-252 151,-216 205,-216 205,-252\"/>\n<text text-anchor=\"middle\" x=\"178\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">{}</text>\n</g>\n<!-- 1 -->\n<g id=\"node2\" class=\"node\">\n<title>1</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"133,-180 79,-180 79,-144 133,-144 133,-180\"/>\n<text text-anchor=\"middle\" x=\"106\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">{1}</text>\n</g>\n<!-- 0&#45;&gt;1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M159.8314,-215.8314C151.2848,-207.2848 140.9443,-196.9443 131.6198,-187.6198\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"133.9592,-185.0095 124.4133,-180.4133 129.0095,-189.9592 133.9592,-185.0095\"/>\n</g>\n<!-- 2 -->\n<g id=\"node3\" class=\"node\">\n<title>2</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"205,-180 151,-180 151,-144 205,-144 205,-180\"/>\n<text text-anchor=\"middle\" x=\"178\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">{2}</text>\n</g>\n<!-- 0&#45;&gt;2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>0&#45;&gt;2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M178,-215.8314C178,-208.131 178,-198.9743 178,-190.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"181.5001,-190.4132 178,-180.4133 174.5001,-190.4133 181.5001,-190.4132\"/>\n</g>\n<!-- 3 -->\n<g id=\"node4\" class=\"node\">\n<title>3</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"277,-180 223,-180 223,-144 277,-144 277,-180\"/>\n<text text-anchor=\"middle\" x=\"250\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">{3}</text>\n</g>\n<!-- 0&#45;&gt;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>0&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M196.1686,-215.8314C204.7152,-207.2848 215.0557,-196.9443 224.3802,-187.6198\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"226.9905,-189.9592 231.5867,-180.4133 222.0408,-185.0095 226.9905,-189.9592\"/>\n</g>\n<!-- 4 -->\n<g id=\"node5\" class=\"node\">\n<title>4</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"61,-108 7,-108 7,-72 61,-72 61,-108\"/>\n<text text-anchor=\"middle\" x=\"34\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">{1, 2}</text>\n</g>\n<!-- 1&#45;&gt;4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>1&#45;&gt;4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M87.8314,-143.8314C79.2848,-135.2848 68.9443,-124.9443 59.6198,-115.6198\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"61.9592,-113.0095 52.4133,-108.4133 57.0095,-117.9592 61.9592,-113.0095\"/>\n</g>\n<!-- 5 -->\n<g id=\"node6\" class=\"node\">\n<title>5</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"133,-108 79,-108 79,-72 133,-72 133,-108\"/>\n<text text-anchor=\"middle\" x=\"106\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">{1, 3}</text>\n</g>\n<!-- 1&#45;&gt;5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>1&#45;&gt;5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M106,-143.8314C106,-136.131 106,-126.9743 106,-118.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"109.5001,-118.4132 106,-108.4133 102.5001,-118.4133 109.5001,-118.4132\"/>\n</g>\n<!-- 6 -->\n<g id=\"node7\" class=\"node\">\n<title>6</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"205,-108 151,-108 151,-72 205,-72 205,-108\"/>\n<text text-anchor=\"middle\" x=\"178\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">{2, 3}</text>\n</g>\n<!-- 2&#45;&gt;6 -->\n<g id=\"edge6\" class=\"edge\">\n<title>2&#45;&gt;6</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M178,-143.8314C178,-136.131 178,-126.9743 178,-118.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"181.5001,-118.4132 178,-108.4133 174.5001,-118.4133 181.5001,-118.4132\"/>\n</g>\n<!-- 7 -->\n<g id=\"node8\" class=\"node\">\n<title>7</title>\n<polygon fill=\"none\" stroke=\"#000000\" points=\"68,-36 0,-36 0,0 68,0 68,-36\"/>\n<text text-anchor=\"middle\" x=\"34\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">{1, 2, 3}</text>\n</g>\n<!-- 4&#45;&gt;7 -->\n<g id=\"edge7\" class=\"edge\">\n<title>4&#45;&gt;7</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M34,-71.8314C34,-64.131 34,-54.9743 34,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"37.5001,-46.4132 34,-36.4133 30.5001,-46.4133 37.5001,-46.4132\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 156
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0EUTWhjmelaO",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def C_n_k(a, n, k, start, d, curr, ans):\n",
        "  '''\n",
        "  Implement combination of k items out  of n items\n",
        "  start: the start of candinate\n",
        "  depth: start from 0, and represent the depth of the search\n",
        "  curr: the current partial solution\n",
        "  ans: collect all the valide solutions\n",
        "  '''\n",
        "  if d == k: #end condition\n",
        "    ans.append(curr[::]) \n",
        "    return\n",
        "  \n",
        "  for i in range(start, n):    \n",
        "    # generate the next solution from curr\n",
        "    curr.append(a[i])\n",
        "    # move to the next solution\n",
        "    C_n_k(a, n, k, i+1, d+1, curr, ans)\n",
        "\n",
        "    #backtrack to previous partial state\n",
        "    curr.pop()\n",
        "  return"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vmciVqqygk05",
        "colab_type": "code",
        "outputId": "5b577292-4401-43f6-a68f-6cb048be50b0",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "a = [1, 2, 3]\n",
        "n = len(a)\n",
        "ans = []\n",
        "a.sort()\n",
        "C_n_k(a, n, 2, 0, 0, [], ans)\n",
        "print(ans, a)"
      ],
      "execution_count": 158,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[1, 2], [1, 3], [2, 3]] [1, 2, 3]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ILlyV3Nt1KBZ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def powerset(a, n, d, curr, ans):\n",
        "  if d == n:\n",
        "    ans.append(curr[::]) \n",
        "    return\n",
        "\n",
        "  # Case 1: select item\n",
        "  curr.append(a[d])\n",
        "  powerset(a, n, d + 1, curr, ans)\n",
        "  # Case 2: not select item\n",
        "  curr.pop()\n",
        "  powerset(a, n, d + 1, curr, ans)\n",
        "  return"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wLPuCCfF-wTv",
        "colab_type": "code",
        "outputId": "e205ec65-c371-4e9e-ee62-5dbb7de9342e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "a = [1, 2, 3]\n",
        "n = len(a)\n",
        "ans = []\n",
        "powerset(a, n, 0, [], ans)\n",
        "ans"
      ],
      "execution_count": 160,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 160
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YV37efjrdJCM",
        "colab_type": "text"
      },
      "source": [
        "#### Questions to ponder\n",
        "1. What if there are duplicates in the input list? How to count and how to enumerate all possible combinations? [1, 2, 3, 2]\n",
        "\n",
        "\n",
        "Take the product of all the (frequencies + 1).\n",
        "\n",
        "For example, in {A,B,B}, the answer is (1+1) [the number of As] * (2+1) [the number of Bs] = 6.\n",
        "\n",
        "In the second example, count(A) = 2 and count(B) = 2. Thus the answer is (2+1) * (2+1) = 9.\n",
        "\n",
        "The reason this works is that you can define any subset as a vector of counts - for {A,B,B}, the subsets can be described as {A=0,B=0}, {A=0,B=1}, {0,2}, {1,0}, {1,1}, {1,2}.\n",
        "\n",
        "For each number in counts[] there are (frequencies of that object + 1) possible values. (0..frequencies)\n",
        "\n",
        "Therefore, the total number of possiblities is the product of all (frequencies+1).\n",
        "\n",
        "The \"all unique\" case can also be explained this way - there is one occurence of each object, so the answer is (1+1)^|S| = 2^|S|.\n",
        "\n",
        "However, how to count the case of $c(n, k)$? Assume we have $m$ unqiue items, and the frequency of each is marked as $x_i$, with $\\sum_{i=0}^{m-1}x_i = n$. \n",
        "\\begin{align}\n",
        "\\sum_{k=0}^{n} c(n, k) = \\prod_{i=0}^{m-1}(x_i + 1)\n",
        "\\end{align}\n",
        "\n",
        "When the maximum of $k$ is 0.\n",
        "\\begin{align}\n",
        "\\sum_{k=0}^{0} c(n, k) = \\prod_{i=0}^{m-1}(1) = 1\n",
        "\\end{align}\n",
        "\n",
        "When the maximum of $k$ is 1.\n",
        "\\begin{align}\n",
        "\\sum_{k=0}^{1} c(n, k) = \\prod_{i=0}^{m-1}(1) = 1\n",
        "\\end{align}\n",
        "\n",
        "We list each as follows:\n",
        "```\n",
        "c(n,0)\n",
        "```\n",
        "\n",
        "Notes:\n",
        "* http://www.math.ucsd.edu/~ebender/CombText/ch-1.pdf\n",
        "* https://math.stackexchange.com/questions/1506536/counting-tuples-with-repetitions\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fcIaL7i7-9na",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def C_n_k(a, n, k, start, depth, curr, ans):\n",
        "  '''\n",
        "  Implement combination of k items out  of n items\n",
        "  start: the start of candinate\n",
        "  depth: start from 0, and represent the depth of the search\n",
        "  curr: the current partial solution\n",
        "  ans: collect all the valide solutions\n",
        "  '''\n",
        "  ans.append(curr[::])\n",
        "  if depth == k: #end condition\n",
        "    return\n",
        "  \n",
        "  for i in range(start, n): \n",
        "    if i - 1 >= start and a[i] == a[i-1]:\n",
        "              continue   \n",
        "    # generate the next solution from curr\n",
        "    curr.append(a[i])\n",
        "    # move to the next solution\n",
        "    C_n_k(a, n, k, i+1, depth+1, curr, ans)\n",
        "    curr.pop()\n",
        "  return"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FQlAWNcp8-5y",
        "colab_type": "code",
        "outputId": "893cf451-50eb-4a26-a3e9-91331bc1b18c",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 256
        }
      },
      "source": [
        "a = [1, 2, 3, 2]\n",
        "n = len(a)\n",
        "ans = [[None]]\n",
        "ans = []\n",
        "a.sort()\n",
        "C_n_k(a, n, 4, 0, 0, [], ans)\n",
        "ans, len(ans)"
      ],
      "execution_count": 162,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "([[],\n",
              "  [1],\n",
              "  [1, 2],\n",
              "  [1, 2, 2],\n",
              "  [1, 2, 2, 3],\n",
              "  [1, 2, 3],\n",
              "  [1, 3],\n",
              "  [2],\n",
              "  [2, 2],\n",
              "  [2, 2, 3],\n",
              "  [2, 3],\n",
              "  [3]],\n",
              " 12)"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 162
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "f7xml9ay0bAm",
        "colab_type": "text"
      },
      "source": [
        "### More Combinatorics"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ze7L-ttOgCUd",
        "colab_type": "text"
      },
      "source": [
        "#### All paths"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jYkhLKk9QZqi",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def all_paths(g, s, path, ans):\n",
        "  '''generate all pahts with backtrack'''\n",
        "  ans.append(path[::])\n",
        "  for v in g[s]:\n",
        "    path.append(v)\n",
        "    print(path)\n",
        "    all_paths(g, v, path, ans)\n",
        "    path.pop()\n",
        "    print(path, 'backtrack')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "84vSh1JIQyLH",
        "colab_type": "code",
        "outputId": "91bbd82e-e03e-4313-c99b-3950465ee2e0",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "al = [[1, 2], [2, 3, 4], [5], [], [], []]\n",
        "print(al)"
      ],
      "execution_count": 164,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[1, 2], [2, 3, 4], [5], [], [], []]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5ILbY1zOl3OZ",
        "colab_type": "code",
        "outputId": "bad37d1a-ad23-4623-d1a5-297db9ed8f03",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 271
        }
      },
      "source": [
        "dot = Digraph(comment='The Round Table', format='png')\n",
        "nodes = range(len(al))\n",
        "for idx, neighbors in enumerate(al):\n",
        "  for n in neighbors:\n",
        "      dot.edge(str(idx), str(n))\n",
        "rank1 = [0]\n",
        "rank2 = [1, 2]\n",
        "rank3 = [3, 4, 5]\n",
        "for rank in [rank1, rank2, rank3]:\n",
        "  with dot.subgraph() as s:\n",
        "    s.attr(rank='same')\n",
        "    for node in rank:\n",
        "      s.node(str(node))\n",
        "dot.render('test-output/all_path_demo', view=True) \n",
        "dot"
      ],
      "execution_count": 165,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Digraph at 0x7fac7519dd30>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: %3 Pages: 1 -->\n<svg width=\"206pt\" height=\"188pt\"\n viewBox=\"0.00 0.00 206.00 188.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 184)\">\n<title>%3</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-184 202,-184 202,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"135\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"135\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n</g>\n<!-- 1 -->\n<g id=\"node2\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 0&#45;&gt;1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M126.2854,-144.5708C122.0403,-136.0807 116.8464,-125.6929 112.1337,-116.2674\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"115.237,-114.6477 107.6343,-107.2687 108.976,-117.7782 115.237,-114.6477\"/>\n</g>\n<!-- 2 -->\n<g id=\"node3\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 0&#45;&gt;2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>0&#45;&gt;2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M143.7146,-144.5708C147.9597,-136.0807 153.1536,-125.6929 157.8663,-116.2674\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"161.024,-117.7782 162.3657,-107.2687 154.763,-114.6477 161.024,-117.7782\"/>\n</g>\n<!-- 1&#45;&gt;2 -->\n<g id=\"edge3\" class=\"edge\">\n<title>1&#45;&gt;2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M126,-90C128.6147,-90 131.2295,-90 133.8442,-90\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"133.9297,-93.5001 143.9297,-90 133.9297,-86.5001 133.9297,-93.5001\"/>\n</g>\n<!-- 3 -->\n<g id=\"node4\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 1&#45;&gt;3 -->\n<g id=\"edge4\" class=\"edge\">\n<title>1&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M83.7307,-74.7307C73.803,-64.803 60.6847,-51.6847 49.5637,-40.5637\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"51.7933,-37.8436 42.2473,-33.2473 46.8436,-42.7933 51.7933,-37.8436\"/>\n</g>\n<!-- 4 -->\n<g id=\"node5\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 1&#45;&gt;4 -->\n<g id=\"edge5\" class=\"edge\">\n<title>1&#45;&gt;4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M99,-71.8314C99,-64.131 99,-54.9743 99,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"102.5001,-46.4132 99,-36.4133 95.5001,-46.4133 102.5001,-46.4132\"/>\n</g>\n<!-- 5 -->\n<g id=\"node6\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"171\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n</g>\n<!-- 2&#45;&gt;5 -->\n<g id=\"edge6\" class=\"edge\">\n<title>2&#45;&gt;5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M171,-71.8314C171,-64.131 171,-54.9743 171,-46.4166\"/>\n<polygon fill=\"#000000\" stroke=\"#000000\" points=\"174.5001,-46.4132 171,-36.4133 167.5001,-46.4133 174.5001,-46.4132\"/>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 165
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HhBVClwEVeUJ",
        "colab_type": "code",
        "outputId": "6f50820c-c436-4201-f066-6aff0d613198",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 293
        }
      },
      "source": [
        "ans = []\n",
        "path = [0]\n",
        "all_paths(al, 0, path, ans)\n",
        "for path in ans:\n",
        "  path = [str(i) for i in path]\n",
        "  print('->'.join(path), end = ', ')"
      ],
      "execution_count": 166,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[0, 1]\n",
            "[0, 1, 2]\n",
            "[0, 1, 2, 5]\n",
            "[0, 1, 2] backtrack\n",
            "[0, 1] backtrack\n",
            "[0, 1, 3]\n",
            "[0, 1] backtrack\n",
            "[0, 1, 4]\n",
            "[0, 1] backtrack\n",
            "[0] backtrack\n",
            "[0, 2]\n",
            "[0, 2, 5]\n",
            "[0, 2] backtrack\n",
            "[0] backtrack\n",
            "0, 0->1, 0->1->2, 0->1->2->5, 0->1->3, 0->1->4, 0->2, 0->2->5, "
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EK22ibhQ3SYy",
        "colab_type": "text"
      },
      "source": [
        "#### Subsequences\n",
        "\n",
        "* Sequence is unique\n",
        "* String has repetition: 940. Distinct Subsequences II\n",
        "\n",
        "The enumeration with backtacking is quite similar to the combination, other than in the case with repetition. In our previous implementation of enumerating unique combinations when there are duplciates in the input, we have sorted the items, making the checking of repetition of choices as simple as checking the precessor. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "y0h_GMlhEw55",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#Counting\n",
        " def distinctSubseqII(S):\n",
        "    dp = [1]\n",
        "    last = {}\n",
        "    for i, x in enumerate(S):\n",
        "        dp.append(dp[-1] * 2)\n",
        "        if x in last:\n",
        "            dp[-1] -= dp[last[x]]\n",
        "        last[x] = i\n",
        "\n",
        "    return (dp[-1] - 1) % (10**9 + 7)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AfYxiTuTE2FN",
        "colab_type": "code",
        "outputId": "72d83f88-aa0d-49c3-8488-008e40249cea",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "S = 'abaab'\n",
        "distinctSubseqII(S)"
      ],
      "execution_count": 168,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "17"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 168
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bITdk__o4X82",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#Enumerating\n",
        "def check_repetition(start, i, a):\n",
        "  for j in range(start, i):\n",
        "    if a[i] == a[j]:\n",
        "      return True\n",
        "  return False\n",
        "\n",
        "def subseqs(a, n, start, curr, ans):\n",
        "  ans.append(''.join(curr[::])) \n",
        "  if start == n: \n",
        "    return\n",
        "  \n",
        "  for i in range(start, n):  \n",
        "    if check_repetition(start, i, a):\n",
        "      continue    \n",
        "    curr.append(a[i])\n",
        "    subseqs(a, n, i+1, curr, ans)\n",
        "    curr.pop()\n",
        "  return"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EE7tL51_4t-E",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from graphviz import Graph\n",
        "dot = Graph(comment='The Round Table', format='png')\n",
        "dot.node_attr['shape']='ellipse'\n",
        "dot.node('0', label='<\\'\\''+'<FONT POINT-SIZE=\"12\">, s={}</FONT>>'.format(0))\n",
        "count = 0\n",
        "\n",
        "def subseqs(a, n, start, curr, ans, node_label):\n",
        "  global count\n",
        "  ans.append(''.join(curr[::])) \n",
        "  if start == n: \n",
        "    return\n",
        "  \n",
        "  for i in range(start, n):  \n",
        "    node = curr + [a[i]]\n",
        "    count += 1\n",
        "    dot.node(str(count), label='<\\''+''.join(node)+'\\''+'<FONT POINT-SIZE=\"12\">, s={}</FONT>>'.format(i+1))\n",
        "    dot.edge(node_label, str(count), _attributes={ 'label':'i={}'.format(i)})\n",
        "    if check_repetition(start, i, a):\n",
        "      dot.node(str(count), label='\\''+''.join(node)+'\\'', _attributes={'color': 'red'})\n",
        "      continue   \n",
        "    curr.append(a[i])\n",
        "    subseqs(a, n, i+1, curr, ans, str(count))\n",
        "    curr.pop()\n",
        "    #count -= 1\n",
        "  return"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NVkaCP2C3py4",
        "colab_type": "code",
        "outputId": "c5b3e660-64cb-47fa-f242-1a2b89bc075b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 562
        }
      },
      "source": [
        "S = '1232'\n",
        "ans = []\n",
        "subseqs(list(S), len(S), 0,  [], ans, '0')\n",
        "print(len(ans), ans)\n",
        "dot.render('test-output/subsequence', view=True) \n",
        "dot"
      ],
      "execution_count": 171,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "14 ['', '1', '12', '123', '1232', '122', '13', '132', '2', '23', '232', '22', '3', '32']\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Graph at 0x7fac7514ca90>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: %3 Pages: 1 -->\n<svg width=\"663pt\" height=\"392pt\"\n viewBox=\"0.00 0.00 662.74 392.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 388)\">\n<title>%3</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-388 658.7422,-388 658.7422,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"494.7457\" cy=\"-366\" rx=\"29.4969\" ry=\"18\"/>\n<text text-anchor=\"start\" x=\"480.2457\" y=\"-363.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">&#39;&#39;</text>\n<text text-anchor=\"start\" x=\"485.2457\" y=\"-363.3\" font-family=\"Times,serif\" font-size=\"12.00\" fill=\"#000000\">, s=0</text>\n</g>\n<!-- 1 -->\n<g id=\"node2\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"333.7457\" cy=\"-279\" rx=\"34.394\" ry=\"18\"/>\n<text text-anchor=\"start\" x=\"315.2457\" y=\"-276.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">&#39;1&#39;</text>\n<text text-anchor=\"start\" x=\"328.2457\" y=\"-276.3\" font-family=\"Times,serif\" font-size=\"12.00\" fill=\"#000000\">, s=1</text>\n</g>\n<!-- 0&#45;&#45;1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&#45;1</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M472.6969,-354.0854C442.6407,-337.8439 388.9981,-308.8569 357.8891,-292.0465\"/>\n<text text-anchor=\"middle\" x=\"434.7457\" y=\"-318.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">i=0</text>\n</g>\n<!-- 9 -->\n<g id=\"node10\" class=\"node\">\n<title>9</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"440.7457\" cy=\"-279\" rx=\"34.394\" ry=\"18\"/>\n<text text-anchor=\"start\" x=\"422.2457\" y=\"-276.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">&#39;2&#39;</text>\n<text text-anchor=\"start\" x=\"435.2457\" y=\"-276.3\" font-family=\"Times,serif\" font-size=\"12.00\" fill=\"#000000\">, s=2</text>\n</g>\n<!-- 0&#45;&#45;9 -->\n<g id=\"edge9\" class=\"edge\">\n<title>0&#45;&#45;9</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M484.077,-348.8116C474.6101,-333.5593 460.8524,-311.3942 451.3922,-296.1527\"/>\n<text text-anchor=\"middle\" x=\"481.7457\" y=\"-318.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">i=1</text>\n</g>\n<!-- 13 -->\n<g id=\"node14\" class=\"node\">\n<title>13</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"527.7457\" cy=\"-279\" rx=\"34.394\" ry=\"18\"/>\n<text text-anchor=\"start\" x=\"509.2457\" y=\"-276.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">&#39;3&#39;</text>\n<text text-anchor=\"start\" x=\"522.2457\" y=\"-276.3\" font-family=\"Times,serif\" font-size=\"12.00\" fill=\"#000000\">, s=3</text>\n</g>\n<!-- 0&#45;&#45;13 -->\n<g id=\"edge13\" class=\"edge\">\n<title>0&#45;&#45;13</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M501.4237,-348.3943C507.1114,-333.3994 515.2472,-311.9505 520.9643,-296.8782\"/>\n<text text-anchor=\"middle\" x=\"523.7457\" y=\"-318.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">i=2</text>\n</g>\n<!-- 15 -->\n<g id=\"node16\" class=\"node\">\n<title>15</title>\n<ellipse fill=\"none\" stroke=\"#ff0000\" cx=\"606.7457\" cy=\"-279\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"606.7457\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">&#39;2&#39;</text>\n</g>\n<!-- 0&#45;&#45;15 -->\n<g id=\"edge15\" class=\"edge\">\n<title>0&#45;&#45;15</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M513.2402,-351.6337C534.2405,-335.321 568.2641,-308.8919 588.9641,-292.8124\"/>\n<text text-anchor=\"middle\" x=\"567.7457\" y=\"-318.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">i=3</text>\n</g>\n<!-- 2 -->\n<g id=\"node3\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"154.7457\" cy=\"-192\" rx=\"38.9931\" ry=\"18\"/>\n<text text-anchor=\"start\" x=\"132.7457\" y=\"-189.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">&#39;12&#39;</text>\n<text text-anchor=\"start\" x=\"152.7457\" y=\"-189.3\" font-family=\"Times,serif\" font-size=\"12.00\" fill=\"#000000\">, s=2</text>\n</g>\n<!-- 1&#45;&#45;2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>1&#45;&#45;2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M308.479,-266.7195C274.9422,-250.4195 215.9735,-221.7588 181.6376,-205.0704\"/>\n<text text-anchor=\"middle\" x=\"265.7457\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">i=1</text>\n</g>\n<!-- 6 -->\n<g id=\"node7\" class=\"node\">\n<title>6</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"255.7457\" cy=\"-192\" rx=\"38.9931\" ry=\"18\"/>\n<text text-anchor=\"start\" x=\"233.7457\" y=\"-189.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">&#39;13&#39;</text>\n<text text-anchor=\"start\" x=\"253.7457\" y=\"-189.3\" font-family=\"Times,serif\" font-size=\"12.00\" fill=\"#000000\">, s=3</text>\n</g>\n<!-- 1&#45;&#45;6 -->\n<g id=\"edge6\" class=\"edge\">\n<title>1&#45;&#45;6</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M319.0745,-262.636C305.3058,-247.2786 284.8013,-224.4082 270.8831,-208.8841\"/>\n<text text-anchor=\"middle\" x=\"309.7457\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">i=2</text>\n</g>\n<!-- 8 -->\n<g id=\"node9\" class=\"node\">\n<title>8</title>\n<ellipse fill=\"none\" stroke=\"#ff0000\" cx=\"339.7457\" cy=\"-192\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"339.7457\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">&#39;12&#39;</text>\n</g>\n<!-- 1&#45;&#45;8 -->\n<g id=\"edge8\" class=\"edge\">\n<title>1&#45;&#45;8</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M334.9889,-260.9735C336.0186,-246.0422 337.4748,-224.9283 338.5041,-210.0034\"/>\n<text text-anchor=\"middle\" x=\"347.7457\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">i=3</text>\n</g>\n<!-- 3 -->\n<g id=\"node4\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"48.7457\" cy=\"-105\" rx=\"44.393\" ry=\"18\"/>\n<text text-anchor=\"start\" x=\"22.7457\" y=\"-102.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">&#39;123&#39;</text>\n<text text-anchor=\"start\" x=\"50.7457\" y=\"-102.3\" font-family=\"Times,serif\" font-size=\"12.00\" fill=\"#000000\">, s=3</text>\n</g>\n<!-- 2&#45;&#45;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>2&#45;&#45;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M135.3036,-176.0429C116.2974,-160.4434 87.5101,-136.8161 68.4234,-121.1506\"/>\n<text text-anchor=\"middle\" x=\"118.7457\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">i=2</text>\n</g>\n<!-- 5 -->\n<g id=\"node6\" class=\"node\">\n<title>5</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"154.7457\" cy=\"-105\" rx=\"44.393\" ry=\"18\"/>\n<text text-anchor=\"start\" x=\"128.7457\" y=\"-102.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">&#39;122&#39;</text>\n<text text-anchor=\"start\" x=\"156.7457\" y=\"-102.3\" font-family=\"Times,serif\" font-size=\"12.00\" fill=\"#000000\">, s=4</text>\n</g>\n<!-- 2&#45;&#45;5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>2&#45;&#45;5</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M154.7457,-173.9735C154.7457,-159.0422 154.7457,-137.9283 154.7457,-123.0034\"/>\n<text text-anchor=\"middle\" x=\"164.7457\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">i=3</text>\n</g>\n<!-- 4 -->\n<g id=\"node5\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"48.7457\" cy=\"-18\" rx=\"48.9926\" ry=\"18\"/>\n<text text-anchor=\"start\" x=\"19.2457\" y=\"-15.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">&#39;1232&#39;</text>\n<text text-anchor=\"start\" x=\"54.2457\" y=\"-15.3\" font-family=\"Times,serif\" font-size=\"12.00\" fill=\"#000000\">, s=4</text>\n</g>\n<!-- 3&#45;&#45;4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>3&#45;&#45;4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M48.7457,-86.9735C48.7457,-72.0422 48.7457,-50.9283 48.7457,-36.0034\"/>\n<text text-anchor=\"middle\" x=\"58.7457\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">i=3</text>\n</g>\n<!-- 7 -->\n<g id=\"node8\" class=\"node\">\n<title>7</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"260.7457\" cy=\"-105\" rx=\"44.393\" ry=\"18\"/>\n<text text-anchor=\"start\" x=\"234.7457\" y=\"-102.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">&#39;132&#39;</text>\n<text text-anchor=\"start\" x=\"262.7457\" y=\"-102.3\" font-family=\"Times,serif\" font-size=\"12.00\" fill=\"#000000\">, s=4</text>\n</g>\n<!-- 6&#45;&#45;7 -->\n<g id=\"edge7\" class=\"edge\">\n<title>6&#45;&#45;7</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M256.7817,-173.9735C257.6398,-159.0422 258.8532,-137.9283 259.711,-123.0034\"/>\n<text text-anchor=\"middle\" x=\"268.7457\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">i=3</text>\n</g>\n<!-- 10 -->\n<g id=\"node11\" class=\"node\">\n<title>10</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"423.7457\" cy=\"-192\" rx=\"38.9931\" ry=\"18\"/>\n<text text-anchor=\"start\" x=\"401.7457\" y=\"-189.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">&#39;23&#39;</text>\n<text text-anchor=\"start\" x=\"421.7457\" y=\"-189.3\" font-family=\"Times,serif\" font-size=\"12.00\" fill=\"#000000\">, s=3</text>\n</g>\n<!-- 9&#45;&#45;10 -->\n<g id=\"edge10\" class=\"edge\">\n<title>9&#45;&#45;10</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M437.2233,-260.9735C434.3056,-246.0422 430.1799,-224.9283 427.2636,-210.0034\"/>\n<text text-anchor=\"middle\" x=\"443.7457\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">i=2</text>\n</g>\n<!-- 12 -->\n<g id=\"node13\" class=\"node\">\n<title>12</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"519.7457\" cy=\"-192\" rx=\"38.9931\" ry=\"18\"/>\n<text text-anchor=\"start\" x=\"497.7457\" y=\"-189.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">&#39;22&#39;</text>\n<text text-anchor=\"start\" x=\"517.7457\" y=\"-189.3\" font-family=\"Times,serif\" font-size=\"12.00\" fill=\"#000000\">, s=4</text>\n</g>\n<!-- 9&#45;&#45;12 -->\n<g id=\"edge12\" class=\"edge\">\n<title>9&#45;&#45;12</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M455.605,-262.636C469.5501,-247.2786 490.3175,-224.4082 504.4141,-208.8841\"/>\n<text text-anchor=\"middle\" x=\"495.7457\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">i=3</text>\n</g>\n<!-- 11 -->\n<g id=\"node12\" class=\"node\">\n<title>11</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"423.7457\" cy=\"-105\" rx=\"44.393\" ry=\"18\"/>\n<text text-anchor=\"start\" x=\"397.7457\" y=\"-102.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">&#39;232&#39;</text>\n<text text-anchor=\"start\" x=\"425.7457\" y=\"-102.3\" font-family=\"Times,serif\" font-size=\"12.00\" fill=\"#000000\">, s=4</text>\n</g>\n<!-- 10&#45;&#45;11 -->\n<g id=\"edge11\" class=\"edge\">\n<title>10&#45;&#45;11</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M423.7457,-173.9735C423.7457,-159.0422 423.7457,-137.9283 423.7457,-123.0034\"/>\n<text text-anchor=\"middle\" x=\"433.7457\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">i=3</text>\n</g>\n<!-- 14 -->\n<g id=\"node15\" class=\"node\">\n<title>14</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"615.7457\" cy=\"-192\" rx=\"38.9931\" ry=\"18\"/>\n<text text-anchor=\"start\" x=\"593.7457\" y=\"-189.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">&#39;32&#39;</text>\n<text text-anchor=\"start\" x=\"613.7457\" y=\"-189.3\" font-family=\"Times,serif\" font-size=\"12.00\" fill=\"#000000\">, s=4</text>\n</g>\n<!-- 13&#45;&#45;14 -->\n<g id=\"edge14\" class=\"edge\">\n<title>13&#45;&#45;14</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M543.8862,-263.0429C559.5658,-247.5415 583.2636,-224.1129 599.1095,-208.4471\"/>\n<text text-anchor=\"middle\" x=\"587.7457\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">i=3</text>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 171
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "p2UCSXkM3TQK",
        "colab_type": "text"
      },
      "source": [
        "#### Partition"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7kLQciZ1Zt2i",
        "colab_type": "text"
      },
      "source": [
        "## Constraint Satisfaction Problems with Backtracking and Pruning"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4vOhZxglCBKD",
        "colab_type": "text"
      },
      "source": [
        "### Sudoku Solver\n",
        "[Search space](https://www.researchgate.net/publication/264572573_Sudoku_Puzzle_Complexity)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oHsib-ORB9Fh",
        "colab_type": "text"
      },
      "source": [
        "First, we build up the board"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wU0IzGC8_EiP",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "board = [[5, 3, None, None, 7, None, None, None, None],\n",
        "         [6, None, None, 1, 9, 5, None, None, None],\n",
        "         [None, 9, 8, None, None, None, None, 6, None],\n",
        "         [8, None, None, None, 6, None, None, None, 3], \n",
        "         [4, None, None, 8, None, 3, None, None, 1], \n",
        "         [7, None, None, None, 2, None, None, None, 6], \n",
        "         [None, 6, None, None, None, None, 2, 8, None], \n",
        "         [None, None, None, 4, 1, 9, None, None, 5],\n",
        "         [None, None, None, None, 8, None, None, 7, 9]]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Psq2cedrMTGJ",
        "colab_type": "text"
      },
      "source": [
        "Define how to change the state"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "t2oeCmmvCotc",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def setState(i, j, v, row_state, col_state, grid_state):\n",
        "  row_state[i] |= 1 << v\n",
        "  col_state[j] |= 1 << v\n",
        "  grid_index = (i//3)*3 + (j//3)\n",
        "  grid_state[grid_index] |= 1 << v\n",
        "  \n",
        "def resetState(i, j, v, row_state, col_state, grid_state):\n",
        "  row_state[i] &= ~(1 << v)\n",
        "  col_state[j] &= ~(1 << v)\n",
        "  grid_index = (i//3)*3 + (j//3)\n",
        "  grid_state[grid_index] &= ~(1 << v)\n",
        "  \n",
        "def checkState(i, j, v, row_state, col_state, grid_state):\n",
        "  row_bit = (1 << v) & row_state[i] != 0\n",
        "  col_bit = (1 << v) & col_state[j]  != 0\n",
        "  grid_index = (i//3)*3 + (j//3)\n",
        "  grid_bit = (1 << v) & grid_state[grid_index]  != 0\n",
        "  return not row_bit and not col_bit and not grid_bit"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SgghNi99MWXw",
        "colab_type": "text"
      },
      "source": [
        "Get the empty spots and its values"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "v0IZMZHU5FR-",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        " def getEmptySpots(board, rows, cols, row_state, col_state, grid_state): \n",
        "    ''' get empty spots and find its corresponding values in O(n*n)'''\n",
        "    empty_spots = {}\n",
        "    # initialize the state, and get empty spots\n",
        "    for i in range(rows):\n",
        "      for j in range(cols):\n",
        "        if board[i][j]:\n",
        "            # set that bit to 1\n",
        "            setState(i, j, board[i][j]-1, row_state, col_state, grid_state)          \n",
        "        else:\n",
        "            empty_spots[(i,j)] = []\n",
        "                    \n",
        "    # get possible values for each spot\n",
        "    for i, j in empty_spots.keys():\n",
        "      for v in range(9):\n",
        "        if checkState(i, j, v, row_state, col_state, grid_state):\n",
        "          empty_spots[(i, j)].append(v+1)\n",
        "          \n",
        "    return empty_spots"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "39DSr_mfCBrQ",
        "colab_type": "text"
      },
      "source": [
        "Second, we intialize the state and find empty spots. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "G76l_z6DAk4n",
        "colab_type": "code",
        "outputId": "3b1d1039-2376-4a98-cebb-5c6c7bf3ba34",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 74
        }
      },
      "source": [
        "# initialize state\n",
        "row_state = [0]*9\n",
        "col_state = [0]*9\n",
        "grid_state = [0]*9\n",
        "\n",
        "empty_spots = getEmptySpots(board, 9, 9, row_state, col_state, grid_state)\n",
        "print(row_state, col_state, grid_state) \n",
        "sorted_empty_spots = sorted(empty_spots.items(), key=lambda x: len(x[1]))\n",
        "print(sorted_empty_spots)"
      ],
      "execution_count": 175,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[84, 305, 416, 164, 141, 98, 162, 281, 448] [248, 292, 128, 137, 483, 276, 2, 224, 309] [436, 337, 32, 200, 166, 37, 32, 393, 466]\n",
            "[((4, 4), [5]), ((6, 5), [7]), ((6, 8), [4]), ((7, 7), [3]), ((0, 3), [2, 6]), ((2, 0), [1, 2]), ((2, 3), [2, 3]), ((2, 4), [3, 4]), ((2, 5), [2, 4]), ((4, 1), [2, 5]), ((5, 1), [1, 5]), ((5, 3), [5, 9]), ((5, 5), [1, 4]), ((6, 4), [3, 5]), ((7, 0), [2, 3]), ((7, 6), [3, 6]), ((8, 5), [2, 6]), ((0, 2), [1, 2, 4]), ((0, 8), [2, 4, 8]), ((1, 1), [2, 4, 7]), ((1, 2), [2, 4, 7]), ((1, 7), [2, 3, 4]), ((2, 8), [2, 4, 7]), ((3, 1), [1, 2, 5]), ((3, 3), [5, 7, 9]), ((3, 5), [1, 4, 7]), ((4, 6), [5, 7, 9]), ((4, 7), [2, 5, 9]), ((5, 7), [4, 5, 9]), ((6, 0), [1, 3, 9]), ((6, 3), [3, 5, 7]), ((7, 1), [2, 7, 8]), ((7, 2), [2, 3, 7]), ((8, 0), [1, 2, 3]), ((0, 5), [2, 4, 6, 8]), ((0, 6), [1, 4, 8, 9]), ((0, 7), [1, 2, 4, 9]), ((1, 6), [3, 4, 7, 8]), ((1, 8), [2, 4, 7, 8]), ((3, 2), [1, 2, 5, 9]), ((3, 6), [4, 5, 7, 9]), ((3, 7), [2, 4, 5, 9]), ((4, 2), [2, 5, 6, 9]), ((5, 2), [1, 3, 5, 9]), ((5, 6), [4, 5, 8, 9]), ((8, 1), [1, 2, 4, 5]), ((8, 3), [2, 3, 5, 6]), ((8, 6), [1, 3, 4, 6]), ((2, 6), [1, 3, 4, 5, 7]), ((8, 2), [1, 2, 3, 4, 5]), ((6, 2), [1, 3, 4, 5, 7, 9])]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jUPMX4-jF7N_",
        "colab_type": "text"
      },
      "source": [
        "Traverse the empty_spots, and fill in. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ved6mk_0F6F-",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def dfs_backtrack(empty_spots, index):\n",
        "  if index == len(empty_spots):\n",
        "    return True\n",
        "  (i, j), vl = empty_spots[index]\n",
        "  \n",
        "  for v in vl: #try each value\n",
        "    # check the state\n",
        "    if checkState(i, j, v-1, row_state, col_state, grid_state):\n",
        "      # set the state\n",
        "      setState(i, j, v-1, row_state, col_state, grid_state)\n",
        "      # mark the board\n",
        "      board[i][j] = v\n",
        "      if dfs_backtrack(empty_spots, index+1):\n",
        "        return True\n",
        "      else:\n",
        "        #backtack to previouse state\n",
        "        resetState(i, j, v-1, row_state, col_state, grid_state)\n",
        "        #unmark the board\n",
        "        board[i][j] = None\n",
        "  return False"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qJAi11amrwf3",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from graphviz import Digraph\n",
        "dot = Digraph(comment='The Round Table', format='png')\n",
        "dot.node_attr['shape']='ellipse'\n",
        "dot.node(str((-1, -1)), label=str((-1, -1)))\n",
        "count = 0\n",
        "def dfs_backtrack(empty_spots, index, last_node):\n",
        "  global count\n",
        "  if index == len(empty_spots):\n",
        "    return True\n",
        "  (i, j), vl = empty_spots[index]\n",
        "  ni, nj = -1, -1\n",
        "  if index + 1 < len(empty_spots):\n",
        "    (ni, nj), nvl = empty_spots[index + 1]\n",
        "\n",
        "  for v in vl: #try each value\n",
        "    # check the state\n",
        "    if checkState(i, j, v-1, row_state, col_state, grid_state):\n",
        "\n",
        "      cur_node = str((ni, nj, v))\n",
        "      dot.node(str((ni, nj, v)), label=str((ni, nj))) # label shows, first is index\n",
        "      dot.edge(last_node, str((ni, nj, v)), label=str(v))\n",
        "      # set the state\n",
        "      setState(i, j, v-1, row_state, col_state, grid_state)\n",
        "      # mark the board\n",
        "      board[i][j] = v\n",
        "      if dfs_backtrack(empty_spots, index+1, cur_node):\n",
        "        count -= 1\n",
        "        return True\n",
        "      else:\n",
        "        #backtack to previouse state\n",
        "        count -= 1\n",
        "        resetState(i, j, v-1, row_state, col_state, grid_state)\n",
        "        dot.edge(str((ni, nj, v)), last_node, label=str(v), _attributes={'color': 'red'})\n",
        "        #unmark the board\n",
        "        board[i][j] = None\n",
        "  return False"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QUr5dZQxIpdn",
        "colab_type": "code",
        "outputId": "f67adef0-a0e6-4202-c003-d69fd841843f",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 74
        }
      },
      "source": [
        "ans = dfs_backtrack(sorted_empty_spots, 0, str((-1, -1)))\n",
        "print(ans)\n",
        "print(board)\n",
        "# dot.render('test-output/sudoku_search_tree', view=True) \n",
        "# dot"
      ],
      "execution_count": 178,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "True\n",
            "[[5, 3, 4, 6, 7, 8, 9, 1, 2], [6, 7, 2, 1, 9, 5, 3, 4, 8], [1, 9, 8, 3, 4, 2, 5, 6, 7], [8, 5, 9, 7, 6, 1, 4, 2, 3], [4, 2, 6, 8, 5, 3, 7, 9, 1], [7, 1, 3, 9, 2, 4, 8, 5, 6], [9, 6, 1, 5, 3, 7, 2, 8, 4], [2, 8, 7, 4, 1, 9, 6, 3, 5], [3, 4, 5, 2, 8, 6, 1, 7, 9]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RUfbZmY1xmbw",
        "colab_type": "text"
      },
      "source": [
        "#### Arbitray variables ordering VS minimal domain first ordering"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "j7d_45x3MiY9",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from copy import deepcopy\n",
        "import time\n",
        "class SudokoSolver():\n",
        "  def __init__(self, board):\n",
        "    self.original_board = deepcopy(board)\n",
        "    self.board = deepcopy(board)\n",
        "    self.n = len(board)\n",
        "    assert (self.n == len(board[0]))\n",
        "    # initialize state\n",
        "    self.row_state = [0]*self.n\n",
        "    self.col_state = [0]*self.n\n",
        "    self.grid_state = [0]*self.n\n",
        "    \n",
        "  def _setState(self, i, j, v):\n",
        "    self.row_state[i] |= 1 << v\n",
        "    self.col_state[j] |= 1 << v\n",
        "    grid_index = (i//3)*3 + (j//3)\n",
        "    self.grid_state[grid_index] |= 1 << v\n",
        "  \n",
        "  def _resetState(self, i, j, v):\n",
        "    self.row_state[i] &= ~(1 << v)\n",
        "    self.col_state[j] &= ~(1 << v)\n",
        "    grid_index = (i//3)*3 + (j//3)\n",
        "    self.grid_state[grid_index] &= ~(1 << v)\n",
        "  \n",
        "  def _checkState(self, i, j, v):\n",
        "    row_bit = (1 << v) & self.row_state[i] != 0\n",
        "    col_bit = (1 << v) & self.col_state[j]  != 0\n",
        "    grid_index = (i//3)*3 + (j//3)\n",
        "    grid_bit = (1 << v) & self.grid_state[grid_index]  != 0\n",
        "    return not row_bit and not col_bit and not grid_bit\n",
        "  \n",
        "  def reset(self):\n",
        "    # initialize state\n",
        "    self.row_state = [0]*self.n\n",
        "    self.col_state = [0]*self.n\n",
        "    self.grid_state = [0]*self.n\n",
        "    self.board = deepcopy(self.original_board)\n",
        "  \n",
        "  def _getEmptySpots(self): \n",
        "    ''' get empty spots and find its corresponding values in O(n*n)'''\n",
        "    empty_spots = {}\n",
        "    # initialize the state, and get empty spots\n",
        "    for i in range(self.n):\n",
        "      for j in range(self.n):\n",
        "        if self.board[i][j]:\n",
        "            # set that bit to 1\n",
        "            self._setState(i, j, self.board[i][j]-1)          \n",
        "        else:\n",
        "            empty_spots[(i,j)] = []\n",
        "                    \n",
        "    # get possible values for each spot\n",
        "    for i, j in empty_spots.keys():\n",
        "      for v in range(self.n):\n",
        "        if self._checkState(i, j, v):\n",
        "          empty_spots[(i, j)].append(v+1)\n",
        "          \n",
        "    return empty_spots\n",
        "  \n",
        "  def helper(self, empty_spots, index):\n",
        "    if index == len(empty_spots):\n",
        "      return True\n",
        "    (i, j), vl = empty_spots[index]\n",
        "  \n",
        "    for v in vl: #try each value\n",
        "      # check the state\n",
        "      if self._checkState(i, j, v-1):\n",
        "        # set the state\n",
        "        self._setState(i, j, v-1)\n",
        "        # mark the board\n",
        "        self.board[i][j] = v\n",
        "        if self.helper(empty_spots, index+1):\n",
        "          return True\n",
        "        else:\n",
        "          #backtack to previouse state\n",
        "          self._resetState(i, j, v-1)\n",
        "          #unmark the board\n",
        "          self.board[i][j] = None\n",
        "    return False\n",
        "  \n",
        "  def backtrackSolver(self):\n",
        "    self.reset()\n",
        "    empty_spots = self._getEmptySpots()\n",
        "    empty_spots = [(k, v) for k, v in empty_spots.items() ]\n",
        "    t0 = time.time()\n",
        "    ans = self.helper(empty_spots, 0)\n",
        "    print('total time: ', time.time() - t0)\n",
        "    return ans\n",
        "  \n",
        "  def backtrackSolverSorted(self):\n",
        "    self.reset()\n",
        "    empty_spots = self._getEmptySpots()\n",
        "    empty_spots = sorted(empty_spots.items(), key=lambda x: len(x[1]))\n",
        "    t0 = time.time()\n",
        "    ans = self.helper(empty_spots, 0)\n",
        "    print('sorted total time: ', time.time() - t0)\n",
        "    return ans"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zIti82qiQ7Je",
        "colab_type": "code",
        "outputId": "35a81f87-07fc-4dca-cc19-bd0440e6f19d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 72
        }
      },
      "source": [
        "board = [[5, 3, None, None, 7, None, None, None, None],\n",
        "         [6, None, None, 1, 9, 5, None, None, None],\n",
        "         [None, 9, 8, None, None, None, None, 6, None],\n",
        "         [8, None, None, None, 6, None, None, None, 3], \n",
        "         [4, None, None, 8, None, 3, None, None, 1], \n",
        "         [7, None, None, None, 2, None, None, None, 6], \n",
        "         [None, 6, None, None, None, None, 2, 8, None], \n",
        "         [None, None, None, 4, 1, 9, None, None, 5],\n",
        "         [None, None, None, None, 8, None, None, 7, 9]]\n",
        "solver = SudokoSolver(board)\n",
        "solver.backtrackSolver()\n",
        "solver.backtrackSolverSorted()"
      ],
      "execution_count": 180,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "total time:  0.02195119857788086\n",
            "sorted total time:  0.00042724609375\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 180
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6y9kEw6B-HGR",
        "colab_type": "text"
      },
      "source": [
        "#### Implementation"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SeHAPGl6-KSL",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from copy import deepcopy\n",
        "class Sudoku():\n",
        "  def __init__(self, board):\n",
        "    self.org_board = deepcopy(board)\n",
        "    self.board = deepcopy(board)\n",
        "    \n",
        "  def init(self):\n",
        "    self.A = set([i for i in range(1,10)])\n",
        "    self.row_state = [set() for i in range(9)]\n",
        "    self.col_state = [set() for i in range(9)]\n",
        "    self.block_state = [[set() for i in range(3)] for i in range(3)]\n",
        "    self.unfilled = []\n",
        "\n",
        "    for i in range(9):\n",
        "      for j in range(9):\n",
        "          c = self.org_board[i][j]\n",
        "          if c == 0:\n",
        "              self.unfilled.append((i, j))\n",
        "          else:\n",
        "              self.row_state[i].add(c)\n",
        "              self.col_state[j].add(c)\n",
        "              self.block_state[i//3][j//3].add(c)\n",
        "  \n",
        "  def set_state(self, i, j, c):\n",
        "    self.board[i][j] = c\n",
        "    self.row_state[i].add(c)\n",
        "    self.col_state[j].add(c)\n",
        "    self.block_state[i//3][j//3].add(c)\n",
        "    \n",
        "  def reset_state(self, i, j, c):\n",
        "    self.board[i][j] = 0\n",
        "    self.row_state[i].remove(c)\n",
        "    self.col_state[j].remove(c)\n",
        "    self.block_state[i//3][j//3].remove(c)\n",
        "    \n",
        "  def _ret_len(self, args):\n",
        "    i, j = args\n",
        "    option = self.A - (self.row_state[i] | self.col_state[j] | self.block_state[i//3 ][j//3])\n",
        "    return len(option)\n",
        "              \n",
        "  def solve(self):\n",
        "    '''implement solver restricted spot selection and look ahead'''\n",
        "    if len(self.unfilled) == 0:\n",
        "      return True\n",
        "    i, j = min(self.unfilled, key = self._ret_len)\n",
        "    option = self.A - (self.row_state[i] | self.col_state[j] | self.block_state[i//3 ][j//3])\n",
        "    #print(option)\n",
        "    if len(option) == 0:\n",
        "      return False\n",
        "    self.unfilled.remove((i, j))\n",
        "    for c in option:\n",
        "      self.set_state(i, j, c)\n",
        "      if self.solve():\n",
        "        return True\n",
        "      else:\n",
        "        self.reset_state(i, j, c)\n",
        "    # no candidate is valid, backtrack\n",
        "    self.unfilled.append((i, j))\n",
        "    return False\n",
        "  \n",
        "  def naive_solve(self):\n",
        "    '''implement naitve solver without restricted spot selection or look ahead'''\n",
        "    if len(self.unfilled) == 0:\n",
        "      return True\n",
        "    i, j = self.unfilled.pop()\n",
        "    option = self.A - (self.row_state[i] | self.col_state[j] | self.block_state[i//3 ][j//3])\n",
        "    for c in option:\n",
        "      self.set_state(i, j, c)\n",
        "      if self.naive_solve():\n",
        "        return True\n",
        "      else:\n",
        "        self.reset_state(i, j, c)\n",
        "    # no candidate is valid, backtrack\n",
        "    self.unfilled.append((i, j))\n",
        "    return False\n",
        "  \n",
        "  \n",
        "      \n",
        "      "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "22LaAbRwAOJl",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "board_easy = [[5, 3, 0, 0, 7, 0, 0, 0, 0],\n",
        "         [6, 0, 0, 1, 9, 5, 0, 0, 0],\n",
        "         [0, 9, 8, 0, 0, 0, 0, 6, 0],\n",
        "         [8, 0, 0, 0, 6, 0, 0, 0, 3], \n",
        "         [4, 0, 0, 8, 0, 3, 0, 0, 1], \n",
        "         [7, 0, 0, 0, 2, 0, 0, 0, 6], \n",
        "         [0, 6, 0, 0, 0, 0, 2, 8, 0], \n",
        "         [0, 0, 0, 4, 1, 9, 0, 0, 5],\n",
        "         [0, 0, 0, 0, 8, 0, 0, 7, 9]]\n",
        "\n",
        "board_hard = [[3, 8, 0, 0, 0, 4, 0, 0, 0],\n",
        "         [0, 0, 5, 0, 0, 0, 0, 1, 0],\n",
        "         [0, 0, 1, 5, 0, 0, 0, 7, 0],\n",
        "         [2, 0, 7, 0, 0, 5, 0, 0, 4],  \n",
        "         [0, 0, 0, 6, 7, 9, 0, 0, 0], \n",
        "         [8, 0, 0, 1, 0, 0, 7, 0, 6],\n",
        "         [0, 5, 0, 0, 0, 8, 2, 0, 0], \n",
        "         [0, 4, 0, 0, 0, 0, 5, 0, 0],\n",
        "         [0, 0, 0, 2, 0, 0, 0, 4, 1]]\n",
        "\n",
        "# board_evil = [[0, 0, 0, 7, 0, 0, 0, 0, 4],\n",
        "#               [8, 0, 0, 0, 0, 6, 0, 0, 0],\n",
        "#               [6, 0, 0, 0, 9, 8, 7, 0, 0],\n",
        "#               [0, 4, 0, 0, 6, 0, 9, 0, 7],  \n",
        "#               [0, 9, 0, 0, 0, 0, 0, 1, 0], \n",
        "#               [1, 0, 8, 0, 2, 0, 0, 3, 0],\n",
        "#               [0, 0, 3, 5, 4, 0, 0, 0, 8], \n",
        "#               [0, 0, 0, 1, 0, 0, 0, 0, 5],\n",
        "#               [2, 0, 0, 0, 0, 9, 0, 0, 0]]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lFy8CNdgENA4",
        "colab_type": "code",
        "outputId": "2da2bea5-a544-4259-f30a-0fa4ffdc5c4d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 184
        }
      },
      "source": [
        "for board in [board_easy, board_hard]:\n",
        "  solver = Sudoku(board)\n",
        "\n",
        "  import time\n",
        "  t0 = time.time()\n",
        "  solver.init()\n",
        "  solver.naive_solve()\n",
        "  print(solver.board)\n",
        "  print('total time using naive solver: ', time.time()-t0, 's')\n",
        "\n",
        "  t0 = time.time()\n",
        "  solver.init()\n",
        "  solver.solve()\n",
        "  print(solver.board)\n",
        "  print('total time using smart solver: ', time.time()-t0, 's')"
      ],
      "execution_count": 183,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[5, 3, 4, 6, 7, 8, 9, 1, 2], [6, 7, 2, 1, 9, 5, 3, 4, 8], [1, 9, 8, 3, 4, 2, 5, 6, 7], [8, 5, 9, 7, 6, 1, 4, 2, 3], [4, 2, 6, 8, 5, 3, 7, 9, 1], [7, 1, 3, 9, 2, 4, 8, 5, 6], [9, 6, 1, 5, 3, 7, 2, 8, 4], [2, 8, 7, 4, 1, 9, 6, 3, 5], [3, 4, 5, 2, 8, 6, 1, 7, 9]]\n",
            "total time using naive solver:  0.005067586898803711 s\n",
            "[[5, 3, 4, 6, 7, 8, 9, 1, 2], [6, 7, 2, 1, 9, 5, 3, 4, 8], [1, 9, 8, 3, 4, 2, 5, 6, 7], [8, 5, 9, 7, 6, 1, 4, 2, 3], [4, 2, 6, 8, 5, 3, 7, 9, 1], [7, 1, 3, 9, 2, 4, 8, 5, 6], [9, 6, 1, 5, 3, 7, 2, 8, 4], [2, 8, 7, 4, 1, 9, 6, 3, 5], [3, 4, 5, 2, 8, 6, 1, 7, 9]]\n",
            "total time using smart solver:  0.002804994583129883 s\n",
            "[[3, 8, 6, 7, 1, 4, 9, 2, 5], [4, 7, 5, 9, 2, 3, 6, 1, 8], [9, 2, 1, 5, 8, 6, 4, 7, 3], [2, 6, 7, 8, 3, 5, 1, 9, 4], [5, 1, 4, 6, 7, 9, 8, 3, 2], [8, 3, 9, 1, 4, 2, 7, 5, 6], [1, 5, 3, 4, 9, 8, 2, 6, 7], [7, 4, 2, 3, 6, 1, 5, 8, 9], [6, 9, 8, 2, 5, 7, 3, 4, 1]]\n",
            "total time using naive solver:  0.029914140701293945 s\n",
            "[[3, 8, 6, 7, 1, 4, 9, 2, 5], [4, 7, 5, 9, 2, 3, 6, 1, 8], [9, 2, 1, 5, 8, 6, 4, 7, 3], [2, 6, 7, 8, 3, 5, 1, 9, 4], [5, 1, 4, 6, 7, 9, 8, 3, 2], [8, 3, 9, 1, 4, 2, 7, 5, 6], [1, 5, 3, 4, 9, 8, 2, 6, 7], [7, 4, 2, 3, 6, 1, 5, 8, 9], [6, 9, 8, 2, 5, 7, 3, 4, 1]]\n",
            "total time using smart solver:  0.0038022994995117188 s\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "G0Z92Cz0vsvM",
        "colab_type": "text"
      },
      "source": [
        "## Combinatorial Optimization Problems\n",
        "* [Resources](https://www.coursera.org/learn/discrete-optimization/lecture/n2TGL/knapsack-1-intuition)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zfCvP2V3v2q4",
        "colab_type": "text"
      },
      "source": [
        "### Travelling Salesman Problem\n",
        "\n",
        "Resources:\n",
        "\n",
        "* [notes](https://www.mathematics.pitt.edu/sites/default/files/TSP.pdf)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8p6Y7id0-npr",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 195
        },
        "outputId": "7fb92394-d0f7-4956-d250-d7f5f0eceafb"
      },
      "source": [
        "from graphviz import Graph\n",
        "dot = Graph(comment='The Round Table', format='png')\n",
        "dot.node_attr['shape']='ellipse'\n",
        "# nodes = ['1', '2', '3', '4']\n",
        "# for n in nodes:\n",
        "#   dot.node(n)\n",
        "dot.edge('1', '2', label=str(10))\n",
        "dot.edge('1', '3', label=str(15))\n",
        "dot.edge('1', '4', label=str(20))\n",
        "dot.edge('2', '4', label=str(25))\n",
        "dot.edge('3', '4', label=str(30))\n",
        "dot.edge('2', '3', label=str(35))\n",
        "\n",
        "rank1 = [1, 4]\n",
        "rank2 = [2, 3]\n",
        "rank3 = [2, 3]\n",
        "for rank in [rank1, rank2]:\n",
        "  with dot.subgraph() as s:\n",
        "    s.attr(rank='same')\n",
        "    for node in rank:\n",
        "      s.node(str(node))\n",
        "dot.render('test-output/tsp_graph', view=True) \n",
        "dot"
      ],
      "execution_count": 184,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<graphviz.dot.Graph at 0x7fac751a57f0>"
            ],
            "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n -->\n<!-- Title: %3 Pages: 1 -->\n<svg width=\"152pt\" height=\"131pt\"\n viewBox=\"0.00 0.00 152.00 131.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 127)\">\n<title>%3</title>\n<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-127 148,-127 148,4 -4,4\"/>\n<!-- 1 -->\n<g id=\"node1\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-105\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n</g>\n<!-- 2 -->\n<g id=\"node2\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n</g>\n<!-- 1&#45;&#45;2 -->\n<g id=\"edge1\" class=\"edge\">\n<title>1&#45;&#45;2</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M19.8573,-87.3405C17.8734,-81.5903 15.992,-75.1128 15,-69 13.1642,-57.6871 16.0425,-45.1556 19.4391,-35.3457\"/>\n<text text-anchor=\"middle\" x=\"23\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">10</text>\n</g>\n<!-- 3 -->\n<g id=\"node3\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"117\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"117\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n</g>\n<!-- 1&#45;&#45;3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>1&#45;&#45;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M33.3926,-87.382C37.91,-76.763 44.801,-63.5006 54,-54 65.1288,-42.5064 80.7206,-33.5567 93.6084,-27.4555\"/>\n<text text-anchor=\"middle\" x=\"62\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">15</text>\n</g>\n<!-- 4 -->\n<g id=\"node4\" class=\"node\">\n<title>4</title>\n<ellipse fill=\"none\" stroke=\"#000000\" cx=\"117\" cy=\"-105\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"117\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n</g>\n<!-- 1&#45;&#45;4 -->\n<g id=\"edge3\" class=\"edge\">\n<title>1&#45;&#45;4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M54.003,-105C65.2905,-105 78.3867,-105 89.705,-105\"/>\n<text text-anchor=\"middle\" x=\"72\" y=\"-111.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">20</text>\n</g>\n<!-- 2&#45;&#45;3 -->\n<g id=\"edge6\" class=\"edge\">\n<title>2&#45;&#45;3</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M54.003,-18C65.2905,-18 78.3867,-18 89.705,-18\"/>\n<text text-anchor=\"middle\" x=\"72\" y=\"-24.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">35</text>\n</g>\n<!-- 2&#45;&#45;4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>2&#45;&#45;4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M44.5987,-31.8714C52.5615,-38.3639 61.9672,-46.3406 70,-54 81.8513,-65.3003 94.3752,-78.9876 103.5124,-89.3365\"/>\n<text text-anchor=\"middle\" x=\"93\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">25</text>\n</g>\n<!-- 3&#45;&#45;4 -->\n<g id=\"edge5\" class=\"edge\">\n<title>3&#45;&#45;4</title>\n<path fill=\"none\" stroke=\"#000000\" d=\"M117,-36.0034C117,-50.9283 117,-72.0422 117,-86.9735\"/>\n<text text-anchor=\"middle\" x=\"125\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">30</text>\n</g>\n</g>\n</svg>\n"
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 184
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Q5MF1uKtPRnH",
        "colab_type": "text"
      },
      "source": [
        "\n",
        "![alt text](https://www.geeksforgeeks.org/wp-content/uploads/Euler12.png)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yb8mmm2r1qxE",
        "colab_type": "code",
        "outputId": "0e9d5367-21a3-4eb4-d38f-0f9185fa8441",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 350
        }
      },
      "source": [
        "# Import our modules that we are using\n",
        "import matplotlib.pyplot as plt\n",
        "import numpy as np\n",
        "import math\n",
        "\n",
        "# Create the vectors X and Y\n",
        "x = np.array(range(10))\n",
        "y = (x)**(x+1)\n",
        "y2= [math.factorial(i) for i in x]\n",
        "print(y)\n",
        "print(y2)\n",
        "\n",
        "# Create the plot\n",
        "plt.plot(x,y, label='y = (x-1)**x')\n",
        "plt.plot(x, y2, label='y = x!')\n",
        "\n",
        "# Add a title\n",
        "plt.title('My first Plot with Python')\n",
        "\n",
        "# Add X and y Label\n",
        "plt.xlabel('x axis')\n",
        "plt.ylabel('y axis')\n",
        "\n",
        "# Add a grid\n",
        "plt.grid(alpha=.4,linestyle='-')\n",
        "\n",
        "# Add a Legend\n",
        "plt.legend()\n",
        "\n",
        "# Show the plot\n",
        "plt.show()"
      ],
      "execution_count": 185,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[         0          1          8         81       1024      15625\n",
            "     279936    5764801  134217728 3486784401]\n",
            "[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEWCAYAAABrDZDcAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0\ndHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAgAElEQVR4nO3deZhcVbnv8e/b3Uk6c0iHDE2HJJKQ\nQTxMAUQuMo9y4FFR9CIyGi8PHJDHCY4akOu5DkdUzsErxIiAgp4Dgg9yEVEZAiozYUpXhzB3uitT\nk3R1kp7f+0ftSqo7PVR3165dw+/zPEVq77323m+tkHpr77X2WubuiIhI6SqLOgAREYmWEoGISIlT\nIhARKXFKBCIiJU6JQESkxCkRiIiUOCUCiZSZjTWzP5jZNjO728zONbOHI4rlbTM7Mcfn/KOZnT/A\n9tvM7Du5jCk471wzczOryPW5JfeUCCRjwRdlu5lN67X+xeBLY+4wDns2MAOocvdPufud7n7yMOMb\n9EsziHO7mbWY2Xoz+5GZlQ/xPMeaWf1wYuzN3U9z99uD415gZk8O91hpX94twettM7s6w31zngQl\nfygRyFC9BXw2tWBmHwLGjeB4c4C17t45WMEs/jo90N0nACcA/xP4QpaOmy+mBJ/vs8ByMzs16oAk\nvykRyFD9Cvh82vL5wB2pBTM7zMw2pP/KNrNPmNlLvQ9kZt8GlgPnBL9gL+79qzj4hXuZmb0OvG5J\nPzazjWbWbGavmNkBZrYMOBf4WnCsPwz2Qdw9BjwBHNBHbGPM7Cdm1hC8fhKsGw/8EahO++Vd3Wvf\neWa21czKguWfm9nGtO2/MrMvBe8fM7NLzGwxcDNwZHDMrWmH3MvM/p+ZJczsaTPbb7DPFny+fwCv\nAQeY2U/N7IZecd5vZleZ2a+AfYE/BOf+Wlqxc83sXTPbbGbfGKx+gm3Hmlm9mX05+HtqNLMLM4lZ\nIuLueumV0Qt4GzgRqAMWA+VAPclf9Q7MDcqtAU5L2+8+4Mv9HPM64NdpyxcAT6YtO/BnYCowFjgF\neB6YAlgQx6yg7G3Adwb5DA7MD94vAeLAxemfL3h/PfAUMB3YG/g78L+DbccC9YOc513g0OB9HfAm\nsDht28HB+8eAS/r67GmfaQtwOFAB3An8tp9zzg0+X0VQN0cBO0he+RwONABlQdlpwbYZvT97r2P9\nPKj3A4G2tM8wWP10BmVGAacH59or6v+H9er7VZBXBGZ2a/BL49UMys4xs7+a2cvBr6+aXMRY5FJX\nBScBtcD6XttvBz4HYGZTSX553zWC833X3ZvcfSfQAUwEFgHm7rXu3jjE471gZu8DfwBWAr/so8y5\nwPXuvtHdNwHfBs4bwjkeB44xs5nB8j3B8jxgErDHFdIA7nP3Zzx5++xO4KBBym8Gmkh+tqvd/a/u\n/gywjWRSAPgM8Ji7bxjkWN92953u/lIQ84HB+sHqpyPY3uHuDwItwMKMPq3kXKH2CLgNuIm0WxID\n+CFwh7vfbmbHA99laP+gZU+/AlYB8+j77+DXQG1wG+XTwBPD+LJO917qjbs/YmY3AT8F5pjZvcBX\n3L15CMc7xN3XDVKmGngnbfmdYF2mHgfOJHnFtIrkL//zgFaS9dE9hGPF097vACYMUn6a993mkkrQ\nfw7+vHEE5x6sfrb0iiGTuCUiBXlF4O6rSP7i2cXM9jOzh8zseTN7wswWBZuWAI8E7x8FzsphqEXJ\n3d8h2Wh8OnBvH9vXA/8APkHyy+9XIz1lr+P/h7sfSvLvdn/gq32VG6EGkre8UvYN1mV6nseBo0ne\nJnkceJLkrZpjguW+hD0U8K+Bs8zsQJK31H4/gnMPVD9SYAoyEfRjBfAvwRfEV4D/G6x/ieQXEsDH\ngYlmVhVBfMXmYuB4d9/ez/Y7gK8BH6KPZDFcQWP0EWY2CthO8hd26tf1BuADWTrVb4Bvmtneluwu\nu5zkF2nqPFVmNrm/nd39dWAnyV/ejwdXLBuAT9J/ItgA1JjZ6Cx9ht4x1QPPkkzMvwtutaWfeyh1\nN1D9SIEpikRgZhOAjwB3m9lq4BZgVrD5KyTvzb5I8tfYeqArkkCLiLu/4e7PDVDkPpK/GO9z9x1Z\nPPUkkg2Y75O8HbEF+Pdg2y+AJUGPnd/3s3+mvgM8B7wMvAK8EKzDk72NfgO8GZyrv1tGj5O8RfJe\n2rIFx+rLIyR7+cTNbPMI4+/P7SSTc++rtO+S/GLfamZfyeA4/daPFB5zL8yJaSz58NID7n6AmU0C\n6tx91iD7TABi7q4G4xwwszeAL7r7X6KORZLM7KMkf7nP8UL9xy9ZVxRXBMFl91tm9imAoK/5gcH7\naan+3MA1wK0RhVlSzOyTJO87PzJYWcmN4HbalcBKJQFJV5CJwMx+Q7IxcmHw4MrFJLuzXWzJB5de\nY3ej8LFAnZmtJTmUwb9FEHJJMbPHgJ8Blw2xd4yEJHhgbSvJW6Y/iTgcyTMFe2tIRESyoyCvCERE\nJHsK7oGyadOm+dy5c4e1b0dHB6NGjcpuQAVM9dGT6mM31UVPxVAfzz///GZ337uvbQWXCObOnctz\nzw3Ua7F/DQ0NVFcP5eHQ4qb66En1sZvqoqdiqA8ze6e/bbo1JCJS4pQIRERKnBKBiEiJK7g2gr50\ndHRQX19Pa2vrgOW6urrYtm1bjqLKf9moj8rKSmpqagq+IU2klIWWCMyskuTwu2OC89zj7tf2KnMB\nyXFiUuPZ3+TuK4d6rvr6eiZOnMjcuXMxs37Ltbe3M3p0KON5FaSR1oe7s2XLFurr65k3b14WIxOR\nXArziqCN5OiULcGj7U+a2R/d/ale5f7L3S8fyYlaW1sHTQKSfWZGVVUVmzZtijoUERmB0BJBMJZJ\nS7A4KniF9hizkkA0VO8ihS/UNgJLTmD+PDAf+Km7P91HsU8GIyKuBa5KG7I3/TjLgGUANTU1NDT0\nnP+iq6uL9vb2QePJtFypyFZ9dHV17fF3UoiampoGL1QiVBc95UN93Pp0Ix+aNZ7D9p2U/YPnYmJk\nkhONPwoc0Gt9FTAmeP9F4JHBjnXooYd6b2vWrNljXV/a2toyKpcvfvzjH/vtt98+pH1OOeUUnzx5\nsn/sYx/rsf6cc87xtWvXurt7d3e3u7t/85vf3LWcWnfttdf2KJOJTOs/361fvz7qEPKG6qKnqOtj\nR1unz736Af/xn+uGfQzgOe/nezUnvYbcfauZPQqcCryatn5LWrGVwA9yEU8h6Ozs5NZbb+WFF/qb\nw6RvX/3qV9mxYwe33HJLj/WXXnopP/jBD/j5z3/Oww8/zKpVq2htbWXlypUkEgmWLFnCqlWr6Ojo\n2LXuqquuyuZHEpFhWrshgTssmjkxlOOH9hxBMIXdlOD9WOAkINarTPpEMmcCtWHFE6bly5fzk5/s\nHtn3G9/4BjfemMm84P175JFHOOSQQ6ioqKCzs5PDDjuMxx57DIBrrrmGb3zjG33ud8IJJzBx4p7/\nsxx99NH85S9/obOzk1NOOYVTTjmFm266iS1btnDVVVftWnfjjTfuWvfOO++wYMECNm/eTHd3N0cf\nfTQPP/zwiD6XiAxdXTwBwKKZIdwWItw2glnA7UE7QRnw3+7+gJldT/IS5X7gCjM7E+gkORn9BSM9\n6bf/8BprGpr73Obuw2rcXFI9iWv/+YP9br/ooov4xCc+wZe+9CW6u7v57W9/yzPPPLNHuaOPPppE\nIrHH+h/+8IeceOKJPdb97W9/49BDDwWgoqKC2267jbPPPpv//M//5KGHHuLpp/tqbulfWVkZ8+fP\n56WXXqKpqYnHHnuMyy67jKqqKm688UaWLFnCY489xhVXXLFr3ZVXXsnXv/51Lr30Ug4//HCWLFnC\nySefPKTzisjI1cabGTuqnH2njgvl+GH2GnoZOLiP9cvT3l9DctawgjZ37lyqqqp48cUX2bBhAwcf\nfDBVVVV7lHviiScyPmZjYyOLFy/etfzBD36Q8847jzPOOIN//OMfw+r/P336dBoaGjjjjDM46aST\n+Na3vsUll1ySaq/hpJNO4rrrruux7pJLLuHuu+/m5ptvZvXq1UM+p4iMXF08wf4zJ1JWFk4vvaJ4\nsjjdQL/cw3yg7JJLLuG2224jHo9z0UUX9VlmKFcEY8eO3eNJ6VdeeYUpU6awceNGAJ5++mm++MUv\nAnD99ddz5plnDhhja2srY8eO3XVV9K1vfQvo2QX0uuuu67Fux44d1NfXA9DS0tLnbScRCY+7E4sn\nOGnxjNDOUXSJICof//jHWb58OR0dHdx11119lhnKFcHixYtZt27druV7772XpqYmVq1axRlnnMEz\nzzzDEUccMaRf6WvXruWAAw7IuDzA17/+dc4991zmzJnDF77wBR544IEh7S8iI7OppY2m7e0smhXe\njzANOpclo0eP5rjjjuPTn/405eXlIz7eaaedxqpVqwDYvHkzV199NStXrmT//ffn8ssv58orr+xz\nv6OPPppPfepT/PWvf6WmpoY//elPAGzYsIGxY8cyc+bMjGN4/PHHefbZZ3clg9GjR/PLX/5yxJ9N\nRDIXa0zeRVgYUo8h0BVB1nR3d/PUU09x9913Z+V4c+bMoaqqitdff50FCxawdu3aXduuuOKKfvfr\n76rjrrvu2nUbKVPHHHMMTz21e0SQe++9d0j7i8jIhd1jCHRFkBVr1qxh/vz5nHDCCSxYsCBrx/3e\n975HY2NjVo41ZcoUzj///KwcS0RypzbezIxJY5g6PrwBM3VFkAVLlizhzTffzPpxFy5cyMKFC7Ny\nrAsvvDArxxGR3Io1JlgY4tUA6IpARCRvdXZ1s25jC4tDbB8AJQIRkbz11ubttHd1h9pQDEoEIiJ5\nK5aDhmJQIhARyVuxeDPlZcZ+08eHeh4lggLz9ttvD/mhMBEpTHXxBPvtPZ4xFSN/NmkgSgQiInmq\nNgc9hkCJICvCGIb6rLPO4o477gDglltu4dxzzx3R8USksDS3drB+687Q5iBIV3zPEfzxaoi/0uem\nCu8GG0bum/khOO17/W4OYxjqFStWcNRRRzFv3jxuuOGGHk/4ikjxW7uroViJoCCEMQz1jBkzuP76\n6znuuOO47777mDp1ajZDFpE8t6vH0Kzwbw0VXyIY4Jd7ZwENQw3JYaerqqp6TAw/d+5cXn311T3K\nikhxicWbmVhZQfXkytDPVXyJICLZHob6mWee4Y9//CMvvvgixxxzDCeffDLz5s3LVrgikudijQkW\nzZw4rFkVh0qNxVmSzWGo29ra+MIXvsCtt95KdXU1N9xwAxdddBHuTkNDA2effXaWohaRfOTu1MUT\noT9IlqIrgizJ5jDUY8aM4aWXXtq1fOaZZ+6afay6upp77rlnxOcQkfy1futOEm2doQ8tkaIrgiwI\naxhqESlNqTkIFoc4K1m60K4IzKwSWAWMCc5zj7tf26vMGOAO4FBgC3COu78dVkxhCWsYahEpTake\nQ/vPKPwrgjbgeHc/EDgIONXMPtyrzMXA++4+H/gx8P3hnszdhx2oDJ/qXST7YvEENXuNZWLlqJyc\nL7RE4EktweKo4NX7W+Ms4Pbg/T3ACTaMJvLKykq2bNmiL6Ucc3e2bNlCZWX43dtESkmssTknD5Kl\nhNpYbGblwPPAfOCn7v50ryL7AO8BuHunmW0DqoDNvY6zDFgGUFNT06NfPUBFRQWbNm0iHo8PGE9X\nV1dWJpYvFtmoj/LyciZMmLDH30khampqijqEvKG66CmX9dHe2c2bm1r4yJzxOft3FWoicPcu4CAz\nmwLcZ2YHuPuQn4Zy9xXACoClS5d6dXX1sOJpaGhguPsWI9XHnlQfu6kuespVfbzWsI0uh8MWVOfs\nnDnpNeTuW4FHgVN7bVoPzAYwswpgMslGYxGRkhRrzN0YQymhJQIz2zu4EsDMxgInAbFexe4Hzg/e\nnw084rrRLyIlrG5DgtEVZcytCncymnRh3hqaBdwetBOUAf/t7g+Y2fXAc+5+P/AL4Fdmtg5oAj4T\nYjwiInmvtrGZBdMnUFGeu8e8QksE7v4ycHAf65envW8FPhVWDCIihaYunuDoBXvn9Jx6slhEJE80\nbW9nY6Itp+0DoEQgIpI3YvFmABblaGiJFCUCEZE8keoxlKvB5lKUCERE8kRdPEHV+NHsPWFMTs+r\nRCAikidi8WYWzcrNZDTplAhERPJAV7dTtyHBwhm5mYwmnRKBiEgeeLdpB60d3TlvKAYlAhGRvBBr\nDHoM5bihGJQIRETyQiyeoMxgwXQlAhGRkhSLNzO3ajxjR+d+qHwlAhGRPFAXT0TSPgBKBCIikdvR\n3sk7TTsi6TEESgQiIpFbu6EF99wPLZGiRCAiErEoewyBEoGISORi8QTjRpcze69xkZxfiUBEJGKx\neDMLZ06krCy3Q0ukKBGIiETI3YnFE5HdFgIlAhGRSG1MtLF1RweLZkbTYwiUCEREIlUbNBTneg6C\ndKElAjObbWaPmtkaM3vNzK7so8yxZrbNzFYHr+V9HUtEpFjVxZOT0UR5ayi0yeuBTuDL7v6CmU0E\nnjezP7v7ml7lnnD3M0KMQ0Qkb8XiCWZOqmTKuNGRxRDaFYG7N7r7C8H7BFAL7BPW+UREClEswqEl\nUsK8ItjFzOYCBwNP97H5SDN7CWgAvuLur/Wx/zJgGUBNTQ0NDQ3DiqOpqWlY+xUr1UdPqo/dVBc9\nhVUfnV3O6xsSHFJdOezvtWwIPRGY2QTgd8CX3L251+YXgDnu3mJmpwO/Bxb0Poa7rwBWACxdutSr\nq6uHHc9I9i1Gqo+eVB+7qS56CqM+6uIJOrudw+ZXR1rfofYaMrNRJJPAne5+b+/t7t7s7i3B+weB\nUWY2LcyYRETyRSweDC0R8a2hMHsNGfALoNbdf9RPmZlBOczs8CCeLWHFJCKST2LxBBVlxgemTYg0\njjBvDR0FnAe8Ymarg3X/CuwL4O43A2cDl5pZJ7AT+Iy7e4gxiYjkjbp4gvnTJzC6ItpHukJLBO7+\nJDDgwBnufhNwU1gxiIjks1hjM4fNmxp1GHqyWEQkCtt2dtCwrTXSoSVSlAhERCKQD08UpygRiIhE\noC5PegyBEoGISCRq4wkmVVYwc1Jl1KEoEYiIRKEunmDRrEkEPegjpUQgIpJj3d2eTAR50D4ASgQi\nIjm3futOWto686LHECgRiIjkXCzVYygPGopBiUBEJOdiwaxk+89QIhARKUmxDQn2nTqOCWNyMhPA\noJQIRERyLNbYHOkcxb0pEYiI5FBrRxdvbd7OYiUCEZHStG5jC90OC/OkxxAoEYiI5FS+9RgCJQIR\nkZyKNTYzpqKMuVXjow5lFyUCEZEcisUT7D9jIuVl0Q8tkaJEICKSQ7E8GloiRYlARCRHNre0sbml\nLa+6joISgYhIzqQmo1k8K396DEGIicDMZpvZo2a2xsxeM7Mr+yhjZvYfZrbOzF42s0PCikdEJGq1\nwdAS+XZFEObzzZ3Al939BTObCDxvZn929zVpZU4DFgSvI4CfBX+KiBSduniCaRPGMG3CmKhD6SG0\nKwJ3b3T3F4L3CaAW2KdXsbOAOzzpKWCKmc0KKyYRkSjlY0Mx5KiNwMzmAgcDT/fatA/wXtpyPXsm\nCxGRgtfV7azdkJ+JIPSh78xsAvA74Evu3jzMYywDlgHU1NTQ0NAwrFiampqGtV+xUn30pPrYTXXR\nUzbq4533W2nr7GZGZdewv8PCMmgiMLOjgNXuvt3MPgccAtzo7u9ksO8okkngTne/t48i64HZacs1\nwboe3H0FsAJg6dKlXl1dPdip+zWSfYuR6qMn1cduqoueRlofL25uBODIxftSXT05GyFlTSa3hn4G\n7DCzA4EvA28Adwy2kyVnZP4FUOvuP+qn2P3A54PeQx8Gtrl7Y2ahi4gUjrp4M2UG86dPiDqUPWRy\na6jT3d3MzgJucvdfmNnFGex3FHAe8IqZrQ7W/SuwL4C73ww8CJwOrAN2ABcO9QOIiBSC2niCedPG\nUzmqPOpQ9pBJIkiY2TXA54CPmlkZMGqwndz9SWDAwTTc3YHLMglURKSQ1cUTfKgmv24JpWRya+gc\noA242N3jJO/j/3uoUYmIFJGWtk7ebdrBojyZo7i3Qa8Igi//H6Utv0sGbQQiIpK0dkNqDoL8Gloi\npd9EYGZPuvv/MLME4OmbSN7Vyc9PJCKSZ2KNQSLIw2cIYIBE4O7/I/gzPyMXESkQdfFmJoypYJ8p\nY6MOpU+DthGY2Yl9rDs/nHBERIpPbTzB/jMmUJZHk9Gky6SxeLmZ/czMxpvZDDP7A/DPYQcmIlIM\n3J1YY3Petg9AZongGJIPka0GngTucvezQ41KRKRIxJtbaW7tzNv2AcgsEewFHE4yGbQBc4KnhkVE\nZBC7G4oL+4rgKeAhdz8VOAyoBv4WalQiIkUiFsxKlm+T0aTL5MniE4NnB3D3ncAVZvbRcMMSESkO\nsXgz1ZMrmTx20AEZIpPJA2XvmtleJGcRqww/JBGR4lEXT+R1QzFkNgz1JcCVJIeWWA18GPgHcHy4\noYmIFLb2zm7WbWzhuEXTow5lQJm0EVxJsm3gHXc/juRMY1tDjUpEpAi8ubmFzm7P6x5DkFkiaHX3\nVgAzG+PuMWBhuGGJiBS+QugxBJk1Fteb2RTg98Cfzex9YNDZyURESl1tvJlR5cYH9h4fdSgDyqSx\n+OPB2+vM7FFgMvBQqFGJiBSBuniC/faewKjyTG6+RGdIk9e7++NhBSIiUmxijQmO3K8q6jAGld9p\nSkSkQG3d0U68uTWvHyRLUSIQEQlB6onifO8xBJkNQ/0vwQNlIiKSobogESzO84fJILMrghnAs2b2\n32Z2aqYDzpnZrWa20cxe7Wf7sWa2zcxWB6/lQwlcRCSfxeLNTBk3iukTx0QdyqAGTQTu/k2Sw0v8\nArgAeN3M/o+Z7TfIrrcBpw5S5gl3Pyh4XZ9BvCIiBSEWT7Bo5kQKYbDmjNoI3N2BePDqJDk09T1m\n9oMB9lkFNGUjSBGRQtLd7ckxhvL8QbKUTMYauhL4PLAZWAl81d07zKwMeB342gjOf6SZvQQ0AF9x\n99f6iWEZsAygpqaGhoaGYZ2sqUl5KZ3qoyfVx26qi56GWh/rt7Wxo72LmZVdw/6+yqVMniOYCnzC\n3Xs8Tezu3WZ2xgjO/QIwx91bzOx0kk8uL+iroLuvAFYALF261Kurq4d90pHsW4xUHz2pPnZTXfQ0\nlPp45f04AEcsmk11df73tcmkjeDa3kkgbVvtcE/s7s3u3hK8fxAYZWbThns8EZF8EWtMYAb7z8j/\nrqMQ4XMEZjYz1QPJzA4PYtkSVTwiItlSt6GZfaeOY/yYIQ3eEJnQojSz3wDHAtPMrB64FhgF4O43\nA2cDl5pZJ7AT+EzQKC0iUtBijYmCeJAsJbRE4O6fHWT7TcBNYZ1fRCQKO9u7eHvLdv75wMJpY9EQ\nEyIiWfT6xgTdXhhDS6QoEYiIZNGuMYYKYGiJFCUCEZEsijUmqBxVxr5Tx0UdSsaUCEREsqhuQzML\nZ0ykvCz/h5ZIUSIQEckSd6e2MVEQcxCkUyIQEcmSTS1tNG1vL5gxhlKUCEREsqSugCajSadEICKS\nJbHGZCLQrSERkRIViyfYe+IYqibk/2Q06ZQIRESyJBZvLrjbQqBEICKSFZ1d3by+saUg5ijuTYlA\nRCQL3t6ynfbObhYWyNDT6ZQIRESyYPfQEkoEIiIlKdaYoLzMmD99QtShDJkSgYhIFsTizXxg2njG\nVJRHHcqQKRGIiGRBLF54Q0ukKBGIiIxQorWD+vd3FmSPIVAiEBEZsbUbgieKC7DHECgRiIiMWG1j\n4fYYghATgZndamYbzezVfrabmf2Hma0zs5fN7JCwYhERCVNdPMHEMRXsM2Vs1KEMS5hXBLcBpw6w\n/TRgQfBaBvwsxFhEREITizezcOZEzApnMpp0oSUCd18FNA1Q5CzgDk96CphiZrPCikdEJAzuTiye\nKNjbQgAVEZ57H+C9tOX6YF1j74JmtozkVQM1NTU0NDQM64RNTQPlpdKj+uhJ9bGb6qKngeojnmgn\n0drJzMruYX83RS3KRJAxd18BrABYunSpV1dXD/tYI9m3GKk+elJ97Ka66Km/+qit3QDAhxfNprp6\nai5Dypooew2tB2anLdcE60RECkZqjKH9C/RhMog2EdwPfD7oPfRhYJu773FbSEQkn8XiCfaZMpZJ\nlaOiDmXYQrs1ZGa/AY4FpplZPXAtMArA3W8GHgROB9YBO4ALw4pFRCQsdQU6GU260BKBu392kO0O\nXBbW+UVEwtbW2cUbm7Zz0pIZUYcyInqyWERkmN7YuJ2ubmfhzMIcYyhFiUBEZJhi8WYAFhf4rSEl\nAhGRYaqLJxhdXsa8aeOjDmVElAhERIapNp5g/vQJVJQX9ldpYUcvIhKhWGNzQQ8tkaJEICIyDE3b\n29mYaCv4rqOgRCAiMiyphuJFBd5jCJQIRESGpS4YWkJXBCIiJSrWmGDq+NHsPXFM1KGMmBKBiMgw\nxDYkWDijcCejSadEICIyRN3dztoCn4wmnRKBiMgQvdu0g50dXSwugoZiUCIQERmyVI+hhUXQUAxK\nBCIiQxaLJzCD/WcoEYiIlKRYY4K5VeMZO7o86lCyQolARGSIYkUwGU06JQIRkSHY0d7JO007iqZ9\nAJQIRESGZO2GFtyLY2iJFCUCEZEhqNs1xpCuCDJiZqeaWZ2ZrTOzq/vYfoGZbTKz1cHrkjDjEREZ\nqdrGBGNHlbPv1HFRh5I1oU1eb2blwE+Bk4B64Fkzu9/d1/Qq+l/ufnlYcYiIZFNdPMH+MydSVlb4\nQ0ukhHlFcDiwzt3fdPd24LfAWSGeT0QkVO5OLN5c8HMU9xZmItgHeC9tuT5Y19snzexlM7vHzGaH\nGI+IyIhsSrTx/o6OomofgBBvDWXoD8Bv3L3NzL4I3A4c37uQmS0DlgHU1NTQ0NAwrJM1NTWNINTi\no/roSfWxm+qip1R9PPVOsqF42qj2YX8P5aMwE8F6IP0Xfk2wbhd335K2uBL4QV8HcvcVwAqApUuX\nenV19bCDGsm+xUj10ZPqYzfVRU/V1dVsen0nAEd9cB57jR8dcUTZE+atoWeBBWY2z8xGA58B7k8v\nYGaz0hbPBGpDjEdEZETq4lUb3swAAAlkSURBVAlmTBpTVEkAQrwicPdOM7sc+BNQDtzq7q+Z2fXA\nc+5+P3CFmZ0JdAJNwAVhxSMiMlK18URRPUiWEmobgbs/CDzYa93ytPfXANeEGYOISDZ0dHXzxsYW\nPrpgWtShZJ2eLBYRycBbm7fT3tVdNLOSpVMiEBHJQCyeAGDhjOK7NaREICKSgVhjMxVlxn7Tx0cd\nStYpEYiIZKAunmC/vScwpqI4JqNJp0QgIpKBWDxRVHMQpFMiEBEZRKKtk/VbdxZlQzEoEYiIDOrN\nLa1Acc1BkE6JQERkEOs2J4eWKMaHyUCJQERkUG9uaWViZQWzJldGHUoolAhERAaxbvNOFs+chFnx\nTEaTTolARGQA7s4bm3cWbY8hUCIQERlQ/fs72dFRnENLpCgRiIgMoC4YWqJYewyBEoGIyIBi8eSs\nZPvPKN5EEPVUlSIiecndeWvzdv7+xhaqJ41mYuWoqEMKjRKBiAjw/vZ2Vr+3lRff28rq97by0ntb\n2bazA4DTF0+NOLpwKRGISMlp6+yitjHB6nffZ3Xwxf/2lh0AlFnyNtDpH5rJQbOncNDsvRjf1Rxx\nxOFSIhCRoubuvNu0I/lr/93kl/6ahmbau7oBmDFpDAfNnsI5h+3LQbOn8E81kxk/pudXY0NDIorQ\nc0aJQESKyradHbwU/MpPvZq2twNQOaqMf9pnChccNZeDZk/h4H2nMGvy2Igjjp4SgYgUrI6uburi\nieR9/Xe38uJ77/Pmpu27ts+fPoHjF03n4H2ncNDsKSycMZGKcnWW7C3URGBmpwI3AuXASnf/Xq/t\nY4A7gEOBLcA57v52mDGJSGFyd9Zv3Zn8lR/c4nll/TbaOpO3eKZNGM1Bs6fwiYP34aDZe/FPsycz\nqYh7+mRTaInAzMqBnwInAfXAs2Z2v7uvSSt2MfC+u883s88A3wfOCSsmEckNd8cdutzpdqe7m+Sf\nvd53BeW63enqDvbpDso5bGxu3dWL58V3t7K5pQ2A0RVlHFA9iXOPmMNB+07h4NlTqNlrbNGOBRS2\nMK8IDgfWufubAGb2W+AsID0RnAVcF7y/B7jJzMzdPdvBvPzY75j0+LW8rf9PdnNUH2lc9bGLu/MW\nuyvDkytJ/4fpu/7D7vW9yozU3sDJwMfKjcpR5VRWlVM5qowxFeVYN/BO8AqVs3dnJ1T08XU54FfV\nANuGu9+hF8BRVw6w7/CEmQj2Ad5LW64HjuivjLt3mtk2oArYnF7IzJYBywBqampoaGgYcjA7OmDn\n6NmUlen+YEp3d7fqI02+1Ec+5KLu7m7Kg3vpFvzHsLT3SRasT71Pld/93nqs77lvz+Olnyd1vIoy\nY1JlBaPS7us70JrlzzuY9vZ2Ro8e3c/W/v/GfMArlAG29bNfa9c4Wofx/TeYgmgsdvcVwAqApUuX\nenV19ZCPUV39SRo+eCTD2bdYNTQ0qD7SqD52U1309H5DA5PzoD7GhXTcMH/+rAdmpy3XBOv6LGNm\nFcBkko3GIiKSI2EmgmeBBWY2z8xGA58B7u9V5n7g/OD92cAjYbQPiIhI/0K7NRTc878c+BPJ7qO3\nuvtrZnY98Jy73w/8AviVma0DmkgmCxERyaFQ2wjc/UHgwV7rlqe9bwU+FWYMIiIysOi7SIiISKSU\nCERESpwSgYhIiVMiEBEpcVZovTXNbBPDf6h8Gr2eWi5xqo+eVB+7qS56Kob6mOPue/e1oeASwUiY\n2XPuvjTqOPKF6qMn1cduqoueir0+dGtIRKTEKRGIiJS4UksEK6IOIM+oPnpSfeymuuipqOujpNoI\nRERkT6V2RSAiIr0oEYiIlLiSSQRmdqqZ1ZnZOjO7Oup4omRms83sUTNbY2avmVn2574rMGZWbmYv\nmtkDUccSNTObYmb3mFnMzGrN7MioY4qKmV0V/Bt51cx+Y2aVUccUhpJIBGZWDvwUOA1YAnzWzJZE\nG1WkOoEvu/sS4MPAZSVeHwBXArVRB5EnbgQecvdFwIGUaL2Y2T7AFcBSdz+A5HD6RTlUfkkkAuBw\nYJ27v+nu7cBvgbMijiky7t7o7i8E7xMk/6HvE21U0TGzGuBjwMqoY4mamU0GPkpyrhDcvd3dt0Yb\nVaQqgLHBDIrjgOxPGJwHSiUR7AO8l7ZcTwl/8aUzs7nAwcDT0UYSqZ8AXwO6ow4kD8wDNgG/DG6V\nrTSz8VEHFQV3Xw/8EHgXaAS2ufvD0UYVjlJJBNIHM5sA/A74krs3Rx1PFMzsDGCjuz8fdSx5ogI4\nBPiZux8MbAdKsk3NzPYieedgHlANjDezz0UbVThKJRGsB2anLdcE60qWmY0imQTudPd7o44nQkcB\nZ5rZ2yRvGR5vZr+ONqRI1QP17p66QryHZGIoRScCb7n7JnfvAO4FPhJxTKEolUTwLLDAzOaZ2WiS\nDT73RxxTZMzMSN4DrnX3H0UdT5Tc/Rp3r3H3uST/v3jE3YvyV18m3D0OvGdmC4NVJwBrIgwpSu8C\nHzazccG/mRMo0obzUOcszhfu3mlmlwN/Itnyf6u7vxZxWFE6CjgPeMXMVgfr/jWYY1rkX4A7gx9N\nbwIXRhxPJNz9aTO7B3iBZE+7FynSoSY0xISISIkrlVtDIiLSDyUCEZESp0QgIlLilAhEREqcEoGI\nSIlTIhDJETP7e9QxiPRF3UdFREqcrghEejGzw8zsZTOrNLPxwXj0B/RR7vdm9nywfVmwbo6ZvW5m\n08yszMyeMLOTg20twZ+zzGyVma0Oxrk/OrefUKQnXRGI9MHMvgNUAmNJjr3z3T7KTHX3JjMbS3IY\nk2PcfYuZXQKcAjwDzHf3LwblW9x9gpl9Gah0938L5soYFwwHLhIJJQKRPgTDKzwLtAIfcfeuPspc\nB3w8WJwLnOLuTwXb/gTMBw5KfcmnJYKPArcCvwZ+7+6rex9bJJd0a0ikb1XABGAiySuDHszsWJKj\nUx7p7geSHIemMtg2juQItwTH6MHdV5Gc/GU9cJuZfT6E+EUypkQg0rdbgG8BdwLf72P7ZOB9d99h\nZotITvmZ8v1gv+XAz3vvaGZzgA3u/nOSs6KV6jDPkidKYvRRkaEIfqF3uPtdwT38v5vZ8e7+SFqx\nh4D/ZWa1QB2QuiV0DHAYcJS7d5nZJ83sQnf/Zdq+xwJfNbMOoAXQFYFESm0EIiIlTreGRERKnBKB\niEiJUyIQESlxSgQiIiVOiUBEpMQpEYiIlDglAhGREvf/AVz5xe7rL8tlAAAAAElFTkSuQmCC\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DcPitdgMPu_R",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "g = [[(1, 10), (2, 15), (3, 20)], \n",
        "   [(0, 10), (2, 35),(3,25)],\n",
        "   [(0, 15),(1,35),(3,30)],\n",
        "   [(0,20),(1,25),(2,30)]]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9w-LBP5xQbBZ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Implemented with graph search\n",
        "def tsp(g, cur, path, mincost, cost, bused, ans):\n",
        "  if len(path) == len(g): # we can only choose 0\n",
        "    cost += g[cur][0][1]\n",
        "    if cost < mincost[0]:\n",
        "      mincost[0] = cost\n",
        "      ans[0] = path[::]\n",
        "    return\n",
        "  for v, c in g[cur]:\n",
        "    # constraint on permutation and cost    \n",
        "    if (not bused[v]) and (cost + c < mincost[0]):\n",
        "        bused[v] = True\n",
        "        path.append(v)\n",
        "        cost += c\n",
        "        tsp(g, v, path, mincost, cost, bused, ans)\n",
        "        bused[v] = False\n",
        "        path.pop()\n",
        "        cost -= c\n",
        "  return"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FEYmJ7T5X9K3",
        "colab_type": "code",
        "outputId": "4cd01cb7-3473-49c5-a429-025cab024f8a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "import sys\n",
        "cv = 0\n",
        "path = [0]\n",
        "mincost = [sys.maxsize]\n",
        "cost = 0\n",
        "bused = [False] * len(g)\n",
        "bused[0] = True\n",
        "ans = [[]]\n",
        "tsp(g, cv, path, mincost, cost, bused, ans)\n",
        "print(mincost[0], ans[0])"
      ],
      "execution_count": 188,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "80 [0, 1, 3, 2]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "r5zIvfeQFntf",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "g = [{1: 10, 2: 15, 3:20}, \n",
        "   {0:10, 2:35,3:25},\n",
        "   {0:15,1:35,3:30},\n",
        "   {0:20,1:25,2:30}]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "M3_6OljQv7xv",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#Implement with permutation\n",
        "def tsp(a, d, used, curr, ans, start, g, mincost, cost):\n",
        "  if d == len(a): \n",
        "    # Add the cost from last vertex to the start\n",
        "    c = g[curr[-1]][start]\n",
        "    cost += c\n",
        "    if cost < mincost[0]:\n",
        "      mincost[0] = cost\n",
        "      ans[0] = curr[::] + [start]\n",
        "    return\n",
        "  \n",
        "  for i in a:\n",
        "    if not used[i] and cost + g[curr[-1]][i] < mincost[0] :\n",
        "      cost += g[curr[-1]][i]\n",
        "      curr.append(i)\n",
        "      used[i] = True      \n",
        "      tsp(a, d + 1, used, curr, ans, start, g, mincost, cost)\n",
        "      curr.pop()\n",
        "      cost -= g[curr[-1]][i]\n",
        "      used[i] = False\n",
        "  return"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gyRbyYYLH2jk",
        "colab_type": "code",
        "outputId": "460d7ba1-1d73-45ef-cb02-2686212749d2",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "import sys\n",
        "mincost = [sys.maxsize]\n",
        "bused = [False] * len(g)\n",
        "bused[0] = True\n",
        "start = 0\n",
        "a = [i for i in range(1, len(g))]\n",
        "ans = [[]]\n",
        "tsp(a, 0, bused, [0], ans, start, g, mincost, 0)\n",
        "print(mincost[0], ans[0])"
      ],
      "execution_count": 191,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "80 [0, 1, 3, 2, 0]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Uyw4RkhiMIqw",
        "colab_type": "text"
      },
      "source": [
        "### Knapsack problem\n",
        "Resources:\n",
        "* [Branch and Bound](https://en.wikipedia.org/wiki/Branch_and_bound)\n",
        "* [MILP](https://www.gurobi.com/resource/mip-basics/)\n",
        "* [COPs](https://www.math.unipd.it/~luigi/courses/metmodoc1718/m02.meta.en.partial01.pdf)\n",
        "#### **Knapsack** \n",
        "\n",
        "#### Depth first branch and bound\n",
        "DFS(backtracking) with branch and bound by estimating the total cost and compare it with **the** best found so far."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JipSSwFPHc76",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "c = 10\n",
        "w = [5, 8, 3]\n",
        "v = [45, 48, 35]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_eKc9AuYIDAi",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import heapq\n",
        "\n",
        "class BranchandBound:\n",
        "  def __init__(self, c, v, w):\n",
        "    self.best = 0 \n",
        "    self.c = c\n",
        "    self.n = len(v)\n",
        "    self.items = [(vi/wi, wi, vi) for _, (vi, wi) in enumerate(zip(v, w))]\n",
        "    self.items.sort(key=lambda x: x[0], reverse=True)\n",
        "    print(self.items)\n",
        "\n",
        "  def estimate(self, idx, curval, left_cap):\n",
        "    est = curval\n",
        "    # use the v/w to estimate\n",
        "    for i in range(idx, self.n):\n",
        "      ratio, wi, _ = self.items[i]\n",
        "      if left_cap - wi >= 0: # use all\n",
        "        est += ratio * wi\n",
        "        left_cap -= wi\n",
        "      else: # use part\n",
        "        est += ratio * (left_cap)\n",
        "        left_cap = 0 \n",
        "    return est\n",
        "  \n",
        "  def dfs(self, idx, est, val, left_cap, status):\n",
        "      if idx == self.n:\n",
        "        self.best = max(self.best, val)\n",
        "        return\n",
        "      print(status, val, left_cap, est )\n",
        "      \n",
        "      _, wi, vi = self.items[idx]\n",
        "      # Case 1: choose the item\n",
        "      if left_cap - wi >= 0: # prune by constraint\n",
        "        # Bound by estimate, increase value and volume\n",
        "        if est > self.best:   \n",
        "          status.append(True)\n",
        "          nest = self.estimate(idx+1, val+vi, left_cap - wi)   \n",
        "          self.dfs(idx+1, nest, val+vi, left_cap - wi, status)\n",
        "          status.pop()\n",
        "\n",
        "      # Case 2: not choose the item\n",
        "      if est > self.best:\n",
        "        status.append(False)\n",
        "        nest =  self.estimate(idx+1, val, left_cap)\n",
        "        self.dfs(idx+1, nest, val, left_cap, status) \n",
        "        status.pop()\n",
        "      return\n",
        "\n",
        "  def bfs(self):\n",
        "      # track val, cap, and idx is which item to add next\n",
        "      q = [(-self.estimate(0, 0, self.c), 0, self.c, 0)] # estimate, val, left_cap, idx\n",
        "      self.best = 0\n",
        "      while q:\n",
        "        est, val, left_cap, idx = heapq.heappop(q)\n",
        "        est = -est\n",
        "        _, wi, vi = self.items[idx]\n",
        "\n",
        "        print(est, val, left_cap, idx, q, self.best, idx, vi)\n",
        "        if idx == self.n - 1:\n",
        "          self.best = max(self.best, val)\n",
        "          continue\n",
        "        \n",
        "        # Case 1: choose the item\n",
        "        nest = self.estimate(idx + 1, val + vi, left_cap - wi)\n",
        "        if nest > self.best:\n",
        "          heapq.heappush(q, (-nest, val + vi, left_cap - wi, idx + 1))\n",
        "\n",
        "        # Case 2: not choose the item\n",
        "        nest = self.estimate(idx + 1, val, left_cap)\n",
        "        if nest > self.best:\n",
        "          heapq.heappush(q, (-nest, val, left_cap, idx + 1))\n",
        "      return \n",
        "\n",
        "  def runDfs(self):\n",
        "      self.dfs(0, self.estimate(0, 0, self.c), 0, self.c, [])\n",
        "      return self.best\n",
        "\n",
        "  def runBfs(self):\n",
        "     self.bfs()\n",
        "     return self.best"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FI6aNwjvIUmZ",
        "colab_type": "code",
        "outputId": "75e10440-a1e1-4885-9fc1-264be5a78a61",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 237
        }
      },
      "source": [
        "bnb = BranchandBound(c, v, w)\n",
        "bnb.runDfs()\n",
        "bnb.runBfs()"
      ],
      "execution_count": 194,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[(11.666666666666666, 3, 35), (9.0, 5, 45), (6.0, 8, 48)]\n",
            "[] 0 10 92.0\n",
            "[True] 35 7 92.0\n",
            "[True, True] 80 2 92.0\n",
            "[True, False] 35 7 77.0\n",
            "[False] 0 10 75.0\n",
            "92.0 0 10 0 [] 0 0 35\n",
            "92.0 35 7 1 [(-75.0, 0, 10, 1)] 0 1 45\n",
            "92.0 80 2 2 [(-77.0, 35, 7, 2), (-75.0, 0, 10, 1)] 0 2 48\n",
            "77.0 35 7 2 [(-75.0, 0, 10, 1)] 80 2 48\n",
            "75.0 0 10 1 [] 80 1 45\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "80"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 194
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lCtOMorH5DJ5",
        "colab_type": "text"
      },
      "source": [
        "### Eight Queen"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8Voc6wAPiBeW",
        "colab_type": "code",
        "outputId": "bec2f965-0a97-421e-ea93-05c8bf5ef1b7",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "n=(64*63*62*61*60*59*58*57)/(8*7*6*5*4*3*2*1)\n",
        "print(n)"
      ],
      "execution_count": 195,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "4426165368.0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "O6R0rgFA5Hbm",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class Solution:\n",
        "    def solveNQueens(self, n):\n",
        "        \"\"\"\n",
        "        :type n: int\n",
        "        :rtype: List[List[str]]\n",
        "        \"\"\"\n",
        "        # queen can move: vertically, horizontally, diagonally \n",
        "        col_state = [False]*n\n",
        "        #diag =[False]*n\n",
        "        left_diag = [False]* (2*n-1) # x+y -> index\n",
        "        right_diag = [False]* (2*n-1) # x+(n-1-y) ->index\n",
        "        n_queen = [] # to track the positions\n",
        "        ans = []\n",
        "        board = [['.' for i in range(n)] for j in range(n)] #initialize as '.' we can try to flip\n",
        "        def collect_solution():\n",
        "            board = [['.' for i in range(n)] for j in range(n)] \n",
        "            for i, j in enumerate(n_queen):\n",
        "                board[i][j] = 'Q'\n",
        "                \n",
        "            for i in range(n):\n",
        "                board[i] = ''.join(board[i])\n",
        "            return board\n",
        "        \n",
        "        def is_valid(r, c):\n",
        "            return not (col_state[c] or left_diag[r+c] or right_diag[r+(n-1-c)])\n",
        "          \n",
        "        def set_state(r, c, val):\n",
        "            col_state[c] = val\n",
        "            #diag[abs(r-c)] = val\n",
        "            left_diag[r+c] = val\n",
        "            right_diag[r+(n-1-c)] = val\n",
        "            \n",
        "        def backtrack(n_queen, k):\n",
        "            if k == n: # a valid result\n",
        "                ans.append(collect_solution())\n",
        "                return\n",
        "            # generate candidates for kth queen\n",
        "            for col in range(n):\n",
        "                if is_valid(k, col):\n",
        "                    set_state(k, col, True)\n",
        "                    n_queen.append(col)\n",
        "                    backtrack(n_queen, k+1)\n",
        "                    set_state(k, col, False)\n",
        "                    n_queen.pop()\n",
        "                \n",
        "        backtrack(n_queen, 0)\n",
        "        return ans\n",
        "      \n",
        "    def solveNQueens2(self, n):\n",
        "      \"\"\"\n",
        "      :type n: int\n",
        "      :rtype: List[List[str]]\n",
        "      \"\"\"\n",
        "      n_queen = [] # to track the positions\n",
        "      ans = []\n",
        "      board = [['.' for i in range(n)] for j in range(n)] #initialize as '.' we can try to flip\n",
        "      def collect_solution():\n",
        "          board = [['.' for i in range(n)] for j in range(n)] \n",
        "          for i, j in enumerate(n_queen):\n",
        "              board[i][j] = 'Q'\n",
        "\n",
        "          for i in range(n):\n",
        "              board[i] = ''.join(board[i])\n",
        "          return board\n",
        "          \n",
        "      def generate_candidate(n_queen, k, n):\n",
        "        if k == 0: #the first row, then the candidates row is all columns\n",
        "          return set([i for i in range(n)])\n",
        "        # generate candidate in kth level based on previous levels\n",
        "        candidates = set([i for i in range(n)])\n",
        "        for r, c in enumerate(n_queen):\n",
        "          if c in candidates:\n",
        "            candidates.remove(c)\n",
        "          c1 = c-(k-r)\n",
        "          if c1 >=0 and c1 in candidates:\n",
        "            candidates.remove(c1)\n",
        "          c2 = c+(k-r)\n",
        "          if c2 < n and c2 in candidates:\n",
        "            candidates.remove(c2)\n",
        "        return candidates\n",
        "\n",
        "      def backtrack(n_queen, k):\n",
        "          if k == n: # a valid result\n",
        "              ans.append(collect_solution())\n",
        "              return\n",
        "          # generate candidates for kth queen\n",
        "          candidates = generate_candidate(n_queen, k, n)\n",
        "          for c in candidates:\n",
        "              n_queen.append(c)\n",
        "              backtrack(n_queen, k+1)\n",
        "              n_queen.pop()\n",
        "\n",
        "      backtrack(n_queen, 0)\n",
        "      return ans"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0WhwqD8Ri-Z6",
        "colab_type": "code",
        "outputId": "1e1d48aa-bae3-49ac-e437-356ca827be8c",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 72
        }
      },
      "source": [
        "import time\n",
        "s = Solution()\n",
        "n = 4\n",
        "t0 = time.time()\n",
        "ans = s.solveNQueens(n)\n",
        "print(ans)\n",
        "t1 = time.time()\n",
        "print('time: ', t1-t0)\n",
        "ans2 = s.solveNQueens2(n)\n",
        "t2 = time.time()\n",
        "print('time: ', t2-t1)"
      ],
      "execution_count": 197,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]\n",
            "time:  0.0006678104400634766\n",
            "time:  0.0014612674713134766\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XWc4fJNy43yT",
        "colab_type": "text"
      },
      "source": [
        "#### Utilize symmetry"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "algw5Z8N42ya",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "    def solveNQueensSymmetry(n):\n",
        "      \"\"\"\n",
        "      :type n: int\n",
        "      :rtype: List[List[str]]\n",
        "      \"\"\"\n",
        "      n_queen = [] # to track the positions\n",
        "          \n",
        "      def generate_candidate(n_queen, s, k, n):\n",
        "        if k == s: #apply symmetry\n",
        "          candidates = set([i for i in range(n//2)])\n",
        "        else:\n",
        "          candidates = set([i for i in range(n)])\n",
        "\n",
        "        for r, c in enumerate(n_queen):\n",
        "          if c in candidates:\n",
        "            candidates.remove(c)\n",
        "          c1 = c-(k-r)\n",
        "          if c1 >=0 and c1 in candidates:\n",
        "            candidates.remove(c1)\n",
        "          c2 = c+(k-r)\n",
        "          if c2 < n and c2 in candidates:\n",
        "            candidates.remove(c2)\n",
        "        return candidates\n",
        "\n",
        "      def backtrack(n_queen, s, k, ans):\n",
        "          '''add s to track the start depth'''\n",
        "          if k == n: # a valid result\n",
        "              ans += 1\n",
        "              return ans\n",
        "          # generate candidates for kth queen\n",
        "          candidates = generate_candidate(n_queen, s, k, n)\n",
        "          for c in candidates:\n",
        "              n_queen.append(c)\n",
        "              ans = backtrack(n_queen, s, k+1, ans)\n",
        "              n_queen.pop()\n",
        "          return ans\n",
        "        \n",
        "      # deal with the left half of the first row\n",
        "      ans = 0\n",
        "\n",
        "      ans += backtrack(n_queen, 0, 0, 0)*2\n",
        "      \n",
        "      # deal with the left half of the second row\n",
        "      if n%2 == 1:\n",
        "        n_queen = [n//2]\n",
        "        ans += backtrack(n_queen, 1, 1, 0)*2\n",
        "      return ans"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZIJaJ4xb6WA2",
        "colab_type": "code",
        "outputId": "1eddfd0c-9ff9-4ba6-8e13-da650fee3efb",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "print(solveNQueensSymmetry(7))"
      ],
      "execution_count": 199,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "40\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "r1QQMOyymOmk",
        "colab_type": "text"
      },
      "source": [
        "## Answers to Exercises"
      ]
    }
  ]
}