# :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:imap and :func:count to form imap(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(imap(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: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:groupby iterable[, keyfunc] sub-iterators grouped by value of keyfunc(v)
:func:ifilter pred, seq elements of seq where pred(elem) is True ifilter(lambda x: x%2, range(10)) --> 1 3 5 7 9
:func:ifilterfalse pred, seq elements of seq where pred(elem) is False ifilterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8
:func:islice seq, [start,] stop [, step] elements from seq[start:stop:step] islice('ABCDEFG', 2, None) --> C D E F G
:func:imap func, p, q, ... func(p0, q0), func(p1, q1), ... imap(pow, (2,3,10), (5,2,3)) --> 32 9 1000
:func:starmap func, seq func(*seq[0]), func(*seq[1]), ... starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000
:func:tee it, n it1, it2 , ... itn splits one iterator into n
:func:takewhile pred, seq seq[0], seq[1], until pred fails takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4
:func:izip p, q, ... (p[0], q[0]), (p[1], q[1]), ... izip('ABCD', 'xy') --> Ax By
:func:izip_longest p, q, ... (p[0], q[0]), (p[1], q[1]), ... izip_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.

## 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:generators 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, imap=imap, mul=operator.mul):
return sum(imap(mul, vec1, vec2))