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

Чтобы вычислить минимальное значение, установите функцию в 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, *, strict=False)

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

Если strict равно true, будет вызвано исключение ValueError, если последняя группа короче 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, *, strict=False):
    # 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)):
        if strict and len(batch) != n:
            raise ValueError('batched(): incomplete batch')
        yield batch

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

Изменено в версии 3.13: Добавлен параметр strict.

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 из элементов входного итерируемого объекта.

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

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

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

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

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 из элементов входного итерируемого объекта, разрешая повторяющиеся элементы более одного раза.

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

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

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

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

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 истинно, а затем возвращает каждый элемент. Приблизительно эквивалентно:

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

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

Если вход представляет собой итератор, то полное потребление islice продвигает входной итератор на max(start, stop) шагов независимо от значения step.

itertools.pairwise(iterable)

Возвращает последовательные перекрывающиеся пары, взятые из входного 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 элементов из iterable.

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

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

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

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

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

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

    if repeat < 0:
        raise ValueError('repeat argument cannot be negative')
    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])

Создает итератор, который возвращает object снова и снова. Продолжается бесконечно, если не указан аргумент 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)

Создаёт итератор, который вычисляет 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)

Создаёт итератор, который возвращает элементы из iterable до тех пор, пока predicate истинно. Примерно эквивалентно:

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):
    if n < 0:
        raise ValueError
    if n == 0:
        return ()
    iterator = _tee(iterable)
    result = [iterator]
    for _ in range(n - 1):
        result.append(_tee(iterator))
    return tuple(result)

class _tee:

    def __init__(self, iterable):
        it = iter(iterable)
        if isinstance(it, _tee):
            self.iterator = it.iterator
            self.link = it.link
        else:
            self.iterator = it
            self.link = [None, None]

    def __iter__(self):
        return self

    def __next__(self):
        link = self.link
        if link[1] is None:
            link[0] = next(self.iterator)
            link[1] = [None, None]
        value, self.link = link
        return value

Когда входной iterable уже является итератором tee, все члены возвращаемого кортежа конструируются так, как будто они были произведены вызовом upstream tee(). Эта «уплотняющая» операция позволяет вложенным вызовам tee() совместно использовать одну и ту же подлежащую цепочку данных и иметь один шаг обновления вместо цепочки вызовов.

Свойство уплотнения делает итераторы tee эффективно «просматриваемыми»:

def lookahead(tee_iterator):
     "Return the next value without moving the input forward"
     [forked_iterator] = tee(tee_iterator, 1)
     return next(forked_iterator)

>>> iterator = iter('abcdef')
>>> [iterator] = tee(iterator, 1)   # Make the input peekable
>>> next(iterator)                  # Move the iterator forward
'a'
>>> lookahead(iterator)             # Check next value
'b'
>>> next(iterator)                  # Continue moving forward
'b'

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

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

itertools.zip_longest(*iterables, fillvalue=None)

Создает итератор, который агрегирует элементы из каждого из iterable.

Если итерируемые объекты имеют неравную длину, отсутствующие значения заполняются 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().

Второстепенная цель рецептов — служить инкубатором. Инструменты itertools 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 loops(n):
    "Loop n times. Like range(n) but without creating integers."
    # for _ in loops(100): ...
    return repeat(None, 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 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, strict=True)

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 is_prime(n):
    "Return True if n is prime."
    # is_prime(1_000_000_000_000_403) → True
    return n > 1 and all(n % p for p in sieve(math.isqrt(n) + 1))

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