itertools — Функции для создания итераторов для эффективной итерации

Этот модуль реализует ряд итераторов, вдохновленных конструкциями из APL, Haskell и SML. Каждый из них переработан в форме, подходящей для Python.

Модуль стандартизирует набор быстрых, экономичных инструментов памяти, полезных как сами по себе, так и в комбинации. Вместе они образуют «алгебру итераторов», позволяющую создавать специализированные инструменты лаконично и эффективно на чистом Python.

Например, SML предоставляет инструмент табуляции: tabulate(f) , который производит последовательность f(0), f(1), .... Такой же эффект можно достичь в Python, объединив imap() и count() для формирования imap(f, count()).

Эти инструменты, а также их встроенные аналоги, также хорошо работают с высокоскоростными функциями в модуле operator. Например, оператор умножения может быть применён к двум векторам для формирования эффективного скалярного произведения: sum(imap(operator.mul, vector1, vector2)).

Бесконечные итераторы:

Итераторы, завершающиеся на самой короткой входной последовательности:

Комбинаторные генераторы:

1. Функции itertools

Все следующие функции модуля строят и возвращают итераторы. Некоторые предоставляют потоки бесконечной длины, поэтому к ним следует обращаться только функциям или циклам, которые усекают поток.

itertools.chain(*iterables)

Создаёт итератор, возвращающий элементы из первого итерируемого объекта до его исчерпания, затем переходит к следующему итерируемому объекту и так далее, пока все итерируемые объекты не будут исчерпаны. Используется для обработки последовательных последовательностей как одной последовательности. Примерно эквивалентно:

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)

Альтернативный конструктор для chain(). Получает введные последовательности из одного итерируемого объекта, который оценивается лениво. Примерно эквивалентно:

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

Новая в версии 2.6.

itertools.combinations(iterable, r)

Возвращает подпоследовательности длины r элементов из входного итерируемого объекта.

Комбинации выводятся в лексикографическом порядке. Таким образом, если входной итерируемый объект отсортирован, кортежи комбинаций будут выведены в отсортированном порядке.

Элементы обрабатываются как уникальные на основе их позиции, а не их значения. Поэтому, если входные элементы уникальны, в каждой комбинации не будет повторяющихся значений.

Приблизительно эквивалентно:

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)

Код для combinations() также может быть выражен как подпоследовательность permutations() после фильтрации записей, где элементы не отсортированы (в соответствии с их позицией в входном наборе):

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)

Число возвращаемых элементов равно n! / r! / (n-r)! при 0 <= r <= n, или ноль, когда r > n.

Новая в версии 2.6.

itertools.combinations_with_replacement(iterable, r)

Возвращает подпоследовательности длины r элементов из входного итерируемого объекта, позволяя повторять отдельные элементы более одного раза.

Комбинации выводятся в лексикографическом порядке. Если входной итерируемый объект отсортирован, кортежи комбинаций будут выведены в отсортированном порядке.

Элементы обрабатываются как уникальные на основе их позиции, а не их значения. Если входные элементы уникальны, сгенерированные комбинации также будут уникальны.

Приблизительно эквивалентно:

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)

Код для combinations_with_replacement() также может быть выражен как подпоследовательность product() после фильтрации записей, где элементы не отсортированы (в соответствии с их позицией в входном наборе):

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)

Число возвращаемых элементов равно (n+r-1)! / r! / (n-1)! при n > 0.

Новая в версии 2.7.

itertools.compress(data, selectors)

Создаёт итератор, фильтрующий элементы из data, возвращая только те, у которых соответствующий элемент в selectors имеет значение True. Остановка происходит при исчерпании одного из итерируемых объектов data или selectors. Примерно эквивалентно:

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)

Добавлена в версии 2.7.

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

Создаёт итератор, возвращающий равномерно распределённые значения, начиная с n. Часто используется в качестве аргумента для imap() для генерации последовательных точек данных. Также используется с izip() для добавления порядковых номеров. Эквивалентно:

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

При подсчёте с плавающей точкой, иногда можно добиться большей точности, заменив умножение на код вида: (start + step * i for i in count()).

Изменено в версии 2.7: добавлено аргумент step и разрешены нецелочисленные аргументы.

itertools.cycle(iterable)

Создаёт итератор, возвращающий элементы из итерируемого объекта, сохраняя копию каждого элемента. После исчерпания итерируемого объекта, возвращает элементы из сохранённой копии. Повторяется бесконечно. Примерно эквивалентно:

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

Обратите внимание, что этот член набора инструментов может потребовать значительного вспомогательного хранилища (в зависимости от длины итерируемого объекта).

itertools.dropwhile(predicate, iterable)

Создаёт итератор, пропускающий элементы из итерируемого объекта, пока предикат истинен; после этого возвращает каждый элемент. Обратите внимание, что итератор не выводит никаких результатов, пока предикат не станет ложным, поэтому у него может быть длительная начальная загрузка. Примерно эквивалентно:

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

Создаёт итератор, возвращающий последовательные ключи и группы из итерируемого объекта. Ключ — это функция, вычисляющая значение ключа для каждого элемента. Если не указано или равно None, по умолчанию ключ — это функция тождества, которая возвращает элемент без изменений. Как правило, итерируемый объект должен быть отсортирован по той же функции ключа.

Действие groupby() аналогично фильтру uniq в Unix. Он генерирует разрыв или новую группу каждый раз, когда значение функции ключа меняется (поэтому обычно необходимо отсортировать данные с использованием той же функции ключа). Это поведение отличается от SQL GROUP BY, который агрегирует общие элементы независимо от порядка ввода.

Возвращаемая группа сама по себе является итератором, который разделяет исходный итерируемый объект с groupby(). Поскольку исходный итерируемый объект общий, когда объект groupby() перемещается вперёд, предыдущая группа становится недоступной. Поэтому, если эти данные понадобятся позднее, их следует сохранить в списке:

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() примерно эквивалентно:

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)

Добавлена в версии 2.4.

itertools.ifilter(predicate, iterable)

Создаёт итератор, фильтрующий элементы из итерируемого объекта, возвращая только те, для которых предикат является True. Если предикат None, то возвращаются элементы, которые истинны. Примерно эквивалентно:

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)

Создаёт итератор, фильтрующий элементы из итерируемого объекта, возвращая только те, для которых предикат False. Если предикат None, то возвращаются элементы, которые ложны. Примерно эквивалентно:

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)

Создаёт итератор, вычисляющий функцию, используя аргументы из каждого итерируемого объекта. Если функция установлена в None, то imap() возвращает аргументы в виде кортежа. Аналогично map(), но останавливается, когда исчерпывается самый короткий итерируемый объект, вместо заполнения None для более коротких итерируемых объектов. Причина различия в том, что бесконечные итерируемые аргументы обычно являются ошибкой для map() (поскольку результат полностью вычисляется), но представляют собой распространённый и полезный способ предоставления аргументов для imap(). Примерно эквивалентно:

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

Создаёт итератор, возвращающий выбранные элементы из итерируемого объекта. Если start не равно нулю, то элементы из итерируемого объекта пропускаются до тех пор, пока не будет достигнуто значение start. После этого элементы возвращаются последовательно, если step не установлен выше единицы, что приводит к пропуску элементов. Если stop None, то итерация продолжается до тех пор, пока итератор не исчерпается, если это возможно; иначе она останавливается в указанной позиции. В отличие от обычного среза, islice() не поддерживает отрицательные значения для start, stop или step. Может использоваться для извлечения связанных полей из данных, где внутренняя структура была сглажена (например, многострочный отчёт может перечислять поле имени на каждой третьей строке). Примерно эквивалентно:

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

Если start None, то итерация начинается с нуля. Если step None, то шаг по умолчанию равен единице.

Изменено в версии 2.5: принимает None значения для start и step по умолчанию.

itertools.izip(*iterables)

Создаёт итератор, агрегирующий элементы из каждого из итерируемых объектов. Подобно zip(), за исключением того, что он возвращает итератор вместо списка. Используется для пошаговой итерации по нескольким итерируемым объектам одновременно. Примерно эквивалентно:

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

Изменено в версии 2.4: Если итерируемых объектов не указано, возвращается итератор нулевой длины вместо исключения TypeError.

Порядок вычисления слева направо гарантирован для итерируемых объектов. Это позволяет использовать выражение для группирования последовательности данных на группы длиной n, используя izip(*[iter(s)]*n).

izip() следует использовать только с входами неравной длины, когда вам не важны хвостовые несовпадающие значения из более длинных итерируемых объектов. Если эти значения важны, используйте izip_longest() вместо этого.

itertools.izip_longest(*iterables[, fillvalue])

Создаёт итератор, агрегирующий элементы из каждого из итерируемых объектов. Если итерируемые объекты имеют неравную длину, пропущенные значения заполняются fillvalue. Итерация продолжается до тех пор, пока не исчерпается самый длинный итерируемый объект. Примерно эквивалентно:

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

Если один из итерируемых объектов потенциально бесконечен, то функцию izip_longest() следует обернуть чем-то, что ограничивает количество вызовов (например, islice() или takewhile()). Если не указано, fillvalue по умолчанию None.

Добавлена в версии 2.6.

itertools.permutations(iterable[, r])

Возвращает последовательные перестановки длины r элементов из итерируемого объекта.

Если r не указано или равно None, то r по умолчанию равно длине итерируемого объекта и генерируются все возможные перестановки полной длины.

Перестановки генерируются в лексикографическом порядке. Таким образом, если входной итерируемый объект отсортирован, кортежи перестановок будут генерироваться в отсортированном порядке.

Элементы обрабатываются как уникальные на основе их позиции, а не их значения. Поэтому, если входные элементы уникальны, в каждой перестановке не будет повторяющихся значений.

Примерно эквивалентно:

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

Код для permutations() также может быть выражен как подпоследовательность product(), отфильтрованная для исключения записей с повторяющимися элементами (те, которые из одного и того же положения в исходном наборе):

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)

Количество возвращаемых элементов равно n! / (n-r)! при 0 <= r <= n или нулю при r > n.

Добавлена в версии 2.6.

itertools.product(*iterables[, repeat])

Декартово произведение входных итерируемых объектов.

Приблизительно эквивалентно вложенным циклам for в выражении генератора. Например, product(A, B) возвращает то же самое, что и ((x,y) for x in A for y in B).

Вложенные циклы работают как счётчик оборотов с элементом в правом конце, увеличивающимся на каждой итерации. Этот шаблон создаёт лексикографический порядок, так что, если входные итерируемые объекты отсортированы, кортежи произведения выводятся в отсортированном порядке.

Чтобы вычислить произведение итерируемого объекта с самим собой, укажите количество повторений с помощью необязательного ключевого аргумента repeat. Например, product(A, repeat=4) означает то же самое, что и product(A, A, A, A).

Эта функция примерно эквивалентна следующему коду, за исключением того, что фактическая реализация не строит промежуточные результаты в памяти:

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)

Новая в версии 2.6.

itertools.repeat(object[, times])

Создаёт итератор, который возвращает объект снова и снова. Продолжается бесконечно, если не указан аргумент times. Используется в качестве аргумента для imap() для неизменных параметров функции. Также используется с izip() для создания постоянных полей в записи кортежа. Примерно эквивалентно:

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

Общее использование repeat — предоставление потока постоянных значений для imap или zip:

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

itertools.starmap(function, iterable)

Создаёт итератор, который вычисляет функцию, используя аргументы, полученные из итерируемого объекта. Используется вместо imap(), когда аргументы уже сгруппированы в кортежи из одного итерируемого объекта (данные «предварительно сгруппированы»). Различие между imap() и starmap() аналогично разнице между function(a,b) и function(*c). Примерно эквивалентно:

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

Изменено в версии 2.6: Ранее starmap() требовал, чтобы аргументы функции были кортежами. Теперь разрешены любые итерируемые объекты.

itertools.takewhile(predicate, iterable)

Создаёт итератор, возвращающий элементы из итерируемого объекта, пока предикат истинен. Примерно эквивалентно:

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

Возвращает n независимых итераторов из одного итерируемого объекта. Примерно эквивалентно:

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)

После того, как tee() выполнил разделение, исходный итерируемый объект не должен использоваться нигде ещё; в противном случае итерируемый объект может быть продвинут, не информируя об этом объекты tee.

Итераторы tee() не потокобезопасны. Может быть выброшено исключение RuntimeError при одновременном использовании итераторов, возвращенных одним и тем же вызовом tee(), даже если исходный итерируемый объект потокобезопасен.

Этот итерируемый объект может потребовать значительного вспомогательного хранилища (в зависимости от того, сколько временных данных нужно хранить). В общем случае, если один итератор использует большинство или все данные, прежде чем другой итератор начнёт, быстрее использовать list() вместо tee().

Новая в версии 2.4.

2. Рецепты

В этом разделе представлены рецепты для создания расширенного набора инструментов с использованием существующих itertools в качестве строительных блоков.

Расширенные инструменты обеспечивают такую же высокую производительность, как и базовый набор инструментов. Превосходная производительность в отношении памяти сохраняется за счёт обработки элементов по одному, а не загрузки всего итерируемого объекта в память сразу. Объём кода сохраняется маленьким за счёт связывания инструментов в функциональном стиле, что помогает устранить временные переменные. Высокая скорость сохраняется за счёт предпочтения «векторизованных» строительных блоков перед использованием циклов for и генераторов, которые несут издержки интерпретатора.

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)

Обратите внимание, что многие из вышеупомянутых рецептов можно оптимизировать, заменив глобальные вызовы локальными переменными, определёнными в качестве значений по умолчанию. Например, рецепт dotproduct можно записать следующим образом:

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