{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\def\\CC{\\bf C}\n",
    "\\def\\QQ{\\bf Q}\n",
    "\\def\\RR{\\bf R}\n",
    "\\def\\ZZ{\\bf Z}\n",
    "\\def\\NN{\\bf N}\n",
    "$$\n",
    "# First step in imperative programming\n",
    "\n",
    "Conditional jump, function and loop ----------------------------------\n",
    "\n",
    "-   In python, conditional jumps can be written with the following syntax :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a is even.\n"
     ]
    }
   ],
   "source": [
    "a = 30\n",
    "if( a % 2 == 0 ):\n",
    "    print( \"a is even.\" )\n",
    "else:\n",
    "    print( \"a is odd.\" )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise :\n",
    "\n",
    "Let \"a\" be the age of a human, give an algorithm that returns :\n",
    "\n",
    "-   \"child\", if it's age is lesser than 13\n",
    "-   \"teenager\", if it's age is greater that 13 and lesser than 18\n",
    "-   \"adult\", if it's age is greater or equal to 18\n",
    "-   \"Alien\", otherwise ;)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "alien\n"
     ]
    }
   ],
   "source": [
    "a = -3\n",
    "if a > 0 and a < 13:\n",
    "   print('child')\n",
    "elif a >= 13 and a< 18:\n",
    "   print('teenager')\n",
    "elif a>=18:\n",
    "   print('adult')\n",
    "else:\n",
    "   print('alien')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Function :\n",
    "\n",
    "A function can be declared with the keyword **def**. Come back to the last exercise and create a function $characteristic(age)$ that takes as parameter the age of an human and returns the previous characteristic."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'alien'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def characteristic(age):\n",
    "   if a > 0 and a < 13:\n",
    "       return('child')\n",
    "   elif a >= 13 and a< 18:\n",
    "       return('teenager')\n",
    "   elif a>=18:\n",
    "       return('adult')\n",
    "   else:\n",
    "       return('alien')\n",
    "characteristic(12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: Write a function that takes, in parameter, a real $x$ and then returns the maximum between $x^2$ and $2x+1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def some_max(x):\n",
    "    return max([x^2,2*x+1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "The Loops\n",
    "\n",
    "Find in the documentation how to use the function *range()*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "range?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise** : List, by using the function *range*, all the even values running from -5 to 21."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-5,\n",
       " -4,\n",
       " -3,\n",
       " -2,\n",
       " -1,\n",
       " 0,\n",
       " 1,\n",
       " 2,\n",
       " 3,\n",
       " 4,\n",
       " 5,\n",
       " 6,\n",
       " 7,\n",
       " 8,\n",
       " 9,\n",
       " 10,\n",
       " 11,\n",
       " 12,\n",
       " 13,\n",
       " 14,\n",
       " 15,\n",
       " 16,\n",
       " 17,\n",
       " 18,\n",
       " 19,\n",
       " 20,\n",
       " 21]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "range(-5,22)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "The loop For :\n",
    "\n",
    "In python, we can repeat the execution of some code. We call a loop each run of that code.\n",
    "\n",
    "Writing loop can be done in the following way :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "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": 1,
   "metadata": {
    "collapsed": false,
    "scrolled": 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": {
    "collapsed": true
   },
   "source": [
    "The loop WHILE :\n",
    "\n",
    "Loops can be written with the following format:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "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",
      "exit i : 10\n"
     ]
    }
   ],
   "source": [
    "n=10\n",
    "i=2\n",
    "while i < n:\n",
    "    print(i)\n",
    "    i = i+1\n",
    "print(\"exit i : \" + str(i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: Give a function that takes an integer $n$ as parameter and return the integer part of $\\log_2(n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def a_function(n):\n",
    "    return floor(log(n)/log(2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Lists\n",
    "\n",
    "- In python, lists are written by using with brackets. For example, the list \\[1, 2, 3, 4\\] can be coded with those lines :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [1,2,3,4]\n",
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 10]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l.append(10)\n",
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   We can write some lists by using loops :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = []\n",
    "for i in range(10):\n",
    "   l.append(i)\n",
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   We can also make it in one line :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[i^2 for i in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   We can create list of different objects. For example, the following code generate all the permutations of size 4:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "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": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[p for p in Permutations(4)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   In fact it is possible to write :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Standard permutations of 4"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P = Permutations(4)\n",
    "P"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   It is possible to use loops and conditional jumps inside lists. In the next example, we select all the permutations that finish on a descent. We recall that $i$ is a descent in a permutation $p$ if $p(i) \\ge p(i+1)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 3, 5, 4],\n",
       " [1, 2, 4, 5, 3],\n",
       " [1, 2, 5, 4, 3],\n",
       " [1, 3, 2, 5, 4],\n",
       " [1, 3, 4, 5, 2],\n",
       " [1, 3, 5, 4, 2],\n",
       " [1, 4, 2, 5, 3],\n",
       " [1, 4, 3, 5, 2],\n",
       " [1, 4, 5, 3, 2],\n",
       " [1, 5, 2, 4, 3],\n",
       " [1, 5, 3, 4, 2],\n",
       " [1, 5, 4, 3, 2],\n",
       " [2, 1, 3, 5, 4],\n",
       " [2, 1, 4, 5, 3],\n",
       " [2, 1, 5, 4, 3],\n",
       " [2, 3, 1, 5, 4],\n",
       " [2, 3, 4, 5, 1],\n",
       " [2, 3, 5, 4, 1],\n",
       " [2, 4, 1, 5, 3],\n",
       " [2, 4, 3, 5, 1],\n",
       " [2, 4, 5, 3, 1],\n",
       " [2, 5, 1, 4, 3],\n",
       " [2, 5, 3, 4, 1],\n",
       " [2, 5, 4, 3, 1],\n",
       " [3, 1, 2, 5, 4],\n",
       " [3, 1, 4, 5, 2],\n",
       " [3, 1, 5, 4, 2],\n",
       " [3, 2, 1, 5, 4],\n",
       " [3, 2, 4, 5, 1],\n",
       " [3, 2, 5, 4, 1],\n",
       " [3, 4, 1, 5, 2],\n",
       " [3, 4, 2, 5, 1],\n",
       " [3, 4, 5, 2, 1],\n",
       " [3, 5, 1, 4, 2],\n",
       " [3, 5, 2, 4, 1],\n",
       " [3, 5, 4, 2, 1],\n",
       " [4, 1, 2, 5, 3],\n",
       " [4, 1, 3, 5, 2],\n",
       " [4, 1, 5, 3, 2],\n",
       " [4, 2, 1, 5, 3],\n",
       " [4, 2, 3, 5, 1],\n",
       " [4, 2, 5, 3, 1],\n",
       " [4, 3, 1, 5, 2],\n",
       " [4, 3, 2, 5, 1],\n",
       " [4, 3, 5, 2, 1],\n",
       " [4, 5, 1, 3, 2],\n",
       " [4, 5, 2, 3, 1],\n",
       " [4, 5, 3, 2, 1],\n",
       " [5, 1, 2, 4, 3],\n",
       " [5, 1, 3, 4, 2],\n",
       " [5, 1, 4, 3, 2],\n",
       " [5, 2, 1, 4, 3],\n",
       " [5, 2, 3, 4, 1],\n",
       " [5, 2, 4, 3, 1],\n",
       " [5, 3, 1, 4, 2],\n",
       " [5, 3, 2, 4, 1],\n",
       " [5, 3, 4, 2, 1],\n",
       " [5, 4, 1, 3, 2],\n",
       " [5, 4, 2, 3, 1],\n",
       " [5, 4, 3, 2, 1]]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[p for p in Permutations(5) if p(4)>p(5) ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   It is possible to obtain the size of a list :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "60"
      ]
     },
     "execution_count": 13,
     "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": [
    "**Exercise**: Write a function to list all fixed points of a given permutation. Then, write another function that lists all permutations without fixed point."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fixed_points(permutation):\n",
    "    fixed_points = []\n",
    "    for i in range(len(permutation)):\n",
    "        if permutation[i] == i+1:\n",
    "            fixed_points += [i]\n",
    "    return fixed_points\n",
    "\n",
    "def derangements(n):\n",
    "    list_derangements = []\n",
    "    for perm in Permutations(n):\n",
    "        if len(fixed_points(perm)) == 0:\n",
    "            list_derangements += [perm]\n",
    "    return list_derangements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "We can generate the generating function of all permutations that have no fixed points. We will assume that $x$ counts the size of the permutations.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "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": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def nb_without_fp(n):\n",
    "    return len(derangements(n))\n",
    "S = sum( nb_without_fp(i)*x^i for i in range(8) )\n",
    "S"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   We can collect the sequence and obtain information about that sequence with OEIS."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "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": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "oeis([ nb_without_fp(i) for i in range(8) ])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercises\n",
    "\n",
    "-   By using the previous examples, write a program that gives the list of all even integers that are lesser than 30."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def even_thirty():\n",
    "    return [i for i in range(30) if i % 2 == 0]\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Propose an algorithm that computes the binomial $\\binom{n}{k}$ by using the Pascal triangle : $\\binom{n+1}{k}=\\binom{n}{k}+\\binom{n}{k-1}$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def my_binomial(n,k):\n",
    "    if k == 0 or n == k:\n",
    "        return 1\n",
    "    elif k == 1:\n",
    "        return n\n",
    "    elif k > n:\n",
    "        return 0\n",
    "    else:\n",
    "        return my_binomial(n-1,k) + my_binomial(n-1,k-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In fact, the function *binomial* exists in Sage. Find that function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "binomial(5,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Dictionaries\n",
    "\n",
    "- Dictionaries are data structures that allow to associate an object called key to another object called value. In a dictionary, all keys are different. In fact a dictionary is a map with finite support."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: 4, 2: 6, 3: 6, 8: 6}"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = {1:4, 2:6, 3:6, 8:6}\n",
    "D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[8, 1, 2, 3]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D.keys()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question**: How do you proceed to :\n",
    "\n",
    "-   determine if a dictionary contains a particular key;\n",
    "-   get a value associated to a key;\n",
    "-   get the number of keys."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D.has_key(5)\n",
    "D[8]\n",
    "len(D)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise** Write a function that takes as parameter a list of integers and then returns a dictionary where\n",
    "\n",
    "-   keys are all the integers present inside the list\n",
    "-   values, associated with the key, are the number of key repetitions inside the list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def multiplicity(a_list):\n",
    "    dict_mult = {}\n",
    "    for elmt in a_list:\n",
    "        if not dict_mult.has_key(elmt):\n",
    "            dict_mult[elmt] = 1\n",
    "        else:\n",
    "            dict_mult[elmt] += 1\n",
    "    return dict_mult"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The generators\n",
    "\n",
    "-   Generators are programs that are useful to enumerate objects on demand. For example, $Permutations(3)$ contains a generator of permutations of size 3. We obtain that generator by typing :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "generator = iter( Permutations(3) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   We can enumerate those permutations by writing :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n",
      "[1, 3, 2]\n",
      "[2, 1, 3]\n",
      "[2, 3, 1]\n",
      "[3, 1, 2]\n",
      "[3, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "print( next( generator ) )\n",
    "print( next( generator ) )\n",
    "print( next( generator ) )\n",
    "print( next( generator ) )\n",
    "print( next( generator ) )\n",
    "print( next( generator ) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   An error is raised when iterator reach the end of the iterator function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "StopIteration",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mStopIteration\u001b[0m                             Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-48-7b1f5606d239>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;32mprint\u001b[0m\u001b[0;34m(\u001b[0m \u001b[0mnext\u001b[0m\u001b[0;34m(\u001b[0m \u001b[0mgenerator\u001b[0m \u001b[0;34m)\u001b[0m \u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "print( next( generator ) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   Generators allow to obtain object one by one without computing a list of all the elements. This is useful when the list is big or infinite. For example, we can compute a generator for all the permutations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n",
      "[1]\n",
      "[1, 2]\n",
      "[2, 1]\n",
      "[1, 2, 3]\n",
      "[1, 3, 2]\n",
      "[2, 1, 3]\n",
      "[2, 3, 1]\n"
     ]
    }
   ],
   "source": [
    "generator = iter(Permutations())\n",
    "print( next(generator) ) \n",
    "print( next(generator) ) \n",
    "print( next(generator) ) \n",
    "print( next(generator) ) \n",
    "print( next(generator) ) \n",
    "print( next(generator) ) \n",
    "print( next(generator) ) \n",
    "print( next(generator) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   It is possible to use iterators inside a loop :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n",
      "[1, 3, 2]\n",
      "[2, 1, 3]\n",
      "[2, 3, 1]\n",
      "[3, 1, 2]\n",
      "[3, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "gen = iter( Permutations(3) )\n",
    "for p in gen:\n",
    "    print( p )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can implement your own generator. You only need to return, during the enumeration, the current value by using the keyword *yield*. At the first use of yield, python will create a generator that stores in memory all the states of the computation. At each *next* the generator will continue the computation and will return the next value of the enumeration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "4\n",
      "9\n",
      "16\n",
      "25\n"
     ]
    }
   ],
   "source": [
    "def generator( n ):\n",
    "     for i in range(n):\n",
    "         yield i**2\n",
    "gen = generator( 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": [
    "## Exercises :\n",
    "\n",
    "-   Write a generator that enumerates all permutations of size $n$ (without using the Sage generator of *Permutations*)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def permutation_iterator(n):\n",
    "    if n == 1:\n",
    "        yield [1]\n",
    "    else:\n",
    "        for prev_perm in permutation_iterator(n-1):\n",
    "            for i in range(n-1):\n",
    "                new_perm = prev_perm[:i] + [n] + prev_perm[i:]\n",
    "                yield new_perm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   Write a generator that enumerates all the compositions of an integer. A composition of $n$ is a list $l_1, l_2, \\ldots, l_k$ of integers such that $l_1 + l_2 + \\ldots + l_n = n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def my_composition_iterator(n):\n",
    "    if n == 0:\n",
    "        yield []\n",
    "    if n == 1:\n",
    "        yield [1]\n",
    "    else:\n",
    "        for first_summand in range(1,n+1):\n",
    "            for comp in my_composition_iterator(n-first_summand):\n",
    "                yield [first_summand] + comp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   Find in the Sage documentation a composition generator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Compositions?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Euler project\n",
    "\n",
    "-   Train yourself by solving problems from the Euler Project Website :\n",
    "\n",
    "<https://projecteuler.net/>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 7.5.beta3",
   "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": 1
}