D_Yarema_Taras-Laboratori_6.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "1Nk3C0isssGo"
   },
   "source": [
    "# <span class=\"tema\">(Ordenar i cerca)</span> Nombres estrictament creixents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "wtfhbqUnssGp"
   },
   "source": [
    "Donat un enter N entre 1 i 9, trobar tots els nombres amb N dígits, dels quals el valor  dels dígits és estrictament creixent.\n",
    "    \n",
    "Per exemple si N=8 els nombres amb dígits estrictament creixents seran: 12345678, 12345679, 12345689, 12346789, 12356789, 12456789, 13456789, 23456789 (**falta un número...**)\n",
    "\n",
    "*Pista*: Podeu pensar en una solució recursiva que vagi generant els números de manera incremental"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conceptualització problema\n",
    "\n",
    "####  Quina solució hauria de donar per als següents valors: $N=9$ i $N=2$?\n",
    "\n",
    "```\n",
    "estrictamentCreixents(9) = {123456789}\n",
    "```\n",
    "\n",
    "```\n",
    "estrictamentCreixents(2) = {12, 13, 14, 15, 16, 17, 18, 19, 23, 24, 25, 26, 27, 28, 29, 34, 35, 36, 37, 38, 39, 45, 46, 47, 48, 49, 56, 57, 58, 59, 67, 68, 69, 78, 79, 89}\n",
    "```\n",
    "\n",
    "#### Imaginem que volem construir un número de 7 dígits ($N=7$) i que ja tenim escrit el nombre fins al dígit 5è ($12345$), quins passos hem de fer?\n",
    "\n",
    "Si $N=7$ i la cadena actual és \"$12345$\". El proper dígit, $m$, compleix $m \\in \\{ 6, 7, 8 \\}$.\n",
    "\n",
    "Per a cada possible $m$, es genera una nova solució encadenant \"$12345$\" i \"$m$\", i es realitza el mateix procediment per a la cadena \"$12345m$\", recursivament.\n",
    "\n",
    "#### Quantes possibilitats hi ha per cada dígit? Quantes combinacions hi ha? Revisa si cal la teoria de combinatòria.\n",
    "\n",
    "Sigui $N \\in \\{1, \\dots , 9\\}$ i $i \\in \\{1, \\dots , N\\}$ un índex. Definim les possibilitats del $i$-éssim dígit de un cert número per el $N$ donat com $D(i)$:\n",
    "\n",
    "$$\n",
    "D(i) = \\begin{cases}\n",
    "m \\in \\{1, \\dots , 10 - N\\} & \\text{si } i = 1 \\\\\n",
    "m \\in \\{D(i-1) + 1, \\dots, 9 - N + i\\} & \\text{altrament.}\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "D'aquesta definició podem deduïr que el cas del primer dígit, existeixen $10 - N$ possibles dígits. A partir del segon, n'hi han $9 - N + i$, on $i$ denota la posició.\n",
    "\n",
    "\n",
    "El número de combinacions possibles és:\n",
    "$$\n",
    "\\#\\{\\text{estrictamentCreixents($N$)}\\} = \\frac{9!}{N!(9-N)!}.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementació recursiva"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def estrictamentCreixents(n, p=[], numbers=set()):\n",
    "    if n == 0:\n",
    "        numbers.add(int(\"\".join(map(str, p))))\n",
    "        return \n",
    "    \n",
    "    if len(p) == 0:\n",
    "        i = 1\n",
    "        numbers = set()\n",
    "    else: \n",
    "        i = p[-1] + 1\n",
    "    \n",
    "    while i <= 10 - n:\n",
    "        estrictamentCreixents(n-1, p + [i], numbers)\n",
    "        i += 1\n",
    "        \n",
    "    return numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "estrictamentCreixents(8) = {12346789, 12345678, 12345679, 12356789, 12456789, 13456789, 23456789, 12345689, 12345789}\n"
     ]
    }
   ],
   "source": [
    "def prettyEstrictamentCreixents(n):\n",
    "    text = f\"estrictamentCreixents({n}) = \" + \"{\"\n",
    "    \n",
    "    for e in estrictamentCreixents(n):\n",
    "        text += f\"{e}, \"\n",
    "    \n",
    "    print(text[:-2] + \"}\")\n",
    "    \n",
    "prettyEstrictamentCreixents(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Itertools implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "a1ppGT5mssGs"
   },
   "outputs": [],
   "source": [
    "from itertools import combinations\n",
    "NUMBERS = [str(i) for i in range(1, 10)]\n",
    "    \n",
    "def estrictamentCreixentsItertools(n):\n",
    "    c = combinations(NUMBERS, n)\n",
    "    \n",
    "    return set([\n",
    "        int(\"\".join(n))\n",
    "        for n in c\n",
    "    ])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Testeig"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "N = 1\n",
      "Recursive: 0.000026 s.\n",
      "Itertools: 0.000014 s.\n",
      "\n",
      "N = 2\n",
      "Recursive: 0.000123 s.\n",
      "Itertools: 0.000038 s.\n",
      "\n",
      "N = 3\n",
      "Recursive: 0.000350 s.\n",
      "Itertools: 0.000081 s.\n",
      "\n",
      "N = 4\n",
      "Recursive: 0.000574 s.\n",
      "Itertools: 0.000102 s.\n",
      "\n",
      "N = 5\n",
      "Recursive: 0.000295 s.\n",
      "Itertools: 0.000057 s.\n",
      "\n",
      "N = 6\n",
      "Recursive: 0.000231 s.\n",
      "Itertools: 0.000041 s.\n",
      "\n",
      "N = 7\n",
      "Recursive: 0.000243 s.\n",
      "Itertools: 0.000259 s.\n",
      "\n",
      "N = 8\n",
      "Recursive: 0.000041 s.\n",
      "Itertools: 0.000007 s.\n",
      "\n",
      "N = 9\n",
      "Recursive: 0.000008 s.\n",
      "Itertools: 0.000002 s.\n",
      "\n",
      "Ran 9 tests: OK.\n"
     ]
    }
   ],
   "source": [
    "from time import time\n",
    "from math import factorial\n",
    "\n",
    "for i in range(1, 10):\n",
    "    print(f\"N = {i}\")\n",
    "    assert estrictamentCreixents(i) == estrictamentCreixentsItertools(i)\n",
    "    \n",
    "    t = time()\n",
    "    estrictamentCreixents(i)\n",
    "    t = time() - t\n",
    "    print(f\"Recursive: {t:2.6f} s.\")\n",
    "    \n",
    "    t = time()\n",
    "    estrictamentCreixentsItertools(i)\n",
    "    t = time() - t\n",
    "    print(f\"Itertools: {t:2.6f} s.\\n\")\n",
    "    \n",
    "print(\"Ran 9 tests: OK.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "oeZlcZPissGw"
   },
   "source": [
    "### Avaluació (0 a 10 punts)\n",
    "\n",
    "\n",
    "Concepte | Puntuació \n",
    "--- | --- \n",
    "Solució correcta i eficient | **8** punts\n",
    "Resposta correcta i clara a les preguntes | **+1** punt\n",
    "Solució correcta ineficient | **2** punts \n",
    "Codi comentat i seguint estàndar PEP8 | **+1** punt \n",
    "S'ofereix una funció adicional per mostrar la solució elegantment| **+0.5** punts \n",
    "L'algorisme falla repetidament | **-7** punts \n",
    "L'algorisme falla en algun cas excepcional | **-4** punt\n",
    "No es donen prous exemples d'execució | **-1** punt\n",
    "Codi, noms de variables, solució o comentaris no prou clars | **-1** punt\n",
    "La funció o els paràmetres no s'anomenen com a l'exemple | **-1** punt"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "NombresCreixents.ipynb",
   "provenance": []
  },
  "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}