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

Функции Itertools¶

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

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

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

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

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

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

def accumulate(iterable, func=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
    it = iter(iterable)
    total = initial
    if initial is None:
        try:
            total = next(it)
        except StopIteration:
            return
    yield total
    for element in it:
        total = func(total, element)
        yield total

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

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

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

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

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

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

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

itertools.chain(*iterables)¶

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

def chain(*iterables):
    # chain('ABC', 'DEF') --> A B C D E F
    for it in iterables:
        for element in it:
            yield element

classmethod chain.from_iterable(iterable)¶

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

def from_iterable(iterables):
    # chain.from_iterable(['ABC', 'DEF']) --> A B C D E F
    for it in iterables:
        for element in it:
            yield element

itertools.combinations(iterable, r)¶

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

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

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

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

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

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

def combinations(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    for indices in permutations(range(n), r):
        if sorted(indices) == list(indices):
            yield tuple(pool[i] for i in indices)

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

itertools.combinations_with_replacement(iterable, r)¶

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

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

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

def combinations_with_replacement(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    for indices in product(range(n), repeat=r):
        if sorted(indices) == list(indices):
            yield tuple(pool[i] for i in indices)

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

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

itertools.compress(data, selectors)¶

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

def compress(data, selectors):
    # compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F
    return (d for d, s in zip(data, selectors) if s)

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

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

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

def count(start=0, step=1):
    # count(10) --> 10 11 12 13 14 ...
    # count(2.5, 0.5) --> 2.5 3.0 3.5 ...
    n = start
    while True:
        yield n
        n += step

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

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

itertools.cycle(iterable)¶

Создайте итератор, возвращающий элементы из 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 до тех пор, пока предикат имеет значение true; затем возвращает каждый элемент. Обратите внимание, что итератор не выдает никаких выходных данных, пока предикат не станет false, поэтому время запуска может быть длительным. Примерно эквивалентно:

def dropwhile(predicate, iterable):
    # dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1
    iterable = iter(iterable)
    for x in iterable:
        if not predicate(x):
            yield x
            break
    for x in iterable:
        yield x

itertools.filterfalse(predicate, iterable)¶

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

def filterfalse(predicate, iterable):
    # filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8
    if predicate is None:
        predicate = bool
    for x in iterable:
        if not predicate(x):
            yield x

itertools.groupby(iterable, key=None)¶

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

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

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

groups = []
uniquekeys = []
data = sorted(data, key=keyfunc)
for k, g in groupby(data, keyfunc):
    groups.append(list(g))      # Store group iterator as a list
    uniquekeys.append(k)

groupby() примерно эквивалентно:

class groupby:
    # [k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B
    # [list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D

    def __init__(self, iterable, key=None):
        if key is None:
            key = lambda x: x
        self.keyfunc = key
        self.it = iter(iterable)
        self.tgtkey = self.currkey = self.currvalue = object()

    def __iter__(self):
        return self

    def __next__(self):
        self.id = object()
        while self.currkey == self.tgtkey:
            self.currvalue = next(self.it)    # Exit on StopIteration
            self.currkey = self.keyfunc(self.currvalue)
        self.tgtkey = self.currkey
        return (self.currkey, self._grouper(self.tgtkey, self.id))

    def _grouper(self, tgtkey, id):
        while self.id is id and self.currkey == tgtkey:
            yield self.currvalue
            try:
                self.currvalue = next(self.it)
            except StopIteration:
                return
            self.currkey = self.keyfunc(self.currvalue)

itertools.islice(iterable, stop)¶

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

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

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

В отличие от обычной нарезки, islice() не поддерживает отрицательные значения для start, stop или step. Может использоваться для извлечения связанных полей из данных, внутренняя структура которых была сглажена (например, в многострочном отчете поле имени может быть указано в каждой третьей строке).

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

def islice(iterable, *args):
    # islice('ABCDEFG', 2) --> A B
    # islice('ABCDEFG', 2, 4) --> C D
    # islice('ABCDEFG', 2, None) --> C D E F G
    # islice('ABCDEFG', 0, None, 2) --> A C E G
    s = slice(*args)
    start, stop, step = s.start or 0, s.stop or sys.maxsize, s.step or 1
    it = iter(range(start, stop, step))
    try:
        nexti = next(it)
    except StopIteration:
        # Consume *iterable* up to the *start* position.
        for i, element in zip(range(start), iterable):
            pass
        return
    try:
        for i, element in enumerate(iterable):
            if i == nexti:
                yield element
                nexti = next(it)
    except StopIteration:
        # Consume to *stop*.
        for i, element in zip(range(i + 1, stop), iterable):
            pass

itertools.pairwise(iterable)¶

Возвращает последовательные перекрывающиеся пары, взятые из входных данных iterable.

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

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

def pairwise(iterable):
    # pairwise('ABCDEFG') --> AB BC CD DE EF FG
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

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

itertools.permutations(iterable, r=None)¶

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

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

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

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

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

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

itertools.product(*iterables, repeat=1)¶

Декартово произведение входных итераций.

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

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

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

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

def product(*args, repeat=1):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

Перед запуском 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)¶

Создайте итератор, который вычисляет функцию, используя аргументы, полученные из iterable. Используется вместо map(), когда параметры аргумента уже сгруппированы в кортежи из одной iterable (когда данные были «предварительно сжаты»).

Разница между 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, если предикат имеет значение true. Примерно эквивалентно:

def takewhile(predicate, iterable):
    # takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4
    for x in iterable:
        if predicate(x):
            yield x
        else:
            break

itertools.tee(iterable, n=2)¶

Возвращает n независимых итераторов из одной итерируемой переменной.

Следующий код на Python помогает объяснить, что делает tee (хотя фактическая реализация более сложна и использует только одну базовую очередь FIFO).:

def tee(iterable, n=2):
    it = iter(iterable)
    deques = [collections.deque() for i in range(n)]
    def gen(mydeque):
        while True:
            if not mydeque:             # when the local deque is empty
                try:
                    newval = next(it)   # fetch a new value and
                except StopIteration:
                    return
                for d in deques:        # load it to all the deques
                    d.append(newval)
            yield mydeque.popleft()
    return tuple(gen(d) for d in deques)

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

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

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

itertools.zip_longest(*iterables, fillvalue=None)¶

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

def zip_longest(*args, fillvalue=None):
    # zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-
    iterators = [iter(it) for it in args]
    num_active = len(iterators)
    if not num_active:
        return
    while True:
        values = []
        for i, it in enumerate(iterators):
            try:
                value = next(it)
            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()). Если не указано, значение заполнения по умолчанию равно None.

Рецепты Itertools¶

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

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

Вторичное назначение recipes - служить в качестве инкубатора. accumulate(), compress(), и pairwise() itertools изначально создавались как recipes. В настоящее время рецепт iter_index() тестируется, чтобы выяснить, оправдает ли он себя.

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

python -m pip install more-itertools

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

import collections
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 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:
        # feed the entire iterator into a zero-length deque
        collections.deque(iterator, maxlen=0)
    else:
        # advance to the empty slice starting at position n
        next(islice(iterator, n, n), None)

def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    return next(islice(iterable, n, None), default)

def all_equal(iterable):
    "Returns True if all the elements are equal to each other"
    g = groupby(iterable)
    return next(g, True) and not next(g, False)

def quantify(iterable, pred=bool):
    "Count how many times the predicate is True"
    return sum(map(pred, iterable))

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

def batched(iterable, n):
    "Batch data into tuples of length n. The last batch may be shorter."
    # batched('ABCDEFG', 3) --> ABC DEF G
    if n < 1:
        raise ValueError('n must be at least one')
    it = iter(iterable)
    while batch := tuple(islice(it, n)):
        yield batch

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
    args = [iter(iterable)] * n
    if incomplete == 'fill':
        return zip_longest(*args, fillvalue=fillvalue)
    if incomplete == 'strict':
        return zip(*args, strict=True)
    if incomplete == 'ignore':
        return zip(*args)
    else:
        raise ValueError('Expected fill, strict, or ignore')

def sumprod(vec1, vec2):
    "Compute a sum of products."
    return sum(starmap(operator.mul, zip(vec1, vec2, strict=True)))

def sum_of_squares(it):
    "Add up the squares of the input values."
    # sum_of_squares([10, 20, 30]) -> 1400
    return sumprod(*tee(it))

def transpose(it):
    "Swap the rows and columns of the input."
    # transpose([(1, 2, 3), (11, 22, 33)]) --> (1, 11) (2, 22) (3, 33)
    return zip(*it, 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):
    # See:  https://betterexplained.com/articles/intuitive-convolution/
    # convolve(data, [0.25, 0.25, 0.25, 0.25]) --> Moving average (blur)
    # convolve(data, [1, -1]) --> 1st finite difference (1st derivative)
    # convolve(data, [1, -2, 1]) --> 2nd finite difference (2nd derivative)
    kernel = tuple(kernel)[::-1]
    n = len(kernel)
    window = collections.deque([0], maxlen=n) * n
    for x in chain(signal, repeat(0, n-1)):
        window.append(x)
        yield sumprod(kernel, window)

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]
    expansion = [1]
    for r in roots:
        expansion = convolve(expansion, (1, -r))
    return list(expansion)

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 = 2.5
    # polynomial_eval([1, -4, -17, 60], x=2.5) --> 8.125
    n = len(coefficients)
    if n == 0:
        return x * 0  # coerce zero to the type of x
    powers = map(pow, repeat(x), reversed(range(n)))
    return sumprod(coefficients, powers)

def iter_index(iterable, value, start=0):
    "Return indices where a value occurs in a sequence or iterable."
    # iter_index('AABCADEAF', 'A') --> 0 1 4 7
    try:
        seq_index = iterable.index
    except AttributeError:
        # Slow path for general iterables
        it = islice(iterable, start, None)
        i = start - 1
        try:
            while True:
                yield (i := i + operator.indexOf(it, value) + 1)
        except ValueError:
            pass
    else:
        # Fast path for sequences
        i = start - 1
        try:
            while True:
                yield (i := seq_index(value, i+1))
        except ValueError:
            pass

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

def factor(n):
    "Prime factors of n."
    # factor(99) --> 3 3 11
    for prime in sieve(math.isqrt(n) + 1):
        while True:
            quotient, remainder = divmod(n, prime)
            if remainder:
                break
            yield prime
            n = quotient
            if n == 1:
                return
    if n > 1:
        yield n

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

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

    Example:  repeatfunc(random.random)
    """
    if times is None:
        return starmap(func, repeat(args))
    return starmap(func, repeat(args, times))

def triplewise(iterable):
    "Return overlapping triplets from an iterable"
    # triplewise('ABCDEFG') --> ABC BCD CDE DEF EFG
    for (a, _), (b, c) in pairwise(pairwise(iterable)):
        yield a, b, c

def sliding_window(iterable, n):
    # sliding_window('ABCDEFG', 4) --> ABCD BCDE CDEF DEFG
    it = iter(iterable)
    window = collections.deque(islice(it, n), maxlen=n)
    if len(window) == n:
        yield tuple(window)
    for x in it:
        window.append(x)
        yield tuple(window)

def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    # Recipe credited to George Sakkis
    num_active = len(iterables)
    nexts = cycle(iter(it).__next__ for it in iterables)
    while num_active:
        try:
            for next in nexts:
                yield next()
        except StopIteration:
            # Remove the iterator we just exhausted from the cycle.
            num_active -= 1
            nexts = cycle(islice(nexts, num_active))

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

def before_and_after(predicate, it):
    """ Variant of takewhile() that allows complete
        access to the remainder of the iterator.

        >>> it = iter('ABCdEfGhI')
        >>> all_upper, remainder = before_and_after(str.isupper, it)
        >>> ''.join(all_upper)
        'ABC'
        >>> ''.join(remainder)     # takewhile() would lose the 'd'
        'dEfGhI'

        Note that the first iterator must be fully
        consumed before the second iterator can
        generate valid results.
    """
    it = iter(it)
    transition = []
    def true_iterator():
        for elem in it:
            if predicate(elem):
                yield elem
            else:
                transition.append(elem)
                return
    def remainder_iterator():
        yield from transition
        yield from it
    return true_iterator(), remainder_iterator()

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 powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBcCAD', str.lower) --> A B c D
    seen = set()
    if key is None:
        for element in filterfalse(seen.__contains__, iterable):
            seen.add(element)
            yield element
        # For order preserving deduplication,
        # a faster but non-lazy solution is:
        #     yield from dict.fromkeys(iterable)
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen.add(k)
                yield element
        # For use cases that allow the last matching element to be returned,
        # a faster but non-lazy solution is:
        #      t1, t2 = tee(iterable)
        #      yield from dict(zip(map(key, t1), t2)).values()

def unique_justseen(iterable, key=None):
    "List unique elements, preserving order. Remember only the element just seen."
    # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B
    # unique_justseen('ABBcCAD', str.lower) --> A B c A D
    return map(next, map(operator.itemgetter(1), groupby(iterable, key)))

def iter_except(func, exception, first=None):
    """ Call a function repeatedly until an exception is raised.

    Converts a call-until-exception interface to an iterator interface.
    Like builtins.iter(func, sentinel) but uses an exception instead
    of a sentinel to end the loop.

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

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

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

    If no true value is found, returns *default*

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

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

def nth_combination(iterable, r, index):
    "Equivalent to list(combinations(iterable, r))[index]"
    pool = tuple(iterable)
    n = len(pool)
    c = math.comb(n, r)
    if index < 0:
        index += c
    if index < 0 or index >= c:
        raise IndexError
    result = []
    while r:
        c, n, r = c*r//n, n-1, r-1
        while index >= c:
            index -= c
            c, n = c*(n-r)//n, n-1
        result.append(pool[-1-n])
    return tuple(result)