Conditional jump, function and loop

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/