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

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

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

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

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

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

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

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

1. Функции itertools

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

itertools.accumulate(iterable[, func])

Создаёт итератор, возвращающий накопленные суммы или накопленные результаты других бинарных функций (указанных в необязательном аргументе func). Если func указан, он должен быть функцией с двумя аргументами. Элементы входного iterable могут быть любого типа, который может быть принят в качестве аргументов для func. (Например, при использовании операции сложения по умолчанию, элементы могут быть любого типа, который можно складывать, включая Decimal или Fraction.) Если входной iterable пустой, то выходной iterable тоже будет пустым.

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

def accumulate(iterable, func=operator.add):
    'Return running totals'
    # accumulate([1,2,3,4,5]) --> 1 3 6 10 15
    # accumulate([1,2,3,4,5], operator.mul) --> 1 2 6 24 120
    it = iter(iterable)
    try:
        total = next(it)
    except StopIteration:
        return
    yield total
    for element in it:
        total = func(total, element)
        yield total

Есть ряд применений для аргумента func. Его можно установить на min() для нахождения текущего минимума, max() для нахождения текущего максимума или operator.mul() для нахождения текущего произведения. Таблицы амортизации могут быть построены путём накопления процентов и применения платежей. Линейные рекуррентные соотношения могут быть смоделированы, если в iterable указать начальное значение и использовать только накопленную сумму в аргументе func:

>>> data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8]
>>> list(accumulate(data, operator.mul))     # running product
[3, 12, 72, 144, 144, 1296, 0, 0, 0, 0]
>>> list(accumulate(data, max))              # running maximum
[3, 4, 6, 6, 6, 9, 9, 9, 9, 9]

# Amortize a 5% loan of 1000 with 4 annual payments of 90
>>> cashflows = [1000, -90, -90, -90, -90]
>>> list(accumulate(cashflows, lambda bal, pmt: bal*1.05 + pmt))
[1000, 960.0, 918.0, 873.9000000000001, 827.5950000000001]

# Chaotic recurrence relation https://en.wikipedia.org/wiki/Logistic_map
>>> logistic_map = lambda x, _:  r * x * (1 - x)
>>> r = 3.8
>>> x0 = 0.4
>>> inputs = repeat(x0, 36)     # only the initial value is used
>>> [format(x, '.2f') for x in accumulate(inputs, logistic_map)]
['0.40', '0.91', '0.30', '0.81', '0.60', '0.92', '0.29', '0.79', '0.63',
 '0.88', '0.39', '0.90', '0.33', '0.84', '0.52', '0.95', '0.18', '0.57',
 '0.93', '0.25', '0.71', '0.79', '0.63', '0.88', '0.39', '0.91', '0.32',
 '0.83', '0.54', '0.95', '0.20', '0.60', '0.91', '0.30', '0.80', '0.60']

См. functools.reduce() для подобной функции, возвращающей только конечное накопленное значение.

Новое в версии 3.2.

Изменено в версии 3.3: Добавлен необязательный параметр func.

itertools.chain(*iterables)

Создаёт итератор, возвращающий элементы из первого iterable до его исчерпания, затем переходит к следующему iterable, пока все 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(). Получает входные данные, сцепленные из одного iterable аргумента, который оценивается лениво. Приблизительно эквивалентно:

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

itertools.combinations(iterable, r)

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

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

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

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

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 = list(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.

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.

Введено в версии 3.1.

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 zip(data, selectors) if s)

Введено в версии 3.1.

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

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

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()).

Изменено в версии 3.1: Добавлен аргумент 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.filterfalse(predicate, iterable)

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

def filterfalse(predicate, iterable):
    # filterfalse(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.groupby(iterable, key=None)

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

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

Возвращаемая группа сама по себе является итератором, который разделяет исходный итерируемый объект с 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:
    # [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
            try:
                self.currvalue = next(self.it)
            except StopIteration:
                return
            self.currkey = self.keyfunc(self.currvalue)

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)
    it = iter(range(s.start or 0, s.stop or sys.maxsize, s.step or 1))
    try:
        nexti = next(it)
    except StopIteration:
        return
    for i, element in enumerate(iterable):
        if i == nexti:
            yield element
            nexti = next(it)

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

itertools.permutations(iterable, r=None)

Возвращает последовательные перестановки длины 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 = list(range(n))
    cycles = list(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.

itertools.product(*iterables, repeat=1)

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

Приблизительно эквивалентно вложенным циклам 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, repeat=1):
    # 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 = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

itertools.repeat(object[, times])

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

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

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

Распространённое использование repeat — предоставление потока постоянных значений для map или zip:

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

itertools.starmap(function, iterable)

Создаёт итератор, вычисляющий функцию с аргументами, полученными из итерируемого объекта. Используется вместо map(), когда аргументы уже сгруппированы в кортежи из одного итерируемого объекта (данные были «предварительно сжаты»). Различие между map() и 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)

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
                try:
                    newval = next(it)   # fetch a new value and
                except StopIteration:
                    return
                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.

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

itertools.zip_longest(*iterables, fillvalue=None)

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

class ZipExhausted(Exception):
    pass

def zip_longest(*args, **kwds):
    # zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-
    fillvalue = kwds.get('fillvalue')
    counter = len(args) - 1
    def sentinel():
        nonlocal counter
        if not counter:
            raise ZipExhausted
        counter -= 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

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

2. Рецепты модуля Itertools

Этот раздел демонстрирует рецепты для создания расширенного набора инструментов с использованием существующих инструментов 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 map(function, count(start))

def tail(n, iterable):
    "Return an iterator over the last n items"
    # tail(3, 'ABCDEFG') --> E F G
    return iter(collections.deque(iterable, maxlen=n))

def consume(iterator, n):
    "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(map(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(map(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 zip(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 zip_longest(*args, fillvalue=fillvalue)

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 partition(pred, iterable):
    'Use a predicate to partition entries into false entries and true entries'
    # partition(is_odd, range(10)) --> 0 2 4 6 8   and  1 3 5 7 9
    t1, t2 = tee(iterable)
    return filterfalse(pred, t1), filter(pred, t2)

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 filterfalse(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 map(next, map(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 builtins.iter(func, sentinel) but uses an exception instead
    of a sentinel to end the loop.

    Examples:
        iter_except(functools.partial(heappop, h), IndexError)   # priority queue iterator
        iter_except(d.popitem, KeyError)                         # non-blocking dict iterator
        iter_except(d.popleft, IndexError)                       # non-blocking deque iterator
        iter_except(q.get_nowait, Queue.Empty)                   # loop over a producer Queue
        iter_except(s.pop, KeyError)                             # non-blocking set iterator

    """
    try:
        if first is not None:
            yield first()            # For database APIs needing an initial cast to db.first()
        while True:
            yield func()
    except exception:
        pass

def first_true(iterable, default=False, pred=None):
    """Returns the first true value in the iterable.

    If no true value is found, returns *default*

    If *pred* is not None, returns the first item
    for which pred(item) is true.

    """
    # first_true([a,b,c], x) --> a or b or c or x
    # first_true([a,b], x, f) --> a if f(a) else b if f(b) else x
    return next(filter(pred, iterable), default)

def random_product(*args, repeat=1):
    "Random selection from itertools.product(*args, **kwds)"
    pools = [tuple(pool) for pool in args] * repeat
    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(range(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 range(r))
    return tuple(pool[i] for i in indices)

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

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