9.7. itertools — Fonctions créant des itérateurs pour boucler efficacement.

Nouveau dans la version 2.3.

Ce module implémente de nombreuses briques d’itérateurs inspirées par des constructions de APL, Haskell et SML. Toutes ont été retravaillées dans un format adéquat pour Python.

Ce module standardise un noyau d’outils rapide, efficaces en mémoire qui sont utiles d’eux-mêmes ou en les combinant. Ensemble, ils forment une « algèbre d’itérateurs » rendant possible la construction succincte et efficace d’outils spécialisés en Python seulement.

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 imap() and count() to form imap(f, count()).

These tools and their built-in counterparts also work well with the high-speed functions in the 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)).

Itérateurs infinis :

Itérateur	Arguments	Résultats	Exemple
count()	start, [step]	start, start+step, start+2*step, …	count(10) --> 10 11 12 13 14 ...
cycle()	p	p0, p1, … plast, p0, p1, …	cycle('ABCD') --> A B C D A B C D ...
repeat()	elem [,n]	elem, elem, elem, … à l’infini ou jusqu’à n fois	repeat(10, 3) --> 10 10 10

Itérateurs se terminant par la séquence d’entrée la plus courte :

Itérateur	Arguments	Résultats	Exemple
chain()	p, q, …	p0, p1, … plast, q0, q1, …	chain('ABC', 'DEF') --> A B C D E F
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
dropwhile()	pred, seq	seq[n], seq[n+1], commençant quand pred échoue	dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1
groupby()	iterable[, keyfunc]	sous-itérateurs groupés par la valeur de keyfunc(v)
ifilter()	pred, seq	elements of seq where pred(elem) is true	ifilter(lambda x: x%2, range(10)) --> 1 3 5 7 9
ifilterfalse()	pred, seq	éléments de seq quand pred(elem) est faux	ifilterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8
islice()	seq, [start,] stop [, step]	éléments de seq[start:stop:step]	islice('ABCDEFG', 2, None) --> C D E F G
imap()	func, p, q, …	func(p0, q0), func(p1, q1), …	imap(pow, (2,3,10), (5,2,3)) --> 32 9 1000
starmap()	func, seq	func(*seq[0]), func(*seq[1]), …	starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000
tee()	it, n	it1, it2, … itn sépare un itérateur en n
takewhile()	pred, seq	seq[0], seq[1], jusqu’à ce que pred échoue	takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4
izip()	p, q, …	(p[0], q[0]), (p[1], q[1]), …	izip('ABCD', 'xy') --> Ax By
izip_longest()	p, q, …	(p[0], q[0]), (p[1], q[1]), …	izip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-

Générateurs combinatoires :

Itérateur	Arguments	Résultats
product()	p, q, … [repeat=1]	produit cartésien, équivalent à une boucle for imbriquée
permutations()	p[, r]	tuples de longueur r, tous les ré-arrangements possibles, sans répétition d’éléments
combinations()	p, r	tuples de longueur r, triés, sans répétition d’éléments
combinations_with_replacement()	p, r	tuples de longueur r, triés, avec répétition d’éléments
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

9.7.1. Fonctions d”itertool

Toutes les fonctions de module qui suivent construisent et renvoient des itérateurs. Certaines fournissent des flux de longueur infinie, elles devraient seulement être accédées par des fonctions ou boucles qui tronquent le flux.

itertools.chain(*iterables)

Créer un itérateur qui renvoie les éléments du premier itérable jusqu’à son épuisement, puis continue avec l’itérable suivant jusqu’à ce que tous les itérables soient épuisés. Utilisée pour traiter des séquences consécutives comme une seule séquence Sensiblement équivalente à :

def chain(*iterables):
    # chain('ABC', 'DEF') --> A B C D E F
    for it in iterables:
        for element in it:
            yield element

classmethod chain.from_iterable(iterable)

Constructeur alternatif pour chain(). Récupère des entrées chaînées d’un unique argument itérable qui est évalué de manière paresseuse. Sensiblement équivalente à :

def from_iterable(iterables):
    # chain.from_iterable(['ABC', 'DEF']) --> A B C D E F
    for it in iterables:
        for element in it:
            yield element

Nouveau dans la version 2.6.

itertools.combinations(iterable, r)

Renvoyer les sous-séquences de longueur r de l’itérable iterable.

Les combinaisons sont émises dans l’ordre lexicographique. Ainsi, si l’itérable iterable est trié, les tuples de combinaison seront produits dans l’ordre.

Les éléments sont considérés comme uniques en fonction de leur position, et non pas de leur valeur. Ainsi, si les éléments en entrée sont uniques, il n’y aura pas de valeurs répétées dans chaque combinaison.

Sensiblement équivalent à :

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = range(r)
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

Le code de combinations() peut aussi être exprimé comme une sous-séquence de permutations() après avoir filtré les entrées dont les éléments ne sont pas triés (selon leur position dans le pool d’entrée) :

def combinations(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    for indices in permutations(range(n), r):
        if sorted(indices) == list(indices):
            yield tuple(pool[i] for i in indices)

Le nombre d’éléments renvoyés est n! / r! / (n-r)! quand 0 <= r <= n ou zéro quand r > n.

Nouveau dans la version 2.6.

itertools.combinations_with_replacement(iterable, r)

Renvoyer les sous-séquences de longueur r des éléments de l’itérable iterable d’entrée, permettant aux éléments individuels d’être répétés plus d’une fois.

Les combinaisons sont émises dans l’ordre lexicographique. Ainsi, si l’itérable iterable est trié, les tuples de combinaison seront produits dans l’ordre.

Les éléments sont considérés comme uniques en fonction de leur position, et non pas de leur valeur. Ainsi si les éléments d’entrée sont uniques, les combinaisons générées seront aussi uniques.

Sensiblement équivalent à :

def combinations_with_replacement(iterable, r):
    # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return
    indices = [0] * r
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        yield tuple(pool[i] for i in indices)

Le code pour combinations_with_replacement() peut aussi être exprimé comme une sous-séquence de product() après avoir filtré les entrées où les éléments ne sont pas dans triés (selon leur position dans le pool d’entrée) :

def combinations_with_replacement(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    for indices in product(range(n), repeat=r):
        if sorted(indices) == list(indices):
            yield tuple(pool[i] for i in indices)

Le nombre d’éléments renvoyés est (n+r-1)! / r! / (n-1)! quand n > 0.

Nouveau dans la version 2.7.

itertools.compress(data, selectors)

Créer un itérateur qui filtre les éléments de data, renvoyant seulement ceux qui ont un élément correspondant dans selectors qui évalue à True. S’arrête quand l’itérable data ou selectors a été épuisé. Sensiblement équivalent à :

def compress(data, selectors):
    # compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F
    return (d for d, s in izip(data, selectors) if s)

Nouveau dans la version 2.7.

itertools.count(start=0, step=1)

Make an iterator that returns evenly spaced values starting with n. Often used as an argument to imap() to generate consecutive data points. Also, used with izip() to add sequence numbers. Equivalent to:

def count(start=0, step=1):
    # count(10) --> 10 11 12 13 14 ...
    # count(2.5, 0.5) -> 2.5 3.0 3.5 ...
    n = start
    while True:
        yield n
        n += step

Quand on compte avec des nombres à virgule flottante, il est parfois possible d’obtenir une meilleure précision en substituant du code multiplicateur comme : (start + step * i for i in count()).

Modifié dans la version 2.7: added step argument and allowed non-integer arguments.

itertools.cycle(iterable)

Créer un itérateur qui renvoie les éléments de l’itérable et qui sauvegarde une copie de chaque. Quand l’itérable est épuisé, renvoyer les éléments depuis la copie sauvegardée. Répète à l’infini. Sensiblement équivalent à :

def cycle(iterable):
    # cycle('ABCD') --> A B C D A B C D A B C D ...
    saved = []
    for element in iterable:
        yield element
        saved.append(element)
    while saved:
        for element in saved:
              yield element

Note, cette fonction pourrait avoir besoin d’un stockage auxiliaire important (en fonction de la longueur de l’itérable).

itertools.dropwhile(predicate, iterable)

Créer un itérateur qui saute les éléments de l’itérable tant que le prédicat est vrai ; ensuite, renvoyer chaque élément. Note, l’itérateur ne produit aucune sortie avant que le prédicat ne devienne faux, il peut donc avoir un temps de démarrage long. Sensiblement équivalent à :

def dropwhile(predicate, iterable):
    # dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1
    iterable = iter(iterable)
    for x in iterable:
        if not predicate(x):
            yield x
            break
    for x in iterable:
        yield x

itertools.groupby(iterable[, key])

Créer un itérateur qui renvoie les clés et les groupes de l’itérable iterable. La clé key est une fonction qui génère une clé pour chaque élément. Si key n’est pas spécifié ou est None, elle vaut par défaut une fonction d’identité qui renvoie l’élément sans le modifier. Généralement, l’itérable a besoin d’être déjà trié selon cette même fonction de clé.

L’opération de groupby() est similaire au filtre uniq dans Unix. Elle génère un nouveau groupe à chaque fois que la valeur de la fonction key change (ce pourquoi il est souvent nécessaire d’avoir trié les données selon la même fonction de clé). Ce comportement est différent de celui de GROUP BY de SQL qui agrège les éléments sans prendre compte de leur ordre d’entrée.

Le groupe renvoyé est lui-même un itérateur qui partage l’itérable sous-jacent avec groupby(). Puisque que la source est partagée, quand l’objet groupby() est avancé, le groupe précédent n’est plus visible. Ainsi, si cette donnée doit être utilisée plus tard, elle devrait être stockée comme une liste :

groups = []
uniquekeys = []
data = sorted(data, key=keyfunc)
for k, g in groupby(data, keyfunc):
    groups.append(list(g))      # Store group iterator as a list
    uniquekeys.append(k)

groupby() est sensiblement équivalent à :

class groupby(object):
    # [k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B
    # [list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D
    def __init__(self, iterable, key=None):
        if key is None:
            key = lambda x: x
        self.keyfunc = key
        self.it = iter(iterable)
        self.tgtkey = self.currkey = self.currvalue = object()
    def __iter__(self):
        return self
    def next(self):
        while self.currkey == self.tgtkey:
            self.currvalue = next(self.it)    # Exit on StopIteration
            self.currkey = self.keyfunc(self.currvalue)
        self.tgtkey = self.currkey
        return (self.currkey, self._grouper(self.tgtkey))
    def _grouper(self, tgtkey):
        while self.currkey == tgtkey:
            yield self.currvalue
            self.currvalue = next(self.it)    # Exit on StopIteration
            self.currkey = self.keyfunc(self.currvalue)

Nouveau dans la version 2.4.

itertools.ifilter(predicate, iterable)

Make an iterator that filters elements from iterable returning only those for which the predicate is True. If predicate is None, return the items that are true. Roughly equivalent to:

def ifilter(predicate, iterable):
    # ifilter(lambda x: x%2, range(10)) --> 1 3 5 7 9
    if predicate is None:
        predicate = bool
    for x in iterable:
        if predicate(x):
            yield x

itertools.ifilterfalse(predicate, iterable)

Créer un itérateur qui filtre les éléments de iterable, ne renvoyant seulement ceux pour lesquels le prédicat est Faux. Si predicate vaut None, renvoyer les éléments qui sont faux. Sensiblement équivalent à :

def ifilterfalse(predicate, iterable):
    # ifilterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8
    if predicate is None:
        predicate = bool
    for x in iterable:
        if not predicate(x):
            yield x

itertools.imap(function, *iterables)

Make an iterator that computes the function using arguments from each of the iterables. If function is set to None, then imap() returns the arguments as a tuple. Like map() but stops when the shortest iterable is exhausted instead of filling in None for shorter iterables. The reason for the difference is that infinite iterator arguments are typically an error for map() (because the output is fully evaluated) but represent a common and useful way of supplying arguments to imap(). Roughly equivalent to:

def imap(function, *iterables):
    # imap(pow, (2,3,10), (5,2,3)) --> 32 9 1000
    iterables = map(iter, iterables)
    while True:
        args = [next(it) for it in iterables]
        if function is None:
            yield tuple(args)
        else:
            yield function(*args)

itertools.islice(iterable, stop)

itertools.islice(iterable, start, stop[, step])

Créer un itérateur qui renvoie les élément sélectionnés de l’itérable. Si start est non-nul, alors les éléments de l’itérable sont sautés jusqu’à ce que start soit atteint. Ensuite, les éléments sont renvoyés consécutivement sauf si step est plus grand que 1, auquel cas certains éléments seront sautés. Si stop est None, alors l’itération continue jusqu’à ce que l’itérateur soit épuisé s’il ne l’est pas déjà ; sinon, il s’arrête à la position spécifiée. À la différence du slicing standard, slice() ne supporte pas les valeurs négatives pour start, stop ou step. Peut être utilisée pour extraire les champs apparentés depuis des données dont la structure interne a été aplatie (par exemple, un rapport multi-ligne pourrait lister un nom de champ toutes les trois lignes). Sensiblement similaire à :

def islice(iterable, *args):
    # islice('ABCDEFG', 2) --> A B
    # islice('ABCDEFG', 2, 4) --> C D
    # islice('ABCDEFG', 2, None) --> C D E F G
    # islice('ABCDEFG', 0, None, 2) --> A C E G
    s = slice(*args)
    start, stop, step = s.start or 0, s.stop or sys.maxint, s.step or 1
    it = iter(xrange(start, stop, step)))
    try:
        nexti = next(it)
    except StopIteration:
        # Consume *iterable* up to the *start* position.
        for i, element in izip(xrange(start), iterable):
            pass
        return
    try:
        for i, element in enumerate(iterable):
            if i == nexti:
                yield element
                nexti = next(it)
    except StopIteration:
        # Consume to *stop*.
        for i, element in izip(xrange(i + 1, stop), iterable):
            pass

Si start vaut None, alors l’itération commence à zéro. Si step vaut None, alors le pas est à 1 par défaut.

Modifié dans la version 2.5: accept None values for default start and step.

itertools.izip(*iterables)

Make an iterator that aggregates elements from each of the iterables. Like zip() except that it returns an iterator instead of a list. Used for lock-step iteration over several iterables at a time. Roughly equivalent to:

def izip(*iterables):
    # izip('ABCD', 'xy') --> Ax By
    iterators = map(iter, iterables)
    while iterators:
        yield tuple(map(next, iterators))

Modifié dans la version 2.4: When no iterables are specified, returns a zero length iterator instead of raising a TypeError exception.

The left-to-right evaluation order of the iterables is guaranteed. This makes possible an idiom for clustering a data series into n-length groups using izip(*[iter(s)]*n).

izip() should only be used with unequal length inputs when you don’t care about trailing, unmatched values from the longer iterables. If those values are important, use izip_longest() instead.

itertools.izip_longest(*iterables[, fillvalue])

Créer un itérateur qui agrège les éléments de chacun des itérables. Si les itérables sont de longueurs différentes, les valeurs manquantes sont remplacées par fillvalue. L’itération continue jusqu’à ce que l’itérable le plus long soit épuisé. Sensiblement équivalent à :

class ZipExhausted(Exception):
    pass

def izip_longest(*args, **kwds):
    # izip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-
    fillvalue = kwds.get('fillvalue')
    counter = [len(args) - 1]
    def sentinel():
        if not counter[0]:
            raise ZipExhausted
        counter[0] -= 1
        yield fillvalue
    fillers = repeat(fillvalue)
    iterators = [chain(it, sentinel(), fillers) for it in args]
    try:
        while iterators:
            yield tuple(map(next, iterators))
    except ZipExhausted:
        pass

If one of the iterables is potentially infinite, then the izip_longest() function should be wrapped with something that limits the number of calls (for example islice() or takewhile()). If not specified, fillvalue defaults to None.

Nouveau dans la version 2.6.

itertools.permutations(iterable[, r])

Renvoyer les permutations successives de longueur r des éléments de iterable.

Si r n’est pas spécifié ou vaut None, alors r a pour valeur la longueur de iterable et toutes les permutations de longueur r possibles sont générées.

Les permutations sont émises dans l’ordre lexicographique. Ainsi, si l’itérable d’entrée iterable est trié, les tuples de permutation seront produits dans l’ordre.

Les éléments sont considérés comme uniques en fonction de leur position, et non pas de leur valeur. Ainsi, si l’élément est unique, il n’y aura pas de valeurs répétées dans chaque permutation.

Sensiblement équivalent à :

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

Le code pour permutations() peut aussi être exprimé comme une sous-séquence de product(), filtré pour exclure les entrées avec des éléments répétés (celles de la même position dans la pool d’entrée) :

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

Le nombre d’éléments renvoyés est n! / (n-r)! quand 0 <= r <= n ou zéro quand r > n.

Nouveau dans la version 2.6.

itertools.product(*iterables[, repeat])

Produit cartésien des itérables d’entrée.

Sensiblement équivalent à des boucles for imbriquées dans une expression de générateur. Par exemple product(A, B) renvoie la même chose que ((x, y) for x in A for y in B).

Les boucles imbriquées tournent comme un compteur kilométrique avec l’élément le plus à droite avançant à chaque itération. ce motif créé un tri lexicographique afin que si les itérables de l’entrée sont triés, les tuples de produit sont émis dans l’ordre.

Pour générer le produit d’un itérable avec lui-même, spécifier le nombre de répétitions avec le paramètre nommé optionnel repeat. Par exemple, product(A, repeat=4) veut dire la même chose que product(A, A, A, A).

Cette fonction est sensiblement équivalente au code suivant, saut que la vraie implémentation ne créé pas les résultats intermédiaires en mémoire :

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

Nouveau dans la version 2.6.

itertools.repeat(object[, times])

Make an iterator that returns object over and over again. Runs indefinitely unless the times argument is specified. Used as argument to imap() for invariant function parameters. Also used with izip() to create constant fields in a tuple record. Roughly equivalent to:

def repeat(object, times=None):
    # repeat(10, 3) --> 10 10 10
    if times is None:
        while True:
            yield object
    else:
        for i in xrange(times):
            yield object

A common use for repeat is to supply a stream of constant values to imap or zip:

>>> list(imap(pow, xrange(10), repeat(2)))
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

itertools.starmap(function, iterable)

Make an iterator that computes the function using arguments obtained from the iterable. Used instead of imap() when argument parameters are already grouped in tuples from a single iterable (the data has been « pre-zipped »). The difference between imap() and starmap() parallels the distinction between function(a,b) and function(*c). Roughly equivalent to:

def starmap(function, iterable):
    # starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000
    for args in iterable:
        yield function(*args)

Modifié dans la version 2.6: Previously, starmap() required the function arguments to be tuples. Now, any iterable is allowed.

itertools.takewhile(predicate, iterable)

Créer un itérateur qui renvoie les éléments d’un itérable tant que le prédicat est vrai. Sensiblement équivalent à :

def takewhile(predicate, iterable):
    # takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4
    for x in iterable:
        if predicate(x):
            yield x
        else:
            break

itertools.tee(iterable[, n=2])

Return n independent iterators from a single iterable. Roughly equivalent to:

def tee(iterable, n=2):
    it = iter(iterable)
    deques = [collections.deque() for i in range(n)]
    def gen(mydeque):
        while True:
            if not mydeque:             # when the local deque is empty
                newval = next(it)       # fetch a new value and
                for d in deques:        # load it to all the deques
                    d.append(newval)
            yield mydeque.popleft()
    return tuple(gen(d) for d in deques)

Une fois que tee() a créé un branchement, l’itérable iterable ne devrait être utilisé nulle part ailleurs ; sinon, iterable pourrait être avancé sans que les objets tee soient informés.

tee iterators are not threadsafe. A RuntimeError may be raised when using simultaneously iterators returned by the same tee() call, even if the original iterable is threadsafe.

Cet outil pourrait avoir besoin d’un stockage auxiliaire important (en fonction de la taille des données temporaires nécessaires). En général, si un itérateur utilise la majorité ou toute la donnée avant qu’un autre itérateur ne commence, il est plus rapide d’utiliser list() à la place de tee().

Nouveau dans la version 2.4.

9.7.2. Cas pratiques

Cette section montre des recettes pour créer une boîte à outil étendue en se servant des itertools existants comme de briques.

Ces outils dérivés offrent la même bonne performance que les outils sous-jacents. La performance mémoire supérieure est gardée en traitant les éléments un à la fois plutôt que de charger tout l’itérable en mémoire en même temps. Le volume de code reste bas grâce à un chaînage de style fonctionnel qui aide à éliminer des variables temporaires. La grande vitesse est gardée en préférant les briques « vectorisées » plutôt que les boucles for et les générateurs qui engendrent du sur-coût de traitement.

def take(n, iterable):
    "Return first n items of the iterable as a list"
    return list(islice(iterable, n))

def tabulate(function, start=0):
    "Return function(0), function(1), ..."
    return imap(function, count(start))

def consume(iterator, n=None):
    "Advance the iterator n-steps ahead. If n is None, consume entirely."
    # Use functions that consume iterators at C speed.
    if n is None:
        # feed the entire iterator into a zero-length deque
        collections.deque(iterator, maxlen=0)
    else:
        # advance to the empty slice starting at position n
        next(islice(iterator, n, n), None)

def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    return next(islice(iterable, n, None), default)

def all_equal(iterable):
    "Returns True if all the elements are equal to each other"
    g = groupby(iterable)
    return next(g, True) and not next(g, False)

def quantify(iterable, pred=bool):
    "Count how many times the predicate is true"
    return sum(imap(pred, iterable))

def padnone(iterable):
    """Returns the sequence elements and then returns None indefinitely.

    Useful for emulating the behavior of the built-in map() function.
    """
    return chain(iterable, repeat(None))

def ncycles(iterable, n):
    "Returns the sequence elements n times"
    return chain.from_iterable(repeat(tuple(iterable), n))

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

def flatten(listOfLists):
    "Flatten one level of nesting"
    return chain.from_iterable(listOfLists)

def repeatfunc(func, times=None, *args):
    """Repeat calls to func with specified arguments.

    Example:  repeatfunc(random.random)
    """
    if times is None:
        return starmap(func, repeat(args))
    return starmap(func, repeat(args, times))

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)

def grouper(iterable, n, fillvalue=None):
    "Collect data into fixed-length chunks or blocks"
    # grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx
    args = [iter(iterable)] * n
    return izip_longest(fillvalue=fillvalue, *args)

def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    # Recipe credited to George Sakkis
    pending = len(iterables)
    nexts = cycle(iter(it).next for it in iterables)
    while pending:
        try:
            for next in nexts:
                yield next()
        except StopIteration:
            pending -= 1
            nexts = cycle(islice(nexts, pending))

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in ifilterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

def unique_justseen(iterable, key=None):
    "List unique elements, preserving order. Remember only the element just seen."
    # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B
    # unique_justseen('ABBCcAD', str.lower) --> A B C A D
    return imap(next, imap(itemgetter(1), groupby(iterable, key)))

def iter_except(func, exception, first=None):
    """ Call a function repeatedly until an exception is raised.

    Converts a call-until-exception interface to an iterator interface.
    Like __builtin__.iter(func, sentinel) but uses an exception instead
    of a sentinel to end the loop.

    Examples:
        bsddbiter = iter_except(db.next, bsddb.error, db.first)
        heapiter = iter_except(functools.partial(heappop, h), IndexError)
        dictiter = iter_except(d.popitem, KeyError)
        dequeiter = iter_except(d.popleft, IndexError)
        queueiter = iter_except(q.get_nowait, Queue.Empty)
        setiter = iter_except(s.pop, KeyError)

    """
    try:
        if first is not None:
            yield first()
        while 1:
            yield func()
    except exception:
        pass

def random_product(*args, **kwds):
    "Random selection from itertools.product(*args, **kwds)"
    pools = map(tuple, args) * kwds.get('repeat', 1)
    return tuple(random.choice(pool) for pool in pools)

def random_permutation(iterable, r=None):
    "Random selection from itertools.permutations(iterable, r)"
    pool = tuple(iterable)
    r = len(pool) if r is None else r
    return tuple(random.sample(pool, r))

def random_combination(iterable, r):
    "Random selection from itertools.combinations(iterable, r)"
    pool = tuple(iterable)
    n = len(pool)
    indices = sorted(random.sample(xrange(n), r))
    return tuple(pool[i] for i in indices)

def random_combination_with_replacement(iterable, r):
    "Random selection from itertools.combinations_with_replacement(iterable, r)"
    pool = tuple(iterable)
    n = len(pool)
    indices = sorted(random.randrange(n) for i in xrange(r))
    return tuple(pool[i] for i in indices)

def tee_lookahead(t, i):
    """Inspect the i-th upcomping value from a tee object
       while leaving the tee object at its current position.

       Raise an IndexError if the underlying iterator doesn't
       have enough values.

    """
    for value in islice(t.__copy__(), i, None):
        return value
    raise IndexError(i)

Note, beaucoup des recettes ci-dessus peuvent être optimisées en replaçant les recherches globales par des recherches locales avec des variables locales définies comme des valeurs par défaut. Par exemple, la recette dotproduct peut être écrite comme :

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