tutorial-iterators
system:sage


Tutorial: Loops and Iterators -- Thematic Tutorials v4.6.2
system:sage

<div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="genindex.html" title="General Index" accesskey="I">index</a></li>
  
    
      <a href="../index.html"><img src="_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
    
  
  
        <li><a href="index.html">Thematic Tutorials v4.6.2</a> &raquo;</li>
 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body">
            
  <div class="section" id="tutorial-loops-and-iterators">
<span id="tutorial-iterators"></span><h1>Tutorial: Loops and Iterators<a class="headerlink" href="#tutorial-loops-and-iterators" title="Permalink to this headline">¶</a></h1>
<p><em>Author: Florent Hivert &lt;<a class="reference external" href="mailto:florent.hivert%40univ-rouen.fr">florent<span>&#46;</span>hivert<span>&#64;</span>univ-rouen<span>&#46;</span>fr</a>&gt; and
Nicolas M. Thiéry &lt;nthiery at users.sf.net&gt;</em></p>
<div class="section" id="list-comprehensions">
<h2>List comprehensions<a class="headerlink" href="#list-comprehensions" title="Permalink to this headline">¶</a></h2>
<p><em>list comprehension</em> is a very handy way to build lists is Python. You can use
either of the following syntax:</p>
<div class="highlight-python"><pre>[ &lt;expr&gt; for &lt;name&gt; in &lt;iterable&gt; ]
[ &lt;expr&gt; for &lt;name&gt; in &lt;iterable&gt; if &lt;condition&gt; ]</pre>
</div>
<p>For example here are lists of square:</p>
<div class="highlight-python">

{{{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]
}}}

</div>
<div class="section" id="exercices">
<h3>Exercices:<a class="headerlink" href="#exercices" title="Permalink to this headline">¶</a></h3>
<ol class="arabic">
<li><p class="first">compute the list of the square of the numbers which smaller that 10 and
prime:</p>
<div class="highlight-python">

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

</div>
</li>
<li><p class="first">compute the list of perfect square less than 100 (hint: use <tt class="docutils literal"><span class="pre">srange</span></tt> to
get a list of sage integers and <tt class="docutils literal"><span class="pre">i.sqrtrem()</span></tt>:</p>
<div class="highlight-python">

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

</div>
</li>
</ol>
<p>On can use more than one iterable in a list comprehension:</p>
<div class="highlight-python">

{{{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)]
}}}

</div>
<div class="admonition warning">
<p class="first admonition-title">Warning</p>
<p class="last">Mind the order of the nested loop in the previous expression.</p>
</div>
<p>On the contrary if one want to build a list of list, one has to nest loop as</p>
<div class="highlight-python">

{{{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]]
}}}

</div>
</div>
<div class="section" id="id1">
<h3>Exercices:<a class="headerlink" href="#id1" title="Permalink to this headline">¶</a></h3>
<ol class="arabic" start="3">
<li><p class="first">Compute the list of pairs <img class="math" src="_images/math/887919dfbc86eebc29e0373f98f97dbf23a0ae23.png" alt="(i,j)"> for i smaller than 5 and j smaller than
8 such that i and j are co-prime</p>
<blockquote>
<div class="highlight-python">

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

</div>
</blockquote>
</li>
<li><p class="first">Compute the same list for <img class="math" src="_images/math/1d5bacee6057acab921107c2063436c39b9cdfcc.png" alt="i < j < 10"></p>
<blockquote>
<div class="highlight-python">

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

</div>
</blockquote>
</li>
</ol>
</div>
</div>
<div class="section" id="iterators">
<h2>Iterators<a class="headerlink" href="#iterators" title="Permalink to this headline">¶</a></h2>
<p>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 <tt class="docutils literal"><span class="pre">next</span></tt>
call. Iterators are build using parentheses:</p>
<div class="highlight-python">

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

</div>
<div class="highlight-python">

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

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

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

</div>
<p>You can get the list of the result that are not yet <em>consumed</em>:</p>
<div class="highlight-python">

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

</div>
<p>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&#8217;t expand any list in memory:</p>
<div class="highlight-python">

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

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

</div>
<div class="section" id="id2">
<h3>Exercices:<a class="headerlink" href="#id2" title="Permalink to this headline">¶</a></h3>
<ol class="arabic" start="5">
<li><p class="first">Compute the sum of <img class="math" src="_images/math/9d65dfc3f0eaf1d44db535249a3c34074ae23985.png" alt="\binom{10}{i}"> for all even <img class="math" src="_images/math/34857b3ba74ce5cd8607f3ebd23e9015908ada71.png" alt="i">:</p>
<div class="highlight-python">

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

</div>
</li>
<li><p class="first">Compute the sum the gcd of all co-prime numbers <img class="math" src="_images/math/3b1be2340079411dac99664d3857725babacc96e.png" alt="i, j"> for <img class="math" src="_images/math/1d5bacee6057acab921107c2063436c39b9cdfcc.png" alt="i < j < 10">:</p>
<div class="highlight-python">

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

</div>
</li>
</ol>
</div>
</div>
<div class="section" id="typical-uses-of-iterators">
<h2>Typical uses of iterators<a class="headerlink" href="#typical-uses-of-iterators" title="Permalink to this headline">¶</a></h2>
<p>Iterators are very handy with the function <tt class="docutils literal"><span class="pre">all</span></tt>, <tt class="docutils literal"><span class="pre">any</span></tt>, <tt class="docutils literal"><span class="pre">exists</span></tt>:</p>
<div class="highlight-python">

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

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

</div>
<div class="highlight-python">

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

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

</div>
<p>Let&#8217;s check that all the prime larger than 2 are odd:</p>
<div class="highlight-python">

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

</div>
<p>It is well know that if <tt class="docutils literal"><span class="pre">2^p</span> <span class="pre">-1</span></tt> is prime then <tt class="docutils literal"><span class="pre">p</span></tt> is prime:</p>
<div class="highlight-python">

{{{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]
}}}

</div>
<p>The converse is not True:</p>
<div class="highlight-python">

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

</div>
<p>Using a list would be much slower here:</p>
<div class="highlight-python">

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

</div>
<p>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:</p>
<div class="highlight-python">

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

</div>
<p>An alternative way to do that is:</p>
<div class="highlight-python">

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

</div>
<div class="section" id="id3">
<h3>Exercices:<a class="headerlink" href="#id3" title="Permalink to this headline">¶</a></h3>
<ol class="arabic">
<li><p class="first">Build the list <img class="math" src="_images/math/a66113fe404de63b719cf897d7029ffe39125283.png" alt="\{i^3 \mid -10<i<10\}">. Can you find two of those cubes
<img class="math" src="_images/math/9ad99798ec4c38e165cf517cb9e02b1c9e824103.png" alt="u"> and <img class="math" src="_images/math/a9f23bf124b6b2b2a993eb313c72e678664ac74a.png" alt="v"> such that <img class="math" src="_images/math/05dfb91c7ff340a65275ff769854f0ff88ddcafa.png" alt="u + v = 218"></p>
<div class="highlight-python">

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

</div>
</li>
</ol>
</div>
</div>
<div class="section" id="itertools">
<h2>itertools<a class="headerlink" href="#itertools" title="Permalink to this headline">¶</a></h2>
<p>Itertools is a module which defines several handy tools for playing with
iterators:</p>
<div class="highlight-python">

{{{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)]
}}}

</div>
<p>The same results can be obtained using <tt class="docutils literal"><span class="pre">enumerate</span></tt>:</p>
<div class="highlight-python">

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

</div>
<p>Here is the analogue of list slicing:</p>
<div class="highlight-python">

{{{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]]
}}}

</div>
<p>The functions <tt class="docutils literal"><span class="pre">map</span></tt> and <tt class="docutils literal"><span class="pre">filter</span></tt> also have an analogue:</p>
<div class="highlight-python">

{{{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]]
}}}

</div>
<div class="section" id="id4">
<h3>Exercices:<a class="headerlink" href="#id4" title="Permalink to this headline">¶</a></h3>
<ol class="arabic">
<li><p class="first">Define an iterator for the <img class="math" src="_images/math/34857b3ba74ce5cd8607f3ebd23e9015908ada71.png" alt="i">-th prime for <img class="math" src="_images/math/cc6d64a9e7bbabf7b3fad137edff3d5bff362d1d.png" alt="5<i<10">:</p>
<div class="highlight-python">

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

</div>
</li>
</ol>
</div>
</div>
<div class="section" id="defining-new-iterators">
<h2>Defining new iterators<a class="headerlink" href="#defining-new-iterators" title="Permalink to this headline">¶</a></h2>
<p>One can very easily write new iterators using the keyword <tt class="docutils literal"><span class="pre">yield</span></tt>. The
following one does not do anything interesting but demonstrating the use of
<tt class="docutils literal"><span class="pre">yield</span></tt>:</p>
<div class="highlight-python">

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

</div>
<p>Iterators can be recursive:</p>
<div class="highlight-python">

{{{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([&#39;a&#39;,&#39;b&#39;,&#39;c&#39;], 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([&#39;a&#39;,&#39;b&#39;,&#39;c&#39;], 3))
///
27
}}}

</div>
<p>Here is another one:</p>
<div class="highlight-python">

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

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

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

</div>
<div class="section" id="id5">
<h3>Exercices:<a class="headerlink" href="#id5" title="Permalink to this headline">¶</a></h3>
<ol class="arabic">
<li><p class="first">Write an iterator with two parameter <img class="math" src="_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n">, <img class="math" src="_images/math/9b25f8e64b484493fda944d25cad453423041fe6.png" alt="l"> iterating through the set of
nondecreasing list of integer of length <img class="math" src="_images/math/9b25f8e64b484493fda944d25cad453423041fe6.png" alt="l"> and smaller than <img class="math" src="_images/math/174fadd07fd54c9afe288e96558c92e0c1da733a.png" alt="n">:</p>
<div class="highlight-python">

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

</div>
</li>
</ol>
</div>
</div>
<div class="section" id="standard-iterables">
<h2>Standard Iterables<a class="headerlink" href="#standard-iterables" title="Permalink to this headline">¶</a></h2>
<p>Finally lots of standard sage objets are iterable. When properly asked they
turn into an iterator:</p>
<div class="highlight-python">

{{{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]
<BLANKLINE>
[0 1]
[1 1]
<BLANKLINE>
[1 1]
[0 1]
<BLANKLINE>
[1 0]
[0 1]
<BLANKLINE>
[1 0]
[1 1]
<BLANKLINE>
[1 1]
[1 0]
<BLANKLINE>
}}}

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

</div>
<p>Beware of infinite loops:</p>
<div class="highlight-python">

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

</div>
<div class="highlight-python">

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

</div>
<p>Infinite loops can nevertheless be useful:</p>
<div class="highlight-python">

{{{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
}}}

</div>
</div>
</div>


          </div>
        </div>
      </div>
      <div class="sphinxsidebar">
        <div class="sphinxsidebarwrapper">
            <h3><a href="index.html">Table Of Contents</a></h3>
            <ul>
<li><a class="reference internal" href="#">Tutorial: Loops and Iterators</a><ul>
<li><a class="reference internal" href="#list-comprehensions">List comprehensions</a><ul>
<li><a class="reference internal" href="#exercices">Exercices:</a></li>
<li><a class="reference internal" href="#id1">Exercices:</a></li>
</ul>
</li>
<li><a class="reference internal" href="#iterators">Iterators</a><ul>
<li><a class="reference internal" href="#id2">Exercices:</a></li>
</ul>
</li>
<li><a class="reference internal" href="#typical-uses-of-iterators">Typical uses of iterators</a><ul>
<li><a class="reference internal" href="#id3">Exercices:</a></li>
</ul>
</li>
<li><a class="reference internal" href="#itertools">itertools</a><ul>
<li><a class="reference internal" href="#id4">Exercices:</a></li>
</ul>
</li>
<li><a class="reference internal" href="#defining-new-iterators">Defining new iterators</a><ul>
<li><a class="reference internal" href="#id5">Exercices:</a></li>
</ul>
</li>
<li><a class="reference internal" href="#standard-iterables">Standard Iterables</a></li>
</ul>
</li>
</ul>

            <h3>This Page</h3>
            <ul class="this-page-menu">
              <li><a href="_sources/tutorial-iterators.txt" rel="nofollow">Show Source</a></li>
            </ul>
          <div id="searchbox" style="display: none">
            <h3>Quick search</h3>
              <p class="searchtip" style="font-size: 90%">
              Enter search terms or a module, class or function name.
              </p>
          </div>
          <script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="genindex.html" title="General Index">index</a></li>
  
    
      <a href="../index.html"><img src="_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
    
  
  
        <li><a href="index.html">Thematic Tutorials v4.6.2</a> &raquo;</li>
 
      </ul>
    </div>
    
    <div class="footer">
        &copy; Copyright 2005--2010, The Sage Development Team.
      Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.0.4.
    </div>
    <script type="text/javascript">
/*global jQuery, window */
/* Sphinx sidebar toggle.  Putting this code at the end of the body
 * enables the toggle for the live, static, and offline docs.  Note:
 * sage.misc.html.math_parse() eats jQuery's dollar-sign shortcut. */
var jq = jQuery;  
jq(document).ready(function () {
    var bar, bod, bg, fg, key, tog, wid_old, wid_new, resize, get_state, set_state;
    bod = jq('div.bodywrapper');
    bar = jq('div.sphinxsidebar');
    tog = jq('<div class="sphinxsidebartoggle"></div>');
    
    /* Delayed resize helper.  Not perfect but good enough. */
    resize = function () {
        setTimeout(function () {
            tog.height(bod.height());
        }, 100);
    };
    jq(window).resize(function () {
        resize();
    });
    
    /* Setup and add the toggle. See Sphinx v0.5.1 default.css. */
    fg = jq('div.sphinxsidebar p a').css('color') || 'rgb(152, 219, 204)';
    bg = jq('div.document').css('background-color') || 'rgb(28, 78, 99)';
    wid_old = '230px';
    wid_new = '5px';
    tog.css('background-color', bg)
        .css('border-width', '0px')
        .css('border-right', wid_new + ' ridge ' + bg)
        .css('cursor', 'pointer')
        .css('position', 'absolute')
        .css('left', '-' + wid_new)
        .css('top', '0px')
        .css('width', wid_new);
    bod.css('position', 'relative');
    bod.prepend(tog);
    resize();
    
    /* Cookie helpers. */
    key = 'sphinxsidebar=';
    set_state = function (s) {
        var date = new Date();
        /* Expiry in 7 days. */
        date.setTime(date.getTime() + (7 * 24 * 3600 * 1000));
        document.cookie = key + encodeURIComponent(s) + '; expires=' +
            date.toUTCString() + '; path=/';
    };
    get_state = function () {
        var i, c, crumbs = document.cookie.split(';');
        for (i = 0; i < crumbs.length; i += 1) {
            c = crumbs[i].replace(/^\s+/, '');
            if (c.indexOf(key) === 0) {
                return decodeURIComponent(c.substring(key.length, c.length));
            }
        }
        return null;
    };
    
    /* Event handlers. */
    tog.mouseover(function (ev) {
        tog.css('border-right-color', fg);
    }).mouseout(function (ev) {
        tog.css('border-right-color', bg);
    }).click(function (ev) {
        if (bod.hasClass('wide')) {
            bod.removeClass('wide');
            bod.css('margin-left', wid_old);
            bar.css('width', wid_old);
            bar.show();
            set_state('visible');
        } else {
            set_state('hidden');
            bar.hide();
            bar.css('width', '0px');
            bod.css('margin-left', wid_new);
            bod.addClass('wide');
        }
        resize();
    });
    
    /* Hide the normally visible sidebar? */
    if (get_state() === 'hidden') {
        tog.trigger('click');
    } else {
        set_state('visible');
    }
});
    </script>