{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Premiers pas dans Sage Math\n",
    "\n",
    "L'objectif de ce cours est de présenter des outils et des structures de données classiques pour intéragir avec le système de calcul formel Sage."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ## Trouver de l'aide\n",
    " \n",
    " Pour trouver de l'aide, il suffit de taper le nom mathématique de l'objet que vous souhaitez utiliser (en utilisant une majuscule) suivi d'un point d'intérogation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Permutations?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Standard permutations of 3"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = Permutations(3); p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list( p )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si vous ne connaissez pas le nom de la fonction mathématique, vous pouvez le deviner en écrivant les premières lettre puis en tapant sur la touche tabulation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "PolynomialRing?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vous pouvez aussi voir le code source d'un programme en mettant deux points d'interrogation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Permutations??"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - On peut trouver de nombreux tutoriels dans la page Help de l'interface jupyter. Il y a des tutoriels et une API complète des objets disponibles.\n",
    "\n",
    " - Essayer de trouver un tutoriel de programmation Python, un tutoriel pour utiliser l'algèbre linéaire, un tutoriel pour utiliser les fonctions symétriques, et l'API des arbres binaires."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ## Sauts conditionnels, fonctions et boucles\n",
    "  - Dans python, les sauts conditionnels se font de la manière suivante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a est paire.\n"
     ]
    }
   ],
   "source": [
    "a = 30\n",
    "if( a % 2 == 0 ):\n",
    "    print( \"a est paire.\" )\n",
    "else:\n",
    "    print( \"a est impaire.\" )\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Exercice : \n",
    "Soit \"a\" l'age d'une personne, donnez une algorithme qui retourne : \n",
    " - enfant, si l'age de la personne est inférieur ou égal à 13\n",
    " - Adolescent, si l'age de la personne est inférieur ou égal à 18\n",
    " - Adulte, si l'age de la personne est supérieur à 18\n",
    " - Alien, sinon ;)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "alien\n"
     ]
    }
   ],
   "source": [
    "a = -3\n",
    "if a > 0 and a < 13:\n",
    "    print('enfant')\n",
    "elif a >= 13 and a< 18:\n",
    "    print('adolescent')\n",
    "elif a>=18:\n",
    "    print('adulte')\n",
    "else:\n",
    "    print('alien')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fonction :\n",
    "une fonction est déclarée à l'aide du mot clé **def**. Reprenons l'exercice précédent afin de créer une fonction caractiristique(age)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def caractiristique(age):\n",
    "    if a > 0 and a < 13:\n",
    "        return('enfant')\n",
    "    elif a >= 13 and a< 18:\n",
    "        return('adolescent')\n",
    "    elif a>=18:\n",
    "        return('adulte')\n",
    "    else:\n",
    "        return('alien')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'alien'"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "caractiristique(12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercice**: Ecrire une fonction qui prend en paramètre un réel x et qui renvoit le max entre $x^2$ et $2x+1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def maxi(x):\n",
    "    return max(x^2,2*x+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maxi(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Les boucles \n",
    "\n",
    "On utilise dans les boucles la fonction range qui retourne une liste. Cherchez la documentation de la fonction range. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "range?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " **exercice** : listez à l'aide de la fonction range les valeurs paires comprise entre -5 et 21"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-4, -2, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "range(-4,21,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Boucle For :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "C est la fin\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "i=2\n",
    "n=10\n",
    "for i in range(n):\n",
    "    print(i)\n",
    "print(\"C est la fin\")\n",
    "print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{}\n",
      "{1}\n",
      "{2}\n",
      "{3}\n",
      "{4}\n",
      "{1, 2}\n",
      "{1, 3}\n",
      "{1, 4}\n",
      "{2, 3}\n",
      "{2, 4}\n",
      "{3, 4}\n",
      "{1, 2, 3}\n",
      "{1, 2, 4}\n",
      "{1, 3, 4}\n",
      "{2, 3, 4}\n",
      "{1, 2, 3, 4}\n"
     ]
    }
   ],
   "source": [
    "for e in Subsets(4):\n",
    "    print( e )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercice**: Ecrire une fonction f qui calcule le n ième terme de la suite $u_n=u_{n-1}+u_{n-1}$ avec $u_{0}=0$ et $u_1=1$ "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def f(n):\n",
    "    u0=0\n",
    "    u1=1\n",
    "    for i in range(2,n+1):\n",
    "        un=u1+u0\n",
    "        u0=u1\n",
    "        u1=un\n",
    "    if n>1:\n",
    "        return un\n",
    "    elif n==1:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Boucle WHILE :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "sortie i : 10\n"
     ]
    }
   ],
   "source": [
    "n=10\n",
    "i=2\n",
    "while i < n:\n",
    "    print(i)\n",
    "    i = i+1\n",
    "print(\"sortie i : \" + str(i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercice**: Donner une fonction qui calcule le plus proche entier de $\\log_2(n)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def proche(n):\n",
    "    i=0\n",
    "    while n> 2^i:\n",
    "        i=i+1\n",
    "    return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "proche(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ## Les listes\n",
    " - Dans python, les listes sont codées à l'aide des crochets. Par exemple, voici comment on écrit la liste [1, 2, 3, 4]:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "l = [1,2,3,4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "l.append(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 10]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - On peut écrire des listes en utilisant des boucles :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = []\n",
    "for i in range(10):\n",
    "    l.append(i)\n",
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - On peut aussi le faire plus rapidement de la façon suivante:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[ i^2 for i in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - On peut créer des listes de différents objets. Par exemple, voici la liste de toutes les permutations de taille 4:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 3, 4],\n",
       " [1, 2, 4, 3],\n",
       " [1, 3, 2, 4],\n",
       " [1, 3, 4, 2],\n",
       " [1, 4, 2, 3],\n",
       " [1, 4, 3, 2],\n",
       " [2, 1, 3, 4],\n",
       " [2, 1, 4, 3],\n",
       " [2, 3, 1, 4],\n",
       " [2, 3, 4, 1],\n",
       " [2, 4, 1, 3],\n",
       " [2, 4, 3, 1],\n",
       " [3, 1, 2, 4],\n",
       " [3, 1, 4, 2],\n",
       " [3, 2, 1, 4],\n",
       " [3, 2, 4, 1],\n",
       " [3, 4, 1, 2],\n",
       " [3, 4, 2, 1],\n",
       " [4, 1, 2, 3],\n",
       " [4, 1, 3, 2],\n",
       " [4, 2, 1, 3],\n",
       " [4, 2, 3, 1],\n",
       " [4, 3, 1, 2],\n",
       " [4, 3, 2, 1]]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[ p for p in Permutations(4)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - En fait, on aurait put faire :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "P = Permutations(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Standard permutations of 4"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - Il est possible d’utiliser les boucles et les sauts conditionnels dans des listes. Par exemple, voilà comment on sélectionne toutes les permutations qui finissent pas une descente (On rappelle que i est une descente dans une permutation p si (p(i)>p(i+1))):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "[p for p in Permutations(5) if p(4)>p(5) ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Il est possible d'obtenir la taille d'une liste"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "60"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [p for p in Permutations(5) if p(4)>p(5)] \n",
    "len( l )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercice**: ecrire une fonction pour lister les points fixes d'une permutation. Puis, une autre fonction pour lister toutes les permustations sans points fixes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def point_fixes( p ):\n",
    "    \"\"\"\n",
    "    renvoie la liste des points fixes d'une permutation donnée en paramètre.\n",
    "    \"\"\"\n",
    "    n = len (p )\n",
    "    resultat = []\n",
    "    for i in range(1, n+1):\n",
    "        if p[i-1] == i:\n",
    "            resultat.append( i )\n",
    "    return resultat\n",
    "\n",
    "permutation_sans_points_fixes = [p for p in Permutations(5) if len( point_fixes(p))==0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "p=[3,2,4,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "point_fixes(p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - On peut générer la série génératrice des permutations sans point fixe comptées par leurs tailles de la manière suivante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1854*x^7 + 265*x^6 + 44*x^5 + 9*x^4 + 2*x^3 + x^2 + 1"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def nb_sans_pf(n):\n",
    "    return len(\n",
    "        [ \n",
    "            p \n",
    "            for p in Permutations(n)\n",
    "            if len(point_fixes(p))==0\n",
    "        ] \n",
    "    )\n",
    "    \n",
    "S = sum( nb_sans_pf(n)*x^n for n in range(8) )\n",
    "S"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - On peut collecter la suite et faire une recherche directement en ligne sur Sloane."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0: A000166: Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.\n",
       "1: A260081: Number of permutations p of [n] with no fixed points and cyclic displacement of elements restricted by three: p(i)<>i and (i-p(i) mod n <= 3 or p(i)-i mod n <= 3).\n",
       "2: A257953: Number of permutations p of [n] with no fixed points and cyclic displacement of elements restricted by nine: p(i)<>i and (i-p(i) mod n <= 9 or p(i)-i mod n <= 9)."
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "oeis([ nb_sans_pf(n) for n in range(8) ])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ## Exercices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - En utilisant les exemples précédents, écrivez un programme qui donne la liste de tous les multiple de 2 plus petit que 30."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "li= [2*i for i in range(15)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "li"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - Proposer un algorithme qui calcul le binomial (n,k) en utilisant le triangle de Pascal, c'est à dire en utilisant la formule de récurrence suivante :\n",
    " $$ \\binom{n+1}{k}=\\binom{n}{k}+\\binom{n}{k-1} $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def binomial2(n,k):\n",
    "    if k<0 or k>n:\n",
    "        return 0\n",
    "    bino = [ 0 for i in range(k+1) ]   #  [0, 0, 0, 0, ... ] (il y en a k+1)\n",
    "    bino[0] = 1\n",
    "    for i in range(n):\n",
    "        for j in range(k, 0, -1):\n",
    "            bino[j] = bino[j] + bino[j-1]\n",
    "    return bino[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "binomial2(5,3) == factorial(5)/( factorial(3)*factorial(2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - En fait binomial existe déjà sur Sage. Trouvez la fonction !!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all( [ binomial(i,j) == binomial2(i,j)  for i in range(10) for j in range(10) ] )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ## Les dictionnaires\n",
    "  - Les dictionnaires sont des structures de données qui permettent d'associer un objet appelé clé à un autre objet appelé valeur. Les clés sont toutes deux à deux différentes. Un dictionnaire est une application à support fini. Voici un exemple de dictionnaire :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: 4, 2: 6, 3: 6, 8: 6}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = {1:4, 2:6, 3:6, 8:6}\n",
    "D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[8, 1, 2, 3]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D.keys()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " **Question**: Comment faire pour :\n",
    "             - si un dictionnaire contient une clef donnée\n",
    "             - acceder a la valeur associée a cette clef\n",
    "             - le nombre de clefs\n",
    "                "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercice** Ecrire une fonction qui prend en paramètre une liste d'entiers et qui revoit un dictionnaire dont les clefs sont les entiers présent dans la liste et les valeurs leur nombre de répétition."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ## Les générateurs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Les générateurs sont des programmes qui servent à énumérer des objets à la demande. Par exemples, l'objet Permutations (qui code l'ensemble des permutations) contient un générateur que l'on obtient en tapant :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "generateur = iter( Permutations(3) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - On peut ensuite énumérer les permutations une à une en tapant :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print( next( generateur ) )\n",
    "print( next( generateur ) )\n",
    "print( next( generateur ) )\n",
    "print( next( generateur ) )\n",
    "print( next( generateur ) )\n",
    "print( next( generateur ) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - Un erreur est levée quand on arrive à la fin de l'itérateur\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print( next( generateur ) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - L'intérêt des générateurs, c'est qu'il permet à l'utilisateur de ne pas devoir créer toute la liste des objets pour pouvoir la manipuler. C'est particulièrement pratique quand l'ensemble à énumérer est grand ou infini. Par exemple, on peut avoir un générateur pour les permutations :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "generateur = iter(Permutations())\n",
    "print( next(generateur) ) \n",
    "print( next(generateur) ) \n",
    "print( next(generateur) ) \n",
    "print( next(generateur) ) \n",
    "print( next(generateur) ) \n",
    "print( next(generateur) ) \n",
    "print( next(generateur) ) \n",
    "print( next(generateur) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - Il est possible d'utiliser les itérateurs directement dans la boucle for :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "gen = iter( Permutations(3) )\n",
    "for p in gen:\n",
    "    print( p )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - En fait, range(4) est un itérateur."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "gen = range(5)\n",
    "print( next(gen) )\n",
    "print( next(gen) )\n",
    "print( next(gen) )\n",
    "print( next(gen) )\n",
    "print( next(gen) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - Vous pouvez implémenter votre propre générateur. Il suffit, pendant votre calcul de retourner la valeur à l'aide du mot clé yield. Yield, va créer un itérateur qui va garder en mémoire l'endroit où le programme s'est arrếté. Il reprendra son exécution à ce point lorsque l'on demandera une nouvelle valeur à l'itérateur."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def generateur_nombre_carre( n ):\n",
    "     for i in range(n):\n",
    "         yield i**2\n",
    "\n",
    "gen = generateur_nombre_carre( 30 )\n",
    "print( next(gen) )\n",
    "print( next(gen) )\n",
    "print( next(gen) )\n",
    "print( next(gen) )\n",
    "print( next(gen) )\n",
    "print( next(gen) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ## Exercices :\n",
    "  - Ecrivez un générateur qui engendre toutes les permutations de taille n."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - Ecrivez un générateur qui engendre toutes les listes d'entiers strictement positif dont la somme est égal à un entier donné en paramètre. On appelle cela une composition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - Cherchez dans sage, si les compositions sont déjà implémentées."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Projet Euler"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - Entraînez vous en prenant les problèmes du projet Euler et en essayant de les résoudre avec le moins de code possible.\n",
    "\n",
    "https://projecteuler.net/\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 7.3",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}