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

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

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

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

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

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

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, итерация продолжается до исчерпания итератора, если таковой имеется; в противном случае она останавливается в заданной позиции. В отличие от обычного среза, 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.permutations(iterable, r=None)

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

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

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

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

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

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() создал разделение, исходный итерируемый объект не должен использоваться нигде больше; в противном случае итерируемый объект может быть продвинут без уведомления объектов tee.

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

Этот итератор может потребовать значительного вспомогательного хранилища (в зависимости от того, сколько временных данных нужно хранить). В целом, если один итератор использует большинство или все данные до начала работы другого итератора, быстрее использовать 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 на Python Package Index:

pip install more-itertools

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

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 pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

def grouper(iterable, n, fillvalue=None):
    "Collect data into fixed-length chunks or blocks"
    # grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx"
    args = [iter(iterable)] * n
    return zip_longest(*args, fillvalue=fillvalue)

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