First step in imperative programming
=====================================

Conditional jump, function and loop
----------------------------------

- In python, conditional jumps can be written with the following syntax :

::

    sage: a = 30
    ....: if( a % 2 == 0 ):
    ....:     print( "a est even." )
    ....: else:
    ....:     print( "a est odd." )
        



Exercise :
----------

Let "a" be the age of an human, give an algorithm that returns :

- "child", if it's age is lesser than 13

- "teenager", if it's age is greater that 13 and lesser than 18

- "adult", if it's age is greater or equal to 18 

- "Alien", otherwise ;).

::

    sage: a = -3
    ....: if a > 0 and a < 13:
    ....:    print('child')
    ....: elif a >= 13 and a< 18:
    ....:    print('teenager')
    ....: elif a>=18:
    ....:    print('adult')
    ....: else:
    ....:    print('alien')


Function :
----------

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.

::

    sage: def characteristic(age):
    ....:    if a > 0 and a < 13:
    ....:        return('child')
    ....:    elif a >= 13 and a< 18:
    ....:        return('teenager')
    ....:    elif a>=18:
    ....:        return('adult')
    ....:    else:
    ....:        return('alien')
    sage: characteristic(12)



**Exercise**: Write a function that takes, in parameter, a real `x`
and then returns the maximum between `x^2` and `2x+1`

::

    sage: 



The Loops
---------


Find in the documentation how to use the function *range()*.

::

    sage: range?

**Exercise** : List, by using the function *range*, all the even values
running from -5 to 21.

::

    sage: 



The loop For :
--------------

In python, we can repeat the execution of some code. We call a loop each run 
of that code.

Writing loop can be done in the following way :

::

    sage: i=2
    ....: n=10
    ....: for i in range(n):
    ....:     print(i)
    ....: print("C est la fin")
    ....: print(i)


    sage: for e in Subsets(4):
    ....:    print( e )


**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`.

::

    sage: 


The loop WHILE :
----------------

Loops can be written with the following format:

::

    sage: n=10
    ....: i=2
    ....: while i < n:
    ....:     print(i)
    ....:     i = i+1
    ....: print("sortie i : " + str(i))


**Exercise**: Give a function that takes an integer `n` as parameter and return 
the integer part of `\log_2(n)`.

::

    sage: 


The lists
----------

-  In python, lists are written by using with brackets. For example, the list 
[1, 2, 3, 4] can be coded with those lines :

::

    sage: l = [1,2,3,4]
    sage: l
    sage: l.append(10)
    sage: l

-  We can write some lists by using loops :

::

    sage: l = []
    ....: for i in range(10):
    ....:    l.append(i)
    ....: l


-  We can also make it in one line :

::

    sage: [i^2 for i in range(10)]


-  We can create list of different objects. For example, the following code
   generate all the permutations of size 4:

::

   sage: [p for p in Permutations(4)]



-  In fact it is possible to write :

::

    sage: P = Permutations(4)
    sage: P




-  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)`.

::

   sage: [p for p in Permutations(5) if p(4)>p(5) ]

-  It is possible to obtain the size of a list :

::

   sage: l = [p for p in Permutations(5) if p(4)>p(5)] 
   sage: len( l )






**Exercise**: Write a function to list all fixed points of a given permutation.
Then, write another function that lists all permutations without fixed point.

::

    sage: 


-  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.

::

    sage: def nb_without_fp(n):
    ....:     return len(
    ....:         [ 
    ....:             p 
    ....:             for p in Permutations(n)
    ....:             if len(fixed_points(p))==0
    ....:         ] 
    ....:     )
    sage: S = sum( nb_without_fp(n)*x^n for n in range(8) )
    sage: S


-  We can collect the sequence and obtain information about that sequence with
   OEIS.

::

    sage: oeis([ nb_sans_pf(n) for n in range(8) ])

Exercises
---------

-  By using the previous examples, write a program that gives the list of all 
   even integers that are lesser than 30.

::

    sage: 


-  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}`.

::

    sage: 

-  In fact, the function *binomial* exists in Sage. Find that function.

::

    sage: 


The dictionaries
----------------

- 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. 

::

    sage: D = {1:4, 2:6, 3:6, 8:6}
    sage: D
    {1: 4, 2: 6, 3: 6, 8: 6}

::

    sage: D.keys()





**Question**: How do you proceed to :

- determine if a dictionary contains a particular key;

- get a value associated to a key;

- get the number of keys.

::

    sage:

**Exercise** Write a function that takes as parameter a list of integers and 
then returns a dictionary where 

- keys are all the integers present inside the list

- values, associated with the key, are the number of key repetitions inside the list.

::

    sage:

The generators
---------------

-  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 :

::

    sage: generator = iter( Permutations(3) )

-  We can enumerate those permutations by writing :

::

    sage: print( next( generator ) )
    sage: print( next( generator ) )
    sage: print( next( generator ) )
    sage: print( next( generator ) )
    sage: print( next( generator ) )
    sage: print( next( generator ) )

-  An error is raised when iterator reach the end of the iterator function.

::

    sage: print( next( generator ) )

-  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:

::

    sage: generator = iter(Permutations())
    sage: print( next(generator) ) 
    sage: print( next(generator) ) 
    sage: print( next(generator) ) 
    sage: print( next(generator) ) 
    sage: print( next(generator) ) 
    sage: print( next(generator) ) 
    sage: print( next(generator) ) 
    sage: print( next(generator) )

-  It is possible to use iterators inside a loop :

::

    sage: gen = iter( Permutations(3) )
    ....: for p in gen:
    ....:     print( p )

-  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.

::

    sage: def generator( n ):
    ....:      for i in range(n):
    ....:          yield i**2
    sage: gen = generator( 30 )
    ....: print( next(gen) )
    ....: print( next(gen) )
    ....: print( next(gen) )
    ....: print( next(gen) )
    ....: print( next(gen) )
    ....: print( next(gen) )

Exercises : 
-----------

-  Write a generator that enumerates all permutations of size `n` (without using 
   the Sage generator of *Permutations*).

::

    sage:


-  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`.

::

    sage:


-  Find in the Sage documentation a composition generator.

::

    sage:

Euler project
-------------

-  Train yourself by solving problems from the Euler Project Website :

https://projecteuler.net/