Tutorial 4 - Introduction to Programming in Python and Sage.ipynb

Kernel: SageMath (stable)

%html

Tutorial: Programming in Python and Sage

Authors: Florent Hivert <[email protected]>, Franco Saliola <[email protected]>, et al.

This tutorial explores the different data structures in Python (and Sage) as well as control structures and Python functions.

The exercises below are extracted from the Sage Thematic Tutorial on Programming in Python and Sage.

The thematic tutorial also contains detailed information on the data structures, control structures and functions.

%html

Lists

Creating Lists I: [Square brackets]

Example:

L = [3, Permutation([5,1,4,2,3]), 17, 17, 3, 51]
L

%html

Exercise: Create the list [63, 12, -10, "a", 12], assign it to the variable L, and print the list.

%html

Exercise: Create the empty list (you will often need to do this).

%html

Creating Lists II: range

The range function provides an easy way to construct a list of integers. Here is the documentation of the range function:

range?

%html

Exercise: Use range to construct the list $[1,2,\ldots,50]$.

%html

Exercise: Use range to construct the list of even numbers between 1 and 100 (including 100).

%html
<p><strong>Exercise:</strong> The <em>step</em> argument for the <em>range</em> command can be negative. Use
<em>range</em> to construct the list $[10, 7, 4, 1, -2]$.</p>

%html
<h3>Creating Lists III: list comprehensions</h3>
<p><em>List comprehensions</em> provide a concise way to create lists from other lists
(or other data types).</p>
<p><strong>Example</strong> We already know how to create the list $[1, 2, \dots, 16]$:</p>

range(1,17)

%html

Using a list comprehension, we can now create the list $[1^2, 2^2, 3^2, \dots, 16^2]$ as follows:

[i^2 for i in range(1,17)]

sum([i^2 for i in range(1,17)])

%html

Exercise: [Project Euler, Problem 6]

The sum of the squares of the first ten natural numbers is $$(1^2 + 2^2 + \cdots + 10^2) = 385.$$ The square of the sum of the first ten natural numbers is $$(1 + 2 + \cdots + 10)^2 = 55^2 = 3025.$$ Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is $$3025 - 385 = 2640.$$

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

%html

Filtering lists with a list comprehension

A list can be filtered using a list comprehension.

Example: To create a list of the squares of the prime numbers between 1 and 100, we use a list comprehension as follows.

[p^2 for p in [1,2,..,100] if is_prime(p)]

%html

Exercise: Use a list comprehension to list all the natural numbers below 20 that are multiples of 3 or 5. Hint:

• To get the remainder of 7 divided by 3 use 7%3.
• To test for equality use two equal signs (==); for example, 3 == 7.

%html

Project Euler, Problem 1: Find the sum of all the multiples of 3 or 5 below 1000.

%html

Fizz Buzz

Écrire une fonction qui affiche les nombres de 1 à 100 de sorte que la fonction affiche "Fizz" au lieu d'afficher les multiples de 3 et "Buzz" au lieu des multiples de 5. Pour les multiples de 3 et 5, afficher "FizzBuzz".

Write a program that prints the numbers from 1 to 100. But for multiples of three print "Fizz" instead of the number and for the multiples of five print "Buzz". For numbers which are multiples of both three and five print "FizzBuzz".

%html

Nested list comprehensions

List comprehensions can be nested!

Examples:

[(x,y) for x in range(5) for y in range(3)]

[[i^j for j in range(1,4)] for i in range(6)]

matrix([[i^j for j in range(1,4)] for i in range(6)])

%html

Exercise:

A Pythagorean triple is a triple $(x,y,z)$ of positive integers satisfying $x^2+y^2=z^2$. The Pythagorean triples whose components are at most $10$ are:

$$[(3, 4, 5), (4, 3, 5), (6, 8, 10), (8, 6, 10)]$$

Using a filtered list comprehension, construct the list of Pythagorean triples whose components are at most $50$.

%html

Project Euler, Problem 9: There exists exactly one Pythagorean triplet for which $a + b + c = 1000$. Find the product $abc$.

%html

Accessing individual elements of lists

To access an element of the list, use the syntax L[i], where $i$ is the index of the item.

Exercise:

1. Construct the list L = [1,2,3,4,3,5,6]. What is L[3]?

%html

What is L[1]?

%html

What is the index of the first element of L?

%html

What is L[-1]? What is L[-2]?

%html

What is L.index(2)? What is L.index(3)?

%html

Modifying lists: changing an element in a list

To change the item in position i of a list L:

L = ["a", 4, 1, 8]
print L

%html

L[2] = 0

print L

%html

Modifying lists: append and extend

To append an object to a list:

L = ["a", 4, 1, 8]
print L

%html

L.append(17)
print L

%html

To extend a list by another list:

L1 = [1,2,3]
L2 = [7,8,9,0]
print L1

print L2

%html

L1.extend(L2)
print L1

%html

Modifying lists: reverse, sort, ...

L = [4,2,5,1,3]
L

%html

L.reverse()
L

%html

L.sort()
L

L = [3,1,6,4]
sorted(L)

%html

L

%html

Concatenating Lists

To concatenate two lists, add them with the operator +. This is not a commutative operation....

L1 = [1,2,3]
L2 = [7,8,9,0]
L1 + L2

%html

Slicing Lists

You can slice a list using the syntax L[start : stop : step]. This will return a sublist of L.

Exercise: Below are some examples of slicing lists. Try to guess what the output will be before evaluating the cell.

L = range(20)
L

%html

L[3:15]

%html

L[3:15:2]

%html

%html

L[:4]

%html

L[:]

%html

L[::-1]

%html

Advanced exercise: The following function combines a loop with the some of the list operations above. What does the function do?

def f(number_of_iterations):
       L = [1]
       for n in range(2, number_of_iterations):
           L = [sum(L[:i]) for i in range(n-1, -1, -1)]
       return numerical_approx(2*L[0]*len(L)/sum(L), digits=50)

%html

%html

Tuples

A tuple is an immutable list. That is, it cannot be changed once it is created. To create a tuple, use parentheses instead of brackets:

t = (3, 5, [3,1], (17,[2,3],17), 4)
t

%html

We can create a tuple from a list, or vice-versa.

tuple(range(5))

%html

list(t)

%html

Tuples behave like lists in many respects:

Operation	Syntax for lists	Syntax for tuples
Accessing a letter	list[3]	tuple[3]
Concatenation	list1 + list2	tuple1 + tuple2
Slicing	list[3:17:2]	tuple[3:17:2]
A reversed copy	list[::-1]	tuple[::-1]
Length	len(list)	len(tuple)

Trying to modify a tuple will fail.

t = (5, 'a', 6/5)
t

t[1] = 'b'

%html

Dictionaries

A dictionary is another built-in data type. Unlike lists, which are indexed by a range of numbers, dictionaries are indexed by keys, which can be any immutable object. Strings and numbers can always be keys (because they are immutable). Dictionaries are sometimes called "associative arrays" in other programming languages.

There are several ways to define dictionaries. One method is to use braces, {}, with comma-separated entries given in the form key:value:

d = {3:17, 'key':[4,1,5,2,3], (3,1,2):'goo', 3/2 : 17}
d

%html

A second solution for creating a dictionary is to use the function dict which admits a list of 2-tuples (key, value) (actually any iterable):

dd = dict((i,i^2) for i in xrange(10))
dd

%html

Dictionaries behave as lists and tuples for several important operations.

Operation	Syntax for lists	Syntax for dictionaries
Accessing elements	list[3]	D["key"]
Length	len(list)	len(D)
Modifying	L[3] = 17	D["key"] = 17
Deleting items	del L[3]	del D["key"]

d[10]='a'
d

%html

A dictionary can have the same value multiple times, but each key must only appear once and must be "immutable".

d = {3: 14, 4: 14}
d

d = {3: 13, 3: 14}
d

d = {[1,2,3] : 12}

%html

Another way to add items to a dictionary is with the update() method which updates the dictionnary from another dictionnary:

d = {}
d

%html

d.update( {10 : 'newvalue', 20: 'newervalue', 3: 14, 'a':[1,2,3]} )
d

%html

We can iterate through the keys, or values, or both, of a dictionary.

d = {10 : 'newvalue', 20: 'newervalue', 3: 14, 'a':[1,2,3]}

%html

[key for key in d]

%html

[key for key in d.iterkeys()]

%html

[value for value in d.itervalues()]

%html

[(key, value) for key, value in d.iteritems()]

%html

Exercise: Consider the following directed graph.

Create a dictionary whose keys are the vertices of the above directed graph, and whose values are the lists of the vertices that it points to. For instance, the vertex 1 points to the vertices 2 and 3, so the dictionary will look like:

d = {  ..., 1:[2,3], ... } 

%html

Then try

g = DiGraph(d)
g.plot()

%html

Using Sage types: The srange command

Example: Construct a $3 \times 3$ matrix whose $(i,j)$ entry is the rational number $\frac{i}{j}$. The integer generated by range are python int. As a consequence, dividing them does euclidian division.

matrix([[ i/j for j in range(1,4)] for i in range(1,4)])

%html

Whereas dividing a Sage Integer by a Sage Integer gives a rational number:

matrix([[ i/j for j in srange(1,4)] for i in srange(1,4)])

%html

Modifying lists has consequences!

Try to predict the results of the following commands.

a = [1, 2, 3]
L = [a, a, a]
L

%html

a.append(4)
L

%html

Now try these:

a = [1, 2, 3]
L = [a, a, a]
L

%html

a = [1, 2, 3, 4]
L

%html

L[0].append(4)
L

%html

You can use the command deepcopy to avoid these issues.

a = [1,2,3]
L = [deepcopy(a), deepcopy(a)]
L

%html

a.append(4)
L

%html

The same issues occur with dictionaries.

d = {1:'a', 2:'b', 3:'c'}
dd = d
d.update( { 4:'d' } )
dd

%html

Loops and Functions

For more verbose explanation of what's going on here, a good place to look is at the following section of the Python tutorial: http://docs.python.org/tutorial/controlflow.html

While Loops

While loops tend not to be used nearly as much as for loops in Python code.

i = 0
while i < 10:
       print i
       i += 1

i = 0
while i < 10:
       if i % 2 == 1:
           i += 1
           continue
       print i
       i += 1

%html

Note that the truth value expression in the while loop is evaluated using bool().

bool(True)

bool('a')

bool(1)

bool(0)

%html

i = 4
while i:
       print i
       i -= 1

%html

For Loops

Here is a basic for loop iterating over all of the elements in the list l:

l = ['a', 'b', 'c']
for letter in l:
       print letter

%html

The range function is very useful when you want to generate arithmetic progressions to loop over. Note that the end point is never included:

range?

range(4)

range(1, 5)

range(1, 11, 2)

range(10, 0, -1)

for i in range(4):
       print i, i*i

%html

You can use the continue keyword to immediately go to the next item in the loop:

for i in range(10):
       if i % 2 == 0:
           continue
       print i

%html

If you want to break out of the loop, use the break keyword:

for i in range(10):
       if i % 2 == 0:
           continue
       if i == 7:
           break
       print i

%html

If you need to keep track of both the position in the list and its value, one (not so elegant) way would be to do the following:

l = ['a', 'b', 'c']
for i in range(len(l)):
       print i, l[i]

%html

It's cleaner to use enumerate which provides the index as well as the value:

l = ['a', 'b', 'c']
for i, letter in enumerate(l):
       print i, letter

%html

You could make something similary to the enumerate function by using zip to zip two lists together:

l = ['a', 'b', 'c']
for i, letter in zip(range(len(l)), l):
       print i, letter

%html

For loops work using Python's iterator protocol.  This allows all sorts of different objects to be looped over.  For example,

GF(5)

for i in GF(5):
       print i, i*i

%html

Exercise

For each of the following sets, compute the list of its elements and their sum. Use two different ways, if possible: with a loop; and using a list comprehension.

• The first $n$ terms of the harmonic series:

  $$\sum_{ i=1}^n \frac{1}{i}$$

%html

The odd integers between $1$ and $n$.

%html

The first $n$ odd integers.

%html

The integers between $1$ and $n$ that are neither divisible by $2$ nor by $3$ nor by $5$.

%html

The first $n$ integers between $1$ and $n$ that are neither divisible by $2$ nor by $3$ nor by $5$.

%html

Functions

Functions are defined using the def statement, and values are returned using the return keyword:

def f(x):
    return x*x

f(2)

%html

%html Here is a function that returns the $n$-th Fibonacci number.

def fib(n):
       if n <= 1:
           return 1
       else:
           return fib(n-1) + fib(n-2)

%html And here is a list of the first twenty Fibonacci numbers.

[fib(n) for n in range(20)]

%html

Default arguments for functions

You can give default values for arguments in functions:

def add_n(x, n=1):
       return x + n

%html

add_n(4)

%html

add_n(4, n=100)

%html

add_n(4, 1000)

%html

You can return multiple things from a function:

def g(x):
       return x, x*x

g(2)

a,b = g(100)

a

b

%html

You can also take variable number of arguments and keyword arguments in a function:

def h(*args, **kwds):
       print type(args), args
       print type(kwds), kwds

%html

h(1,2,3,n=4)

%html

Let's use the yield instruction to make a generator for the Fibonacci numbers less than $n$:

def fib_gen(n):
       if n < 1:
           return
       a = b = 1
       yield b
       while b < n:
           yield b
           a, b = b, b+a

for i in fib_gen(50):
       print i

%html

Exercices

1. Write a function is_even returning True if n is even and False otherwise.
2. Write a function every_other which takes a list l and returns a list containing every other element of l
3. Write a function computing the $n$-th Fibonacci number. Try to improve performance.