python-clinic / Doc / library / itertools.rst

:mod:`itertools` --- Functions creating iterators for efficient looping

This module implements a number of :term:`iterator` building blocks inspired by constructs from APL, Haskell, and SML. Each has been recast in a form suitable for Python.

The module standardizes a core set of fast, memory efficient tools that are useful by themselves or in combination. Together, they form an "iterator algebra" making it possible to construct specialized tools succinctly and efficiently in pure Python.

For instance, SML provides a tabulation tool: tabulate(f) which produces a sequence f(0), f(1), .... The same effect can be achieved in Python by combining :func:`map` and :func:`count` to form map(f, count()).

These tools and their built-in counterparts also work well with the high-speed functions in the :mod:`operator` module. For example, the multiplication operator can be mapped across two vectors to form an efficient dot-product: sum(map(operator.mul, vector1, vector2)).

Infinite Iterators:

Iterator Arguments Results Example
:func:`count` start, [step] start, start+step, start+2*step, ... count(10) --> 10 11 12 13 14 ...
:func:`cycle` p p0, p1, ... plast, p0, p1, ... cycle('ABCD') --> A B C D A B C D ...
:func:`repeat` elem [,n] elem, elem, elem, ... endlessly or up to n times repeat(10, 3) --> 10 10 10

Iterators terminating on the shortest input sequence:

Iterator Arguments Results Example
:func:`accumulate` p [,func] p0, p0+p1, p0+p1+p2, ... accumulate([1,2,3,4,5]) --> 1 3 6 10 15
:func:`chain` p, q, ... p0, p1, ... plast, q0, q1, ... chain('ABC', 'DEF') --> A B C D E F
:func:`compress` data, selectors (d[0] if s[0]), (d[1] if s[1]), ... compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F
:func:`dropwhile` pred, seq seq[n], seq[n+1], starting when pred fails dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1
:func:`filterfalse` pred, seq elements of seq where pred(elem) is False filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8
:func:`groupby` iterable[, keyfunc] sub-iterators grouped by value of keyfunc(v)  
:func:`islice` seq, [start,] stop [, step] elements from seq[start:stop:step] islice('ABCDEFG', 2, None) --> C D E F G
:func:`starmap` func, seq func(*seq[0]), func(*seq[1]), ... starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000
:func:`takewhile` pred, seq seq[0], seq[1], until pred fails takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4
:func:`tee` it, n it1, it2 , ... itn splits one iterator into n  
:func:`zip_longest` p, q, ... (p[0], q[0]), (p[1], q[1]), ... zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-

Combinatoric generators:

Iterator Arguments Results
:func:`product` p, q, ... [repeat=1] cartesian product, equivalent to a nested for-loop
:func:`permutations` p[, r] r-length tuples, all possible orderings, no repeated elements
:func:`combinations` p, r r-length tuples, in sorted order, no repeated elements
:func:`combinations_with_replacement` p, r r-length tuples, in sorted order, with repeated elements
product('ABCD', repeat=2)   AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
permutations('ABCD', 2)   AB AC AD BA BC BD CA CB CD DA DB DC
combinations('ABCD', 2)   AB AC AD BC BD CD
combinations_with_replacement('ABCD', 2)   AA AB AC AD BB BC BD CC CD DD

Itertool functions

The following module functions all construct and return iterators. Some provide streams of infinite length, so they should only be accessed by functions or loops that truncate the stream.

Itertools Recipes

This section shows recipes for creating an extended toolset using the existing itertools as building blocks.

The extended tools offer the same high performance as the underlying toolset. The superior memory performance is kept by processing elements one at a time rather than bringing the whole iterable into memory all at once. Code volume is kept small by linking the tools together in a functional style which helps eliminate temporary variables. High speed is retained by preferring "vectorized" building blocks over the use of for-loops and :term:`generator`s which incur interpreter overhead.

Note, many of the above recipes can be optimized by replacing global lookups with local variables defined as default values. For example, the dotproduct recipe can be written as:

def dotproduct(vec1, vec2, sum=sum, map=map, mul=operator.mul):
    return sum(map(mul, vec1, vec2))