{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "metric-consortium",
   "metadata": {},
   "source": [
    "# Recursion (3/3 - 2021)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "knowing-study",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "Given two non-negative integers ``a`` and ``b``, compute ``power(a, b) == a ** b`` using recursion, without using ``**``, i.e. only using multiplication, division, addision and subtraction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "signal-stephen",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "power(10,10)\n",
      "power(10,5)\n",
      "power(10,4)\n",
      "power(10,2)\n",
      "power(10,1)\n",
      "power(10,0)\n",
      "10000000000\n"
     ]
    }
   ],
   "source": [
    "def power(a, b):\n",
    "    print(f'power({a},{b})')\n",
    "    if b == 0:\n",
    "#        print('b=0')\n",
    "        return 1\n",
    "    if b % 2 == 0:  # b even\n",
    "        # exploit a ** (2 * b) == (a ** b) ** 2\n",
    "        \n",
    "#        print('even call')\n",
    "        p = power(a, b // 2)\n",
    "        return p * p\n",
    "#        print('odd call')\n",
    "    return a * power(a, b - 1)\n",
    "    \n",
    "print(power(10, 10))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "baking-projector",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "Convert a recursive tuple to a nicely indented string. E.g. ``dump(((1, 3), (5, (4, 6))))`` could become\n",
    "\n",
    "<pre>\n",
    "(\n",
    "   (\n",
    "      1,\n",
    "      3\n",
    "   ),\n",
    "   (\n",
    "      5,\n",
    "      (\n",
    "         4,\n",
    "         6\n",
    "      )\n",
    "   )\n",
    ")\n",
    "</pre>\n",
    "\n",
    "similar to what you achieve for lists using\n",
    "\n",
    "```\n",
    "import json\n",
    "print(json.dumps([[1,3],[5,[4,6]]], indent=3))\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "civilian-supply",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(\n",
      "   (\n",
      "      1,\n",
      "      3\n",
      "   ),\n",
      "   (\n",
      "      5,\n",
      "      (\n",
      "         4,\n",
      "         6\n",
      "      )\n",
      "   )\n",
      ")\n"
     ]
    }
   ],
   "source": [
    "def dump(tree, *, indent_level=0, indent=3):    \n",
    "    prefix = indent * indent_level * ' '\n",
    "    if type(tree) is not tuple:\n",
    "        return prefix + str(tree)\n",
    "    else:\n",
    "        children = [\n",
    "            dump(child, indent=indent, indent_level=indent_level + 1)\n",
    "            for child in tree\n",
    "        ]\n",
    "        return prefix + '(\\n' + ',\\n'.join(children) + '\\n' + prefix + ')'\n",
    "    \n",
    "tree = ((1,3),4,((5,6), (7, (8, 9))))\n",
    "tree = ((1,3),(5,(4,6)))\n",
    "\n",
    "assert tree == eval(dump(tree))\n",
    "\n",
    "print(dump(tree))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "hundred-jewel",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "Create a recursive function ``subsets(L, k)`` that given a list ``L`` and an integer ``k``, returns a list of all subsets of ``L`` of size ``k``. It is assumed all elements are distinct. E.g. ``subsets([1,2,3,4,5], 3)`` should return\n",
    "\n",
    "```\n",
    "[[3, 4, 5], [2, 4, 5], [2, 3, 5], [2, 3, 4], [1, 4, 5], [1, 3, 5], [1, 3, 4], [1, 2, 5], [1, 2, 4], [1, 2, 3]]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "split-document",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[3, 4, 5], [2, 4, 5], [2, 3, 5], [2, 3, 4], [1, 4, 5], [1, 3, 5], [1, 3, 4], [1, 2, 5], [1, 2, 4], [1, 2, 3]]\n"
     ]
    }
   ],
   "source": [
    "def subsets(L, k):\n",
    "#    print('*', end='')\n",
    "    if k == 0:\n",
    "        return [[]]\n",
    "    if k > len(L):\n",
    "        return []\n",
    "    if k == len(L):\n",
    "        return [L.copy()]\n",
    "    head, *tail = L\n",
    "#    head = L[0]\n",
    "#    tail = L[1:]\n",
    "    \n",
    "    answer = subsets(tail, k)\n",
    "    for subset in subsets(tail, k - 1):\n",
    "#        answer.append([head] + subset)\n",
    "        answer.append([head, *subset])\n",
    "    return answer\n",
    "\n",
    "print(subsets(list(range(1, 6)), 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "operational-shock",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[3, 4, 5], [2, 4, 5], [2, 3, 5], [2, 3, 4], [1, 4, 5], [1, 3, 5], [1, 3, 4], [1, 2, 5], [1, 2, 4], [1, 2, 3]]\n"
     ]
    }
   ],
   "source": [
    "def subsets(L, k):\n",
    "#    print('*', end='')\n",
    "    if k == 0:\n",
    "        return [[]]\n",
    "    if k > len(L):\n",
    "        return []\n",
    "    if k == len(L):  # Case can be omittted\n",
    "        return [L.copy()]\n",
    "    head, *tail = L\n",
    "    \n",
    "    return subsets(tail, k) + [[head, *subset] for subset in subsets(tail, k - 1)]\n",
    "\n",
    "print(subsets(list(range(1, 6)), 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bound-sound",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "Create ``subsets(L, k)`` without using recursion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "designed-assignment",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]\n"
     ]
    }
   ],
   "source": [
    "# Idea: repeatedly extend solutions of size i to size i + 1\n",
    "\n",
    "def subsets(L, k):\n",
    "    L = sorted(L)\n",
    "    if k == 0:\n",
    "        S = [[]]  \n",
    "    if k > len(L):\n",
    "        return []\n",
    "    S = [[x] for x in L]  # subsets of size 1\n",
    "    for _ in range(k - 1):  # extend exisiting solutions with one more element\n",
    "        # assumes S is a sorted list of distinct elements\n",
    "     #   print(f'{S=}')\n",
    "        S = [subset + [x] for subset in S for x in L if x > subset[-1]]   \n",
    "     #  S = [[*subset, x] for subset in S for x in L if x > subset[-1]]   # use * notation\n",
    "\n",
    "    return S\n",
    "\n",
    "print(subsets(list(range(1, 6)), 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "distinct-yield",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 5], [1, 3, 5], [2, 3, 5], [1, 4, 5], [2, 4, 5], [3, 4, 5]]\n"
     ]
    }
   ],
   "source": [
    "#  L = [x, x, x, x, x, x, x, x, x, x, x, x, x, x]\n",
    "#                                     ^\n",
    "#       |--S=subsets of size <= k--|  x\n",
    "\n",
    "# Idea: Construct all subsets of size <= k of L[:i]\n",
    "\n",
    "def subsets(L, k):\n",
    "    if k > len(L):\n",
    "        return []\n",
    "    S = [[]]  # all subsets of L[:0], ie. only \n",
    "    for x in L:\n",
    "        for s in S.copy():\n",
    "        #for s in S[:]:\n",
    "        #for s in S[::]:\n",
    "        #for s in list(S):\n",
    "            if len(s) < k:\n",
    "                S.append([*s, x]) \n",
    "            #print(f'..{x=} {s=} {S=}')\n",
    "        #print(f'{x=} {S=}')\n",
    "    return [s for s in S if len(s) == k]\n",
    "\n",
    "print(subsets(list(range(1, 6)), 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "amateur-update",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "L.copy() 1.2472410999998829\n",
      "L[:] 1.218890999999985\n",
      "L[::] 1.2248884000000544\n",
      "list(L) 1.2442267999999785\n"
     ]
    }
   ],
   "source": [
    "import timeit\n",
    "\n",
    "for cmd in ['L.copy()', 'L[:]', 'L[::]', 'list(L)']:\n",
    "    t = timeit.timeit(cmd, setup='L=list(range(1000000))', number=100)\n",
    "    print(cmd, t)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}