{
 "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 30\n",
    "if( a % 2 == 0 ):\n",
    "    print( \"a est even.\" )\n",
    "else:\n",
    "    print( \"a est odd.\" )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise :\n",
    "\n",
    "Let \"a\" be the age of an 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": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "```\n",
    "\n",
    "## The Loops\n",
    "\n",
    "Find in the documentation how to use the function *range()*.\n",
    "```{.python .input}\n",
    "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "```\n",
    "\n",
    "## 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 :\n",
    "```{.python .input}\n",
    "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "```\n",
    "```{.python .input}\n",
    "for e in Subsets(4):\n",
    "   print( e )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: Write a function $f$ that takes an integer $n$ and then returns the value $u_n$ defined by $u_n=u_{n-1}+u_{n-1}$ with $u_{0}=0$ and $u_1=1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "```\n",
    "\n",
    "## The loop WHILE :\n",
    "\n",
    "Loops can be written with the following format:\n",
    "```{.python .input}\n",
    "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": [
    "**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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "```\n",
    "\n",
    "## The 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 :\n",
    "```{.python .input}\n",
    "l = [1,2,3,4]\n",
    "l\n",
    "l.append(10)\n",
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   We can write some lists by using loops :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[p for p in Permutations(4)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   In fact it is possible to write :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "```\n",
    "\n",
    "-   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",
    "```{.python .input}\n",
    "def nb_without_fp(n):\n",
    "    return len(\n",
    "        [ \n",
    "            p \n",
    "            for p in Permutations(n)\n",
    "            if len(fixed_points(p))==0\n",
    "        ] \n",
    "    )\n",
    "S = sum( nb_without_fp(n)*x^n for n 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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "oeis([ nb_sans_pf(n) for n 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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "```\n",
    "\n",
    "-   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",
    "```{.python .input}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   In fact, the function *binomial* exists in Sage. Find that function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: 4, 2: 6, 3: 6, 8: 6}"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "```\n",
    "\n",
    "## The 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.\n",
    "```{.python .input}\n",
    "D = {1:4, 2:6, 3:6, 8:6}\n",
    "D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sage:"
   ]
  },
  {
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sage:"
   ]
  },
  {
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "generator = iter( Permutations(3) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   We can enumerate those permutations by writing :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gen = iter( Permutations(3) )\n",
    "for p in gen:\n",
    "    print( p )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   You can implement your own generator. It suffices, during the enumeration, to return 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 calculus. At each *next* the generator will continue the calculus and will return the next value of the enumeration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sage:"
   ]
  },
  {
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sage:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-   Find in the Sage documentation a composition generator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sage:"
   ]
  },
  {
   "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": {},
 "nbformat": 4,
 "nbformat_minor": 1
}