itertools – Функции, создающие итераторы для эффективного перебора¶itertools – Functions creating iterators for efficient looping

Функции itertools¶Itertool Functions

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

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

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

Если function не указана, по умолчанию используется сложение. Function должна принимать два аргумента: накопленное значение и очередной элемент из iterable.

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

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

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(). Для текущего максимума – function max(). Для текущего произведения – function operator.mul(). Для построения таблицы амортизации накопите проценты и примените платежи:

>>> data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8]
>>> list(accumulate(data, max))              # текущий максимум
[3, 4, 6, 6, 6, 9, 9, 9, 9, 9]
>>> list(accumulate(data, operator.mul))     # текущее произведение
[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)¶

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

Если strict равен True, будет вызвано исключение ValueError, если последняя группа короче n.

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

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

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

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

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 истинен. Останавливается, когда исчерпан либо 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 и сохраняет копию каждого. Когда 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

Этот инструмент может потребовать значительного объёма дополнительной памяти (в зависимости от длины iterable).

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

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

Make an iterator that returns consecutive keys and groups from the iterable. The key is a function computing a key value for each element. If not specified or is None, key defaults to an identity function and returns the element unchanged. Generally, the iterable needs to already be sorted on the same key function.

Работа 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))      # Сохранить групповой итератор как список
    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.

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

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

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

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

Если входной итерируемый объект уже является объектом-итератором 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)   # Сделать входные данные просматриваемыми (peekable)
>>> next(iterator)                  # Продвинуть итератор вперед
'a'
>>> lookahead(iterator)             # Проверить следующее значение
'b'
>>> next(iterator)                  # Продолжить движение вперед
'b'

Итераторы 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 Recipes

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

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

Второстепенная цель рецептов – служить инкубатором. accumulate(), compress() и pairwise() изначально были рецептами. В настоящее время рецепты sliding_window(), derangements() и sieve() тестируются, чтобы проверить, оправдают ли они себя.

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

python -m pip install more-itertools

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

from itertools import (accumulate, batched, chain, combinations, compress,
     count, cycle, filterfalse, groupby, islice, permutations, product,
     repeat, starmap, tee, zip_longest)
from collections import Counter, deque
from contextlib import suppress
from functools import reduce
from heapq import heappush, heappushpop, heappush_max, heappushpop_max
from math import comb, isqrt, prod, sumprod
from operator import getitem, is_not, itemgetter, mul, neg, truediv


# ==== Базовые однострочники ====

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 repeatfunc(function, times=None, *args):
    "Repeat calls to a function with specified arguments."
    if times is None:
        return starmap(function, repeat(args))
    return starmap(function, 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(deque(iterable, maxlen=n))

def consume(iterator, n=None):
    "Advance the iterator n-steps ahead. If n is None, consume entirely."
    # Используйте функции, потребляющие итераторы на скорости C.
    if n is None:
        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(itemgetter(0), groupby(iterable))
    return map(next, map(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]
    sequenced = sorted(iterable, key=key, reverse=reverse)
    return unique_justseen(sequenced, key=key)

def sliding_window(iterable, n):
    "Collect data into overlapping fixed-length chunks or blocks."
    # sliding_window('ABCDEFG', 3) → ABC BCD CDE DEF EFG
    iterator = iter(iterable)
    window = 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
    # Алгоритм Джорджа Саккиса
    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(getitem, repeat(seq), slices)

def derangements(iterable, r=None):
    "Produce r length permutations without fixed points."
    # derangements('ABCD') → BADC BCDA BDAC CADB CDAB CDBA DABC DCAB DCBA
    # Алгоритм Стефана Похманна
    seq = tuple(iterable)
    pos = tuple(range(len(seq)))
    have_moved = map(map, repeat(is_not), repeat(pos), permutations(pos, r=r))
    valid_derangements = map(all, have_moved)
    return compress(permutations(seq, r=r), valid_derangements)

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 suppress(ValueError):
            while True:
                yield (i := seq_index(value, i, stop))
                i += 1

def iter_except(function, exception, first=None):
    "Convert a call-until-exception interface to an iterator interface."
    # iter_except(d.popitem, KeyError) → неблокирующий итератор словаря
    with suppress(exception):
        if first is not None:
            yield first()
        while True:
            yield function()


# ==== Математические операции ====

def multinomial(*counts):
    "Number of distinct arrangements of a multiset."
    # Counter('abracadabra').values() → 5 2 2 1 1
    # multinomial(5, 2, 2, 1, 1) → 83160
    return prod(map(comb, accumulate(counts), counts))

def powerset(iterable):
    "Subsequences of the iterable from shortest to longest."
    # 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 sumprod(*tee(iterable))


# ==== Операции с матрицами ====

def reshape(matrix, columns):
    "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), columns, 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(sumprod, product(m1, transpose(m2))), n)


# ==== Арифметика многочленов ====

def convolve(signal, kernel):
    """Дискретная линейная свёртка двух итерируемых объектов.
    Эквивалентно умножению многочленов.

    Свёртки математически коммутативны; однако входные данные
    вычисляются по-разному.  Сигнал потребляется лениво и может быть
    бесконечным. Ядро полностью потребляется до начала вычислений.

    Статья:  https://betterexplained.com/articles/intuitive-convolution/
    Видео:    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]) → Скользящее среднее (размытие)
    # convolve(data, [1/2, 0, -1/2]) → Оценка первой производной
    # convolve(data, [1, -2, 1]) → Оценка второй производной
    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(sumprod, repeat(kernel), windowed_signal)

def polynomial_from_roots(roots):
    """Вычисляет коэффициенты многочлена по его корням.

       (x - 5) (x + 4) (x - 3)  раскрывается в:   x³ -4x² -17x + 60
    """
    # polynomial_from_roots([5, -4, 3]) → [1, -4, -17, 60]
    factors = zip(repeat(1), map(neg, roots))
    return list(reduce(convolve, factors, [1]))

def polynomial_eval(coefficients, x):
    """Вычисляет значение многочлена в заданной точке.

    Вычисляет с лучшей численной устойчивостью, чем метод Горнера.
    """
    # Вычислить x³ -4x² -17x + 60 при 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 sumprod(coefficients, powers)

def polynomial_derivative(coefficients):
    """Вычисляет первую производную многочлена.

       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(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=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(isqrt(n) + 1):
        while not n % prime:
            yield prime
            n //= prime
            if n == 1:
                return
    if n > 1:
        yield n

def is_prime(n):
    "Return True if n is prime."
    # is_prime(1_000_000_000_000_403) → True
    return n > 1 and next(factor(n)) == 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 потому что len([1, 5, 7, 11]) == 4
    for prime in set(factor(n)):
        n -= n // prime
    return n


# ==== Скользящие статистики ====

def running_mean(iterable):
    "Average of values seen so far."
    # running_mean([37, 33, 38, 28]) → 37 35 36 34
    return map(truediv, accumulate(iterable), count(1))

def running_min(iterable):
    "Smallest of values seen so far."
    # running_min([37, 33, 38, 28]) → 37 33 33 28
    return accumulate(iterable, func=min)

def running_max(iterable):
    "Largest of values seen so far."
    # running_max([37, 33, 38, 28]) → 37 37 38 38
    return accumulate(iterable, func=max)

def running_median(iterable):
    "Median of values seen so far."
    # running_median([37, 33, 38, 28]) → 37 35 37 35
    read = iter(iterable).__next__
    lo = []  # максимальная куча
    hi = []  # мин-куча того же размера, что и lo, или на единицу меньше
    with suppress(StopIteration):
        while True:
            heappush_max(lo, heappushpop(hi, read()))
            yield lo[0]
            heappush(hi, heappushpop_max(lo, read()))
            yield (lo[0] + hi[0]) / 2

def running_statistics(iterable):
    "Aggregate statistics for values seen so far."
    # Создать кортежи: (size, minimum, median, maximum, mean)
    t0, t1, t2, t3 = tee(iterable, 4)
    return zip(
        count(1),
        running_min(t0),
        running_median(t1),
        running_max(t2),
        running_mean(t3),
    )