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

Функции Itertool¶

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

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

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

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

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

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

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() для текущего произведения. Амортизационные таблицы могут быть построены путем накопления процентов и применения платежей. Амортизационные таблицы первого порядка recurrence relations можно моделировать, задавая начальное значение в итерабле и используя только накопленный итог в аргументе func:

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

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

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

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

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

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

Изменено в версии 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. Таким образом, если входная итерабельная отсортирована, то кортежи комбинаций будут выдаваться в отсортированном порядке.

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

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

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. Таким образом, если входная итерабельная отсортирована, то кортежи комбинаций будут выдаваться в отсортированном порядке.

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

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

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: Добавлен аргумент шаг и разрешены нецелые аргументы.

itertools.cycle(iterable)¶

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

def cycle(iterable):
    # cycle('ABCD') --> A B C D A B C D A B C D ...
    saved = []
    for element in iterable:
        yield element
        saved.append(element)
    while saved:
        for element in saved:
              yield element

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

itertools.dropwhile(predicate, iterable)¶

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

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

itertools.filterfalse(predicate, iterable)¶

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

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

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

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

class groupby:
    # [k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B
    # [list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D
    def __init__(self, iterable, key=None):
        if key is None:
            key = lambda x: x
        self.keyfunc = key
        self.it = iter(iterable)
        self.tgtkey = self.currkey = self.currvalue = object()
    def __iter__(self):
        return self
    def __next__(self):
        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 ненулевое, то элементы из итератора пропускаются, пока не будет достигнуто начало. После этого элементы возвращаются последовательно, если только step не установлен больше единицы, что приводит к пропуску элементов. Если stop равен None, то итерация продолжается до тех пор, пока итератор не будет исчерпан, если он вообще исчерпан; в противном случае итератор останавливается на указанной позиции. В отличие от обычной нарезки, islice() не поддерживает отрицательные значения для start, stop или step. Может использоваться для извлечения связанных полей из данных, внутренняя структура которых была сглажена (например, в многострочном отчете поле имени может быть указано в каждой третьей строке). Примерно эквивалентно:

def islice(iterable, *args):
    # islice('ABCDEFG', 2) --> A B
    # islice('ABCDEFG', 2, 4) --> C D
    # islice('ABCDEFG', 2, None) --> C D E F G
    # islice('ABCDEFG', 0, None, 2) --> A C E G
    s = slice(*args)
    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

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

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 и генерируются все возможные полноразмерные перестановки.

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

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

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

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

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

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

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

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

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

itertools.starmap(function, iterable)¶

Создайте итератор, который вычисляет функцию, используя аргументы, полученные из итерируемой таблицы. Используется вместо map(), когда параметры аргументов уже сгруппированы в кортежи из одной итерируемой (данные были «предварительно упакованы»). Различие между map() и starmap() параллельно различию между function(a,b) и function(*c). Примерно эквивалентно:

def starmap(function, iterable):
    # starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000
    for args in iterable:
        yield function(*args)

itertools.takewhile(predicate, iterable)¶

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

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

itertools.tee(iterable, n=2)¶

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

Следующий код 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 не являются потокобезопасными. Может возникнуть ошибка RuntimeError при одновременном использовании итераторов, возвращаемых одним и тем же вызовом tee(), даже если исходный 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()). Если не указано, fillvalue по умолчанию равно None.

Рецепты Itertools¶

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

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

pip install more-itertools

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

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

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

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 pad_none(iterable):
    """Returns the sequence elements and then returns None indefinitely.

    Useful for emulating the behavior of the built-in map() function.
    """
    return chain(iterable, repeat(None))

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

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

def 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 sum(map(operator.mul, kernel, window))

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 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 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()
    seen_add = seen.add
    if key is None:
        for element in filterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

def unique_justseen(iterable, key=None):
    "List unique elements, preserving order. Remember only the element just seen."
    # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B
    # unique_justseen('ABBCcAD', str.lower) --> A B C A D
    return map(next, map(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 random_product(*args, repeat=1):
    "Random selection from itertools.product(*args, **kwds)"
    pools = [tuple(pool) for pool in args] * repeat
    return tuple(map(random.choice, pools))

def random_permutation(iterable, r=None):
    "Random selection from itertools.permutations(iterable, r)"
    pool = tuple(iterable)
    r = len(pool) if r is None else r
    return tuple(random.sample(pool, r))

def random_combination(iterable, r):
    "Random selection from itertools.combinations(iterable, r)"
    pool = tuple(iterable)
    n = len(pool)
    indices = sorted(random.sample(range(n), r))
    return tuple(pool[i] for i in indices)

def random_combination_with_replacement(iterable, r):
    "Random selection from itertools.combinations_with_replacement(iterable, r)"
    pool = tuple(iterable)
    n = len(pool)
    indices = sorted(random.choices(range(n), k=r))
    return tuple(pool[i] for i in indices)

def nth_combination(iterable, r, index):
    "Equivalent to list(combinations(iterable, r))[index]"
    pool = tuple(iterable)
    n = len(pool)
    if r < 0 or r > n:
        raise ValueError
    c = 1
    k = min(r, n-r)
    for i in range(1, k+1):
        c = c * (n - k + i) // i
    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)