itertools ---为有效循环创建迭代器的函数


此模块实现了许多 iterator 受APL、Haskell和SML构造启发的构建块。每一个都以适合于Python的形式进行了重铸。

该模块标准化了一组快速、内存高效的核心工具,这些工具本身或组合使用都很有用。它们一起形成了一个“迭代器代数”,从而可以在纯Python中简洁高效地构造专用工具。

例如,SML提供了一个制表工具: tabulate(f) 它产生一个序列 f(0), f(1), ... . 在python中,通过结合使用 map()count() 形成 map(f, count()) .

这些工具及其内置对应工具也可以很好地与 operator 模块。例如,乘法运算符可以跨两个向量映射,以形成有效的点积: sum(map(operator.mul, vector1, vector2)) .

无限迭代器:

迭代器

参数

结果

例子

count()

开始, [step]

开始,开始+步骤,开始+2*步骤,…

count(10) --> 10 11 12 13 14 ...

cycle()

P0,P1,…plast,p0,p1,…

cycle('ABCD') --> A B C D A B C D ...

repeat()

电子 [,n]

Elem,Elem,Elem,…无休止或最多N次

repeat(10, 3) --> 10 10 10

以最短输入序列终止的迭代器:

迭代器

参数

结果

例子

accumulate()

磷 [FUNC]

p0,p0+p1,p0+p1+p2,…

accumulate([1,2,3,4,5]) --> 1 3 6 10 15

chain()

p,q,…

P0,P1,…塑料,Q0,Q1,…

chain('ABC', 'DEF') --> A B C D E F

chain.from_iterable()

可迭代的

P0,P1,…塑料,Q0,Q1,…

chain.from_iterable(['ABC', 'DEF']) --> A B C D E F

compress()

数据选择器

(d[0] if s[0]), (d[1] if s[1]), ...

compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F

dropwhile()

塞德

SEQ [n] SEQ [n+1] ,当pred失败时开始

dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1

filterfalse()

塞德

pred(elem)为假的seq元素

filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8

groupby()

可迭代的 [键]

按键(v)值分组的子迭代器

islice()

塞克 [开始,] 停止 [,步骤]

序列中的元素 [开始:停止:步骤]

islice('ABCDEFG', 2, None) --> C D E F G

pairwise()

可迭代的

(P [0] ,p [1] )、(第 [1] ,p [2] )

pairwise('ABCDEFG') --> AB BC CD DE EF FG

starmap()

FECC,SEQ

FUNC * SEQ [0] (FUNC) * SEQ [1] )

starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000

takewhile()

塞德

SEQ [0] SEQ [1] ,直到pred失败

takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4

tee()

它,n

IT1,IT2,…ITN将一个迭代器拆分为N

zip_longest()

p,q,…

(p[0], q[0]), (p[1], q[1]), ...

zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-

组合迭代器:

迭代器

参数

结果

product()

p,q,… [repeat=1]

笛卡尔积,等价于嵌套for循环

permutations()

磷 [, r]

r-长度元组,所有可能的顺序,没有重复的元素

combinations()

P,R

r-长度元组,按排序顺序,无重复元素

combinations_with_replacement()

P,R

r-长度元组,按顺序排列,具有重复的元素

实例

结果

product('ABCD', repeat=2)

AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD

permutations('ABCD', 2)

AB AC AD BA BC BD CA CB CD DA DB DC

combinations('ABCD', 2)

AB AC AD BC BD CD

combinations_with_replacement('ABCD', 2)

AA AB AC AD BB BC BD CC CD DD

ITertool函数

下面的模块函数所有构造和返回迭代器。有些提供无限长的流,因此它们只能由截断流的函数或循环访问。

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

生成一个迭代器,返回累积和或其他二进制函数的累积结果(通过可选的 func 参数)。

如果 func 提供了,它应该是两个参数的函数。输入元素 可迭代的 可以是任何可以作为参数接受的类型 func . (例如,使用默认的加法运算,元素可以是任何可加类型,包括 DecimalFraction

通常,输出的元素数与输入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() 对于正在运行的产品。摊销表可以通过累计利息和应用付款来构建。一阶 recurrence relations 可以通过提供ITerable中的初始值并仅使用 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)

创建一个迭代器,它从第一个iterable返回元素,直到它耗尽,然后继续到下一个iterable,直到所有iterable都耗尽。用于将连续序列作为单个序列处理。大致相当于:

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() . 从一个延迟计算的iterable参数获取链接输入。大致相当于:

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 输入元素的长度子序列 可迭代的 .

组合元组根据输入的顺序以字典顺序发出 可迭代的 . 所以,如果输入 可迭代的 如果排序,组合元组将按排序顺序生成。

元素根据其位置而不是其值被视为唯一的。因此,如果输入元素是唯一的,那么每个组合中都不会有重复值。

大致相当于:

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 输入元素的长度子序列 可迭代的 允许单个元素重复多次。

组合元组根据输入的顺序以字典顺序发出 可迭代的 . 所以,如果输入 可迭代的 如果排序,组合元组将按排序顺序生成。

元素根据其位置而不是其值被视为唯一的。因此,如果输入元素是唯一的,生成的组合也将是唯一的。

大致相当于:

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 . 当 dataselectors Iterables已经精疲力竭了。大致相当于:

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)

生成一个迭代器,返回以数字开头的等间距值 开始 . 常被用作 map() 生成连续的数据点。也用于 zip() 添加序列号。大致相当于:

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

用浮点数计数时,有时可以通过替换乘法代码(如: (start + step * i for i in count()) .

在 3.1 版更改: 补充 step 参数和允许的非整数参数。

itertools.cycle(iterable)

创建一个从iterable返回元素的迭代器,并保存每个元素的副本。当iterable用完时,从保存的副本返回元素。无限重复。大致相当于:

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

注意,工具包的这个成员可能需要大量的辅助存储(取决于iterable的长度)。

itertools.dropwhile(predicate, iterable)

生成一个迭代器,只要谓词为真,就从iterable中删除元素;然后返回每个元素。注意,迭代器不产生 any 输出,直到谓词第一次变为假,所以它可能有很长的启动时间。大致相当于:

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)

生成一个迭代器,该迭代器从 可迭代的 . 这个 key 是为每个元素计算键值的函数。如果未指定或 Nonekey 默认为标识函数,并返回未更改的元素。通常,iterable需要已经按照相同的键函数排序。

操作 groupby() 类似于 uniq 在Unix中过滤。每次键函数的值改变时,它都会生成一个中断或新组(这就是为什么通常需要使用相同的键函数对数据进行排序)。该行为不同于SQL的组,通过该组聚合公共元素,而不管它们的输入顺序如何。

返回的组本身是与共享基础ITerable的迭代器 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])

生成一个从iterable返回所选元素的迭代器。如果 开始 为非零,则跳过iterable中的元素,直到到达start。之后,元素将连续返回,除非 step 设置的值高于导致跳过项的值。如果 stopNone ,然后迭代继续,直到迭代器耗尽为止(如果有的话);否则,它将在指定的位置停止。与常规切片不同, islice() 不支持负值 开始stopstep . 可用于从内部结构已展平的数据中提取相关字段(例如,多行报表可以每隔三行列出一个名称字段)。大致相当于:

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

如果 开始None ,然后迭代从零开始。如果 stepNone ,则步骤默认为1。

itertools.pairwise(iterable)

返回从输入获取的连续重叠对 可迭代的

输出迭代器中的2元组的数量将比输入的数量少1。如果输入迭代值少于两个,则为空。

大致相当于:

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

输入iterables的笛卡尔积。

大致相当于生成器表达式中的嵌套for循环。例如, product(A, B) 返回与相同的 ((x,y) for x in A for y in B) .

嵌套循环像里程表一样循环,在每次迭代中都有最右边的元素前进。这个模式创建一个词典排序,这样,如果输入的iterables被排序,则产品元组将按排序顺序发出。

要用ITerable本身计算ITerable的积,请用可选的 重复 关键字参数。例如, 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 一遍又一遍。无限期运行,除非 参数已指定。用作参数 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

常用于 重复 是向 mapzip ::

>>> 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返回元素。大致相当于:

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 来自单个iterable的独立迭代器。

下面的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() 打电话,即使是原件 可迭代的 是线程安全的。

此itertool可能需要大量的辅助存储(取决于需要存储多少临时数据)。通常,如果一个迭代器在另一个迭代器启动之前使用大部分或全部数据,那么使用它会更快 list() 而不是 tee() .

itertools.zip_longest(*iterables, fillvalue=None)

生成一个从每个iterables聚合元素的迭代器。如果iterables的长度不均匀,则将缺少的值填入 填充值 . 迭代一直持续到最长的iterable用完为止。大致相当于:

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)

如果其中一个iterables可能是无限的,那么 zip_longest() 函数应该用限制调用次数的内容(例如 islice()takewhile() )如果未指定, 填充值 默认为 None .

Itertools秘诀

本节显示了使用现有的itertools作为构建基块创建扩展工具集的方法。

基本上所有这些菜谱和许多其他菜谱都可以从 more-itertools project 在Python包索引中找到:

pip install more-itertools

扩展工具提供与底层工具集相同的高性能。优越的内存性能是由一次处理一个元素来保持的,而不是一次将整个iterable都带到内存中。通过将工具以一种有助于消除临时变量的功能样式链接在一起,代码量保持较小。与for循环和 generator 这会增加翻译费用。

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