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

Функции Itertool

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

itertools.accumulate(iterable[, function, *, initial=None])

Создаёт итератор, возвращающий кумулятивные суммы или кумулятивные результаты от других бинарных функций.

Функция по умолчанию — сложение. Функция должна принимать два аргумента: накопленную сумму и значение из итерируемого объекта.

Если предоставлено начальное значение, накопление начнется с этого значения, и выходной поток будет иметь на один элемент больше, чем входной итерируемый объект.

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

def accumulate(iterable, function=operator.add, *, initial=None):
    'Return running totals'
    # accumulate([1,2,3,4,5]) → 1 3 6 10 15
    # accumulate([1,2,3,4,5], initial=100) → 100 101 103 106 110 115
    # accumulate([1,2,3,4,5], operator.mul) → 1 2 6 24 120

    iterator = iter(iterable)
    total = initial
    if initial is None:
        try:
            total = next(iterator)
        except StopIteration:
            return

    yield total
    for element in iterator:
        total = function(total, element)
        yield total

Аргумент function может быть установлен на min() для текущего минимума, max() для текущего максимума или operator.mul() для текущего произведения. Таблицы амортизации можно построить, накопив проценты и применив платежи:

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

# Amortize a 5% loan of 1000 with 10 annual payments of 90
>>> update = lambda balance, payment: round(balance * 1.05) - payment
>>> list(accumulate(repeat(90, 10), update, initial=1_000))
[1000, 960, 918, 874, 828, 779, 728, 674, 618, 559, 497]

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

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

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

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

itertools.batched(iterable, n)

Разбивает данные из iterable на кортежи длиной n. Последняя партия может быть короче n.

Перебирает входной итерируемый объект и накапливает данные в кортежи размером до n. Вход потребляется лениво, только достаточно для заполнения пакета. Результат выдается сразу, как только пакет заполнен или входной итерируемый объект исчерпан:

>>> flattened_data = ['roses', 'red', 'violets', 'blue', 'sugar', 'sweet']
>>> unflattened = list(batched(flattened_data, 2))
>>> unflattened
[('roses', 'red'), ('violets', 'blue'), ('sugar', 'sweet')]

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

def batched(iterable, n):
    # batched('ABCDEFG', 3) → ABC DEF G
    if n < 1:
        raise ValueError('n must be at least one')
    iterator = iter(iterable)
    while batch := tuple(islice(iterator, n)):
        yield batch

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

itertools.chain(*iterables)

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

def chain(*iterables):
    # chain('ABC', 'DEF') → A B C D E F
    for iterable in iterables:
        yield from iterable

classmethod chain.from_iterable(iterable)

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

def from_iterable(iterables):
    # chain.from_iterable(['ABC', 'DEF']) → A B C D E F
    for iterable in iterables:
        yield from iterable

itertools.combinations(iterable, r)

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

Вывод — подпоследовательность product(), сохраняющая только элементы, которые являются подпоследовательностями iterable. Длина вывода задаётся math.comb(), который вычисляет n! / r! / (n - r)! при 0 ≤ r ≤ n или ноль, когда r > n.

Кортежи комбинаций генерируются в лексикографическом порядке в соответствии с порядком входного 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)

itertools.combinations_with_replacement(iterable, r)

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

Вывод — подпоследовательность product(), которая сохраняет только элементы, являющиеся подпоследовательностями (с возможными повторяющимися элементами) входного iterable. Количество возвращаемых подпоследовательностей равно (n + r - 1)! / r! / (n - 1)! при n > 0.

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

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

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

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)

Добавлена в версии 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 (datum for datum, selector in zip(data, selectors) if selector)

Добавлена в версии 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)

Создаёт итератор, возвращающий элементы из 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)

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

def dropwhile(predicate, iterable):
    # dropwhile(lambda x: x<5, [1,4,6,3,8]) → 6 3 8

    iterator = iter(iterable)
    for x in iterator:
        if not predicate(x):
            yield x
            break

    for x in iterator:
        yield x

Обратите внимание, что этот итератор не выдаёт никакого результата, пока предикат не станет ложным, поэтому у этого итератора может быть длительная фаза запуска.

itertools.filterfalse(predicate, iterable)

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

def filterfalse(predicate, iterable):
    # filterfalse(lambda x: x<5, [1,4,6,3,8]) → 6 8
    if predicate is None:
        predicate = bool
    for x in iterable:
        if not predicate(x):
            yield x

itertools.groupby(iterable, key=None)

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

Действие 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() приблизительно эквивалентно:

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

    keyfunc = (lambda x: x) if key is None else key
    iterator = iter(iterable)
    exhausted = False

    def _grouper(target_key):
        nonlocal curr_value, curr_key, exhausted
        yield curr_value
        for curr_value in iterator:
            curr_key = keyfunc(curr_value)
            if curr_key != target_key:
                return
            yield curr_value
        exhausted = True

    try:
        curr_value = next(iterator)
    except StopIteration:
        return
    curr_key = keyfunc(curr_value)

    while not exhausted:
        target_key = curr_key
        curr_group = _grouper(target_key)
        yield curr_key, curr_group
        if curr_key == target_key:
            for _ in curr_group:
                pass

itertools.islice(iterable, stop)

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

Создаёт итератор, возвращающий выбранные элементы из итерируемого объекта. Работает как срезы последовательностей, но не поддерживает отрицательные значения для start, stop или step.

Если start равно нулю или None, итерация начинается с нуля. В противном случае элементы из итерируемого объекта пропускаются, пока не будет достигнут start.

Если stop равно None, итерация продолжается до исчерпания итератора, если таковой имеется. В противном случае она останавливается в указанной позиции.

Если step равно None, шаг по умолчанию равен одному. Элементы возвращаются последовательно, если 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 = 0 if s.start is None else s.start
    stop = s.stop
    step = 1 if s.step is None else s.step
    if start < 0 or (stop is not None and stop < 0) or step <= 0:
        raise ValueError

    indices = count() if stop is None else range(max(start, stop))
    next_i = start
    for i, element in zip(indices, iterable):
        if i == next_i:
            yield element
            next_i += step

itertools.pairwise(iterable)

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

Количество 2-кортежей в итераторе вывода будет на один меньше, чем количество входных значений. Он будет пустым, если входной итерируемый объект содержит меньше двух значений.

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

def pairwise(iterable):
    # pairwise('ABCDEFG') → AB BC CD DE EF FG
    iterator = iter(iterable)
    a = next(iterator, None)
    for b in iterator:
        yield a, b
        a = b

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

itertools.permutations(iterable, r=None)

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

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

Вывод является подпоследовательностью product(), где записи с повторяющимися элементами отфильтрованы. Длина вывода задаётся значением math.perm(), которое вычисляет n! / (n - r)! когда 0 ≤ r ≤ n или ноль, когда r > n.

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

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

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

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

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(*iterables, 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 iterables] * repeat

    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]

    for prod in result:
        yield tuple(prod)

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

itertools.repeat(object[, times])

Создаёт итератор, который возвращает объект снова и снова. Работает бесконечно, если не указан аргумент times.

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

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,3,8]) → 1 4
    for x in iterable:
        if not predicate(x):
            break
        yield x

Обратите внимание, что элемент, который впервые не удовлетворяет условию предиката, потребляется из входного итератора, и получить к нему доступ невозможно. Это может быть проблемой, если приложение хочет дополнительно потреблять входной итератор после того, как takewhile будет исчерпан. Чтобы обойти эту проблему, рассмотрите использование more-iterools before_and_after() вместо этого.

itertools.tee(iterable, n=2)

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

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

def tee(iterable, n=2):
    iterator = iter(iterable)
    shared_link = [None, None]
    return tuple(_tee(iterator, shared_link) for _ in range(n))

def _tee(iterator, link):
    try:
        while True:
            if link[1] is None:
                link[0] = next(iterator)
                link[1] = [None, None]
            value, link = link
            yield value
    except StopIteration:
        return

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

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

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

itertools.zip_longest(*iterables, fillvalue=None)

Создаёт итератор, который агрегирует элементы из каждого из итерируемых объектов.

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

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

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

def zip_longest(*iterables, fillvalue=None):
    # zip_longest('ABCD', 'xy', fillvalue='-') → Ax By C- D-

    iterators = list(map(iter, iterables))
    num_active = len(iterators)
    if not num_active:
        return

    while True:
        values = []
        for i, iterator in enumerate(iterators):
            try:
                value = next(iterator)
            except StopIteration:
                num_active -= 1
                if not num_active:
                    return
                iterators[i] = repeat(fillvalue)
                value = fillvalue
            values.append(value)
        yield tuple(values)

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

Рецепты itertools

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

Основное назначение рецептов itertools — образовательное. Рецепты показывают различные способы мышления об отдельных инструментах — например, то, что chain.from_iterable связано с понятием сглаживания. Рецепты также дают идеи о способах комбинирования инструментов — например, о том, как starmap() и repeat() могут работать вместе. Рецепты также демонстрируют шаблоны использования itertools с модулями operator и collections, а также с встроенными itertools, такими как map(), filter(), reversed(), и enumerate().

Второстепенное назначение рецептов — роль инкубатора. Итераторы accumulate(), compress(), и pairwise() изначально были рецептами. В настоящее время рецепты sliding_window(), iter_index(), и sieve() проверяются на эффективность.

Практически все эти рецепты и многие другие можно установить из проекта more-itertools на Python Package Index:

python -m pip install more-itertools

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

import collections
import contextlib
import functools
import math
import operator
import random

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

def prepend(value, iterable):
    "Prepend a single value in front of an iterable."
    # prepend(1, [2, 3, 4]) → 1 2 3 4
    return chain([value], iterable)

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

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

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

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

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=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:
        collections.deque(iterator, maxlen=0)
    else:
        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 quantify(iterable, predicate=bool):
    "Given a predicate that returns True or False, count the True results."
    return sum(map(predicate, iterable))

def first_true(iterable, default=False, predicate=None):
    "Returns the first true value or the *default* if there is no true value."
    # 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(predicate, iterable), default)

def all_equal(iterable, key=None):
    "Returns True if all the elements are equal to each other."
    # all_equal('4٤௪౪໔', key=int) → True
    return len(take(2, groupby(iterable, key))) <= 1

def unique_justseen(iterable, key=None):
    "Yield unique elements, preserving order. Remember only the element just seen."
    # unique_justseen('AAAABBBCCDAABBB') → A B C D A B
    # unique_justseen('ABBcCAD', str.casefold) → A B c A D
    if key is None:
        return map(operator.itemgetter(0), groupby(iterable))
    return map(next, map(operator.itemgetter(1), groupby(iterable, key)))

def unique_everseen(iterable, key=None):
    "Yield unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') → A B C D
    # unique_everseen('ABBcCAD', str.casefold) → A B c D
    seen = set()
    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(iterable, key=None, reverse=False):
   "Yield unique elements in sorted order. Supports unhashable inputs."
   # unique([[1, 2], [3, 4], [1, 2]]) → [1, 2] [3, 4]
   return unique_justseen(sorted(iterable, key=key, reverse=reverse), key=key)

def sliding_window(iterable, n):
    "Collect data into overlapping fixed-length chunks or blocks."
    # sliding_window('ABCDEFG', 4) → ABCD BCDE CDEF DEFG
    iterator = iter(iterable)
    window = collections.deque(islice(iterator, n - 1), maxlen=n)
    for x in iterator:
        window.append(x)
        yield tuple(window)

def grouper(iterable, n, *, incomplete='fill', fillvalue=None):
    "Collect data into non-overlapping fixed-length chunks or blocks."
    # grouper('ABCDEFG', 3, fillvalue='x') → ABC DEF Gxx
    # grouper('ABCDEFG', 3, incomplete='strict') → ABC DEF ValueError
    # grouper('ABCDEFG', 3, incomplete='ignore') → ABC DEF
    iterators = [iter(iterable)] * n
    match incomplete:
        case 'fill':
            return zip_longest(*iterators, fillvalue=fillvalue)
        case 'strict':
            return zip(*iterators, strict=True)
        case 'ignore':
            return zip(*iterators)
        case _:
            raise ValueError('Expected fill, strict, or ignore')

def roundrobin(*iterables):
    "Visit input iterables in a cycle until each is exhausted."
    # roundrobin('ABC', 'D', 'EF') → A D E B F C
    # Algorithm credited to George Sakkis
    iterators = map(iter, iterables)
    for num_active in range(len(iterables), 0, -1):
        iterators = cycle(islice(iterators, num_active))
        yield from map(next, iterators)

def partition(predicate, iterable):
    """Partition entries into false entries and true entries.

    If *predicate* is slow, consider wrapping it with functools.lru_cache().
    """
    # partition(is_odd, range(10)) → 0 2 4 6 8   and  1 3 5 7 9
    t1, t2 = tee(iterable)
    return filterfalse(predicate, t1), filter(predicate, t2)

def subslices(seq):
    "Return all contiguous non-empty subslices of a sequence."
    # subslices('ABCD') → A AB ABC ABCD B BC BCD C CD D
    slices = starmap(slice, combinations(range(len(seq) + 1), 2))
    return map(operator.getitem, repeat(seq), slices)

def iter_index(iterable, value, start=0, stop=None):
    "Return indices where a value occurs in a sequence or iterable."
    # iter_index('AABCADEAF', 'A') → 0 1 4 7
    seq_index = getattr(iterable, 'index', None)
    if seq_index is None:
        iterator = islice(iterable, start, stop)
        for i, element in enumerate(iterator, start):
            if element is value or element == value:
                yield i
    else:
        stop = len(iterable) if stop is None else stop
        i = start
        with contextlib.suppress(ValueError):
            while True:
                yield (i := seq_index(value, i, stop))
                i += 1

def iter_except(func, exception, first=None):
    "Convert a call-until-exception interface to an iterator interface."
    # iter_except(d.popitem, KeyError) → non-blocking dictionary iterator
    with contextlib.suppress(exception):
        if first is not None:
            yield first()
        while True:
            yield func()

Следующие рецепты имеют более математический характер:

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 sum_of_squares(iterable):
    "Add up the squares of the input values."
    # sum_of_squares([10, 20, 30]) → 1400
    return math.sumprod(*tee(iterable))

def reshape(matrix, cols):
    "Reshape a 2-D matrix to have a given number of columns."
    # reshape([(0, 1), (2, 3), (4, 5)], 3) →  (0, 1, 2), (3, 4, 5)
    return batched(chain.from_iterable(matrix), cols)

def transpose(matrix):
    "Swap the rows and columns of a 2-D matrix."
    # transpose([(1, 2, 3), (11, 22, 33)]) → (1, 11) (2, 22) (3, 33)
    return zip(*matrix, strict=True)

def matmul(m1, m2):
    "Multiply two matrices."
    # matmul([(7, 5), (3, 5)], [(2, 5), (7, 9)]) → (49, 80), (41, 60)
    n = len(m2[0])
    return batched(starmap(math.sumprod, product(m1, transpose(m2))), n)

def convolve(signal, kernel):
    """Discrete linear convolution of two iterables.
    Equivalent to polynomial multiplication.

    Convolutions are mathematically commutative; however, the inputs are
    evaluated differently.  The signal is consumed lazily and can be
    infinite. The kernel is fully consumed before the calculations begin.

    Article:  https://betterexplained.com/articles/intuitive-convolution/
    Video:    https://www.youtube.com/watch?v=KuXjwB4LzSA
    """
    # convolve([1, -1, -20], [1, -3]) → 1 -4 -17 60
    # convolve(data, [0.25, 0.25, 0.25, 0.25]) → Moving average (blur)
    # convolve(data, [1/2, 0, -1/2]) → 1st derivative estimate
    # convolve(data, [1, -2, 1]) → 2nd derivative estimate
    kernel = tuple(kernel)[::-1]
    n = len(kernel)
    padded_signal = chain(repeat(0, n-1), signal, repeat(0, n-1))
    windowed_signal = sliding_window(padded_signal, n)
    return map(math.sumprod, repeat(kernel), windowed_signal)

def polynomial_from_roots(roots):
    """Compute a polynomial's coefficients from its roots.

       (x - 5) (x + 4) (x - 3)  expands to:   x³ -4x² -17x + 60
    """
    # polynomial_from_roots([5, -4, 3]) → [1, -4, -17, 60]
    factors = zip(repeat(1), map(operator.neg, roots))
    return list(functools.reduce(convolve, factors, [1]))

def polynomial_eval(coefficients, x):
    """Evaluate a polynomial at a specific value.

    Computes with better numeric stability than Horner's method.
    """
    # Evaluate x³ -4x² -17x + 60 at x = 5
    # polynomial_eval([1, -4, -17, 60], x=5) → 0
    n = len(coefficients)
    if not n:
        return type(x)(0)
    powers = map(pow, repeat(x), reversed(range(n)))
    return math.sumprod(coefficients, powers)

def polynomial_derivative(coefficients):
    """Compute the first derivative of a polynomial.

       f(x)  =  x³ -4x² -17x + 60
       f'(x) = 3x² -8x  -17
    """
    # polynomial_derivative([1, -4, -17, 60]) → [3, -8, -17]
    n = len(coefficients)
    powers = reversed(range(1, n))
    return list(map(operator.mul, coefficients, powers))

def sieve(n):
    "Primes less than n."
    # sieve(30) → 2 3 5 7 11 13 17 19 23 29
    if n > 2:
        yield 2
    data = bytearray((0, 1)) * (n // 2)
    for p in iter_index(data, 1, start=3, stop=math.isqrt(n) + 1):
        data[p*p : n : p+p] = bytes(len(range(p*p, n, p+p)))
    yield from iter_index(data, 1, start=3)

def factor(n):
    "Prime factors of n."
    # factor(99) → 3 3 11
    # factor(1_000_000_000_000_007) → 47 59 360620266859
    # factor(1_000_000_000_000_403) → 1000000000000403
    for prime in sieve(math.isqrt(n) + 1):
        while not n % prime:
            yield prime
            n //= prime
            if n == 1:
                return
    if n > 1:
        yield n

def totient(n):
    "Count of natural numbers up to n that are coprime to n."
    # https://mathworld.wolfram.com/TotientFunction.html
    # totient(12) → 4 because len([1, 5, 7, 11]) == 4
    for prime in set(factor(n)):
        n -= n // prime
    return n