Tutorial: Loops and Iterators¶

Author: Florent Hivert <florent.hivert@univ-rouen.fr> and Nicolas M. Thiéry <nthiery at users.sf.net>

List comprehensions¶

list comprehension is a very handy way to build lists is Python. You can use either of the following syntax:

[ <expr> for <name> in <iterable> ]
[ <expr> for <name> in <iterable> if <condition> ]

For example here are lists of square:

{{{id=0|
[ i^2 for i in [1, 3, 7] ]
///
[1, 9, 49]
}}}

{{{id=1|
[ i^2 for i in range(1,10) ]
///
[1, 4, 9, 16, 25, 36, 49, 64, 81]
}}}

{{{id=2|
[ i^2 for i in range(1,10) if i % 2 == 1]
///
[1, 9, 25, 49, 81]
}}}

Exercices:¶

compute the list of the square of the numbers which smaller that 10 and prime:

{{{id=3| # edit here /// }}}
compute the list of perfect square less than 100 (hint: use srange to get a list of sage integers and i.sqrtrem():

{{{id=4| # edit here /// }}}

On can use more than one iterable in a list comprehension:

{{{id=5|
[ (i,j) for i in range(1,6) for j in range(1,i) ]
///
[(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3), (5, 1), (5, 2), (5, 3), (5, 4)]
}}}

Warning

Mind the order of the nested loop in the previous expression.

On the contrary if one want to build a list of list, one has to nest loop as

{{{id=6|
[ [ binomial(n, i) for i in range(n+1) ] for n in range(10) ]
///
[[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1],
[1, 5, 10, 10, 5, 1],
[1, 6, 15, 20, 15, 6, 1],
[1, 7, 21, 35, 35, 21, 7, 1],
[1, 8, 28, 56, 70, 56, 28, 8, 1],
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]]
}}}

Exercices:¶

Compute the list of pairs $(i,j)$ for i smaller than 5 and j smaller than 8 such that i and j are co-prime

{{{id=7| # edit here /// }}}
Compute the same list for $i < j < 10$

{{{id=8| # edit here /// }}}

Iterators¶

To build the previous list Python actually builds an iterator. This is a device which goes along a bunch of objects returning them for each next call. Iterators are build using parentheses:

{{{id=9|
it = (binomial(8, i) for i in range(9))
it.next()
///
1
}}}

{{{id=10|
it.next()
///
8
}}}

{{{id=11|
it.next()
///
28
}}}

{{{id=12|
it.next()
///
56
}}}

You can get the list of the result that are not yet consumed:

{{{id=13|
list(it)
///
[70, 56, 28, 8, 1]
}}}

Iterator can be passed to functions. The two following calls gives the same results but the second one is much more memory efficient as it doesn’t expand any list in memory:

{{{id=14|
sum( binomial(8, i) for i in xrange(9) )
///
256
}}}

{{{id=15|
sum( [ binomial(8, i) for i in range(9) ] )
///
256
}}}

Exercices:¶

Compute the sum of $\binom{10}{i}$ for all even $i$ :

{{{id=16| # edit here /// }}}
Compute the sum the gcd of all co-prime numbers $i, j$ for $i < j < 10$ :

{{{id=17| # edit here /// }}}

Typical uses of iterators¶

Iterators are very handy with the function all, any, exists:

{{{id=18|
all([True, True, True, True])
///
True
}}}

{{{id=19|
all([True, False, True, True])
///
False
}}}

{{{id=20|
any([False, False, False, False])
///
False
}}}

{{{id=21|
any([False, False, True, False])
///
True
}}}

Let’s check that all the prime larger than 2 are odd:

{{{id=22|
all( is_odd(p) for p in range(1,100) if is_prime(p) and p>2 )
///
True
}}}

It is well know that if 2^p -1 is prime then p is prime:

{{{id=23|
def mersenne(p): return 2^p -1
[ is_prime(p) for p in range(20) if is_prime(mersenne(p)) ]
///
[True, True, True, True, True, True, True]
}}}

The converse is not True:

{{{id=24|
all( is_prime(mersenne(p)) for p in range(1000) if is_prime(p) )
///
False
}}}

Using a list would be much slower here:

{{{id=25|
all( [ is_prime(mersenne(p)) for p in range(1000) if is_prime(p)] )
///
False
}}}

You can get the counter example using exists. It take two arguments: an iterator and a function with tests the property you want to be True:

{{{id=26|
exists( (p for p in range(1000) if is_prime(p)), lambda p: not is_prime(mersenne(p)) )
///
(True, 11)
}}}

An alternative way to do that is:

{{{id=27|
contre_exemples = (p for p in range(1000) if is_prime(p) and not is_prime(mersenne(p)))
contre_exemples.next()
///
11
}}}

Exercices:¶

Build the list $\{i^3 \mid -10<i<10\}$ . Can you find two of those cubes $u$ and $v$ such that $u + v = 218$

{{{id=28| # edit here /// }}}

itertools¶

Itertools is a module which defines several handy tools for playing with iterators:

{{{id=29|
l = [3, 234, 12, 53, 23]
[(i, l[i]) for i in range(len(l))]
///
[(0, 3), (1, 234), (2, 12), (3, 53), (4, 23)]
}}}

The same results can be obtained using enumerate:

{{{id=30|
list(enumerate(l))
///
[(0, 3), (1, 234), (2, 12), (3, 53), (4, 23)]
}}}

Here is the analogue of list slicing:

{{{id=31|
list(Permutations(3))
///
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
}}}

{{{id=32|
list(Permutations(3))[1:4]
///
[[1, 3, 2], [2, 1, 3], [2, 3, 1]]
}}}

{{{id=33|
import itertools
list(itertools.islice(Permutations(3), 1, 4))
///
[[1, 3, 2], [2, 1, 3], [2, 3, 1]]
}}}

The functions map and filter also have an analogue:

{{{id=34|
list(itertools.imap(lambda z: z.cycle_type(), Permutations(3)))
///
[[1, 1, 1], [2, 1], [2, 1], [3], [3], [2, 1]]
}}}

{{{id=35|
list(itertools.ifilter(lambda z: z.has_pattern([1,2]), Permutations(3)))
///
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]]
}}}

Exercices:¶

Define an iterator for the $i$ -th prime for $5<i<10$ :

{{{id=36| # edit here /// }}}

Defining new iterators¶

One can very easily write new iterators using the keyword yield. The following one does not do anything interesting but demonstrating the use of yield:

{{{id=37|
def f(n):
     for i in range(n):
         yield i
[ u for u in f(5) ]
///
[0, 1, 2, 3, 4]
}}}

Iterators can be recursive:

{{{id=38|
def words(alphabet,l):
      if l == 0:
          yield []
      else:
          for word in words(alphabet, l-1):
              for a in alphabet:
                  yield word + [a]
///
}}}

{{{id=39|
[ w for w in words(['a','b','c'], 3) ]
///
[['a', 'a', 'a'], ['a', 'a', 'b'], ['a', 'a', 'c'], ['a', 'b', 'a'], ['a', 'b', 'b'], ['a', 'b', 'c'], ['a', 'c', 'a'], ['a', 'c', 'b'], ['a', 'c', 'c'], ['b', 'a', 'a'], ['b', 'a', 'b'], ['b', 'a', 'c'], ['b', 'b', 'a'], ['b', 'b', 'b'], ['b', 'b', 'c'], ['b', 'c', 'a'], ['b', 'c', 'b'], ['b', 'c', 'c'], ['c', 'a', 'a'], ['c', 'a', 'b'], ['c', 'a', 'c'], ['c', 'b', 'a'], ['c', 'b', 'b'], ['c', 'b', 'c'], ['c', 'c', 'a'], ['c', 'c', 'b'], ['c', 'c', 'c']]
}}}

{{{id=40|
sum(1 for w in words(['a','b','c'], 3))
///
27
}}}

Here is another one:

{{{id=41|
def dyck_words(l):
       if l==0:
           yield ''
       else:
           for k in range(l):
               for w1 in dyck_words(k):
                   for w2 in dyck_words(l-k-1):
                       yield '('+w1+')'+w2
///
}}}

{{{id=42|
list(dyck_words(4))
///
['()()()()',
'()()(())',
'()(())()',
'()(()())',
'()((()))',
'(())()()',
'(())(())',
'(()())()',
'((()))()',
'(()()())',
'(()(()))',
'((())())',
'((()()))',
'(((())))']
}}}

{{{id=43|
sum(1 for w in dyck_words(5))
///
42
}}}

Exercices:¶

Write an iterator with two parameter $n$ , $l$ iterating through the set of nondecreasing list of integer of length $l$ and smaller than $n$ :

{{{id=44| # edit here /// }}}

Standard Iterables¶

Finally lots of standard sage objets are iterable. When properly asked they turn into an iterator:

{{{id=45|
sum( x^len(s) for s in Subsets(8) )
///
x^8 + 8*x^7 + 28*x^6 + 56*x^5 + 70*x^4 + 56*x^3 + 28*x^2 + 8*x + 1
}}}

{{{id=46|
sum( x^p.length() for p in Permutations(3) )
///
x^3 + 2*x^2 + 2*x + 1
}}}

{{{id=47|
factor(sum( x^p.length() for p in Permutations(3) ))
///
(x + 1)*(x^2 + x + 1)
}}}

{{{id=48|
P = Permutations(5)
all( p in P for p in P )
///
True
}}}

{{{id=49|
for p in GL(2, 2): print p; print
///
[0 1]
[1 0]

[0 1]
[1 1]

[1 1]
[0 1]

[1 0]
[0 1]

[1 0]
[1 1]

[1 1]
[1 0]

}}}

{{{id=50|
for p in Partitions(3): print p
///
[3]
[2, 1]
[1, 1, 1]
}}}

Beware of infinite loops:

{{{id=51|
for p in Partitions(): print p
///
}}}

{{{id=52|
for p in Primes(): print p
///
}}}

Infinite loops can nevertheless be useful:

{{{id=53|
exists( Primes(), lambda p: not is_prime(mersenne(p)) )
///
(True, 11)
}}}

{{{id=54|
contre_exemples = (p for p in Primes() if not is_prime(mersenne(p)))
contre_exemples.next()
///
11
}}}

Tutorial: Loops and Iterators¶

List comprehensions¶

Exercices:¶

Exercices:¶

Iterators¶

Exercices:¶

Typical uses of iterators¶

Exercices:¶

itertools¶

Exercices:¶

Defining new iterators¶

Exercices:¶

Standard Iterables¶

Table Of Contents

This Page

Navigation

Tutorial: Loops and Iterators¶

List comprehensions¶

Exercices:¶

Exercices:¶

Iterators¶

Exercices:¶

Typical uses of iterators¶

Exercices:¶

itertools¶

Exercices:¶

Defining new iterators¶

Exercices:¶

Standard Iterables¶

Table Of Contents

This Page

Quick search

Navigation