# `itertools` --- 为高效循环而创建迭代器的函数¶

`count()`

[start[, step]]

start, start+step, start+2*step, ...

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

`cycle()`

p

p0, p1, ... plast, p0, p1, ...

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

`repeat()`

elem [,n]

elem, elem, elem, ... 重复无限次或n次

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

`accumulate()`

p [,func]

p0, p0+p1, p0+p1+p2, ...

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

`batched()`

p, n

(p0, p1, ..., p_n-1), ...

`batched('ABCDEFG', n=3) --> ABC DEF G`

`chain()`

p, q, ...

p0, p1, ... plast, q0, q1, ...

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

`chain.from_iterable()`

iterable -- 可迭代对象

p0, p1, ... plast, q0, q1, ...

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

`compress()`

data, selectors

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

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

`dropwhile()`

pred, seq

seq[n], seq[n+1], ... 从pred首次真值测试失败开始

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

`filterfalse()`

pred, seq

seq中pred(x)为假值的元素，x是seq中的元素。

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

`groupby()`

iterable[, key]

`islice()`

seq, [start,] stop [, step]

seq[start:stop:step]中的元素

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

`pairwise()`

iterable -- 可迭代对象

(p[0], p[1]), (p[1], p[2])

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

`starmap()`

func, seq

func(*seq[0]), func(*seq[1]), ...

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

`takewhile()`

pred, seq

seq[0], seq[1], ..., 直到pred真值测试失败

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

`tee()`

it, 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]

`permutations()`

p[, r]

`combinations()`

p, r

`combinations_with_replacement()`

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

```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 10 annual payments of 90
>>> account_update = lambda bal, pmt: round(bal * 1.05) + pmt
>>> list(accumulate(repeat(-90, 10), account_update, initial=1_000))
[1000, 960, 918, 874, 828, 779, 728, 674, 618, 559, 497]
```

3.2 新版功能.

itertools.batched(iterable, n)

```>>> flattened_data = ['roses', 'red', 'violets', 'blue', 'sugar', 'sweet']
>>> unflattened = list(batched(flattened_data, 2))
>>> unflattened
[('roses', 'red'), ('violets', 'blue'), ('sugar', 'sweet')]

>>> for batch in batched('ABCDEFG', 3):
...     print(batch)
...
('A', 'B', 'C')
('D', 'E', 'F')
('G',)
```

```def batched(iterable, n):
# 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
```

3.12 新版功能.

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)

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

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

`0 <= r <= n` 时，返回项的个数是 `n! / r! / (n-r)!`；当 `r > n` 时，返回项个数为0。

itertools.combinations_with_replacement(iterable, 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()` 的代码可被改写为 `production()` 过滤后的子序列，（相对于元素在输入中的位置）元素不是有序的。

```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 > 0` 时，返回项个数为 `(n+r-1)! / r! / (n-1)!`.

3.1 新版功能.

itertools.compress(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)

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

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)

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

`groupby()` 操作类似于Unix中的 `uniq`。当每次 key 函数产生的键值改变时，迭代器会分组或生成一个新组（这就是为什么通常需要使用同一个键值函数先对数据进行排序）。这种行为与SQL的GROUP BY操作不同，SQL的操作会忽略输入的顺序将相同键值的元素分在同组中。

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

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

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

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

`0 <= r <= n` ，返回项个数为 `n! / (n-r)!` ；当 `r > n` ，返回项个数为0。

itertools.product(*iterables, repeat=1)

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

```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 的一个常见用途是向 mapzip 提供一个常量值的流:

```>>> list(map(pow, range(10), repeat(2)))
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
```
itertools.starmap(function, 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)

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

```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()` 调用所返回的迭代器时可能引发 `RuntimeError`，即使原本的 iterable 是线程安全的。is threadsafe.

itertools.zip_longest(*iterables, fillvalue=None)

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

## itertools 配方¶

```python -m pip install more-itertools
```

```import collections
import functools
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 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 flatten(list_of_lists):
"Flatten one level of nesting"
return chain.from_iterable(list_of_lists)

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

def 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):
# 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 quantify(iterable, pred=bool):
"Given a predicate that returns True or False, count the True results."
return sum(map(pred, iterable))

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 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 iter_index(iterable, value, start=0, stop=None):
"Return indices where a value occurs in a sequence or iterable."
# iter_index('AABCADEAF', 'A') --> 0 1 4 7
seq_index = getattr(iterable, 'index', None)
if seq_index is None:
# Slow path for general iterables
it = islice(iterable, start, stop)
for i, element in enumerate(it, start):
if element is value or element == value:
yield i
else:
# Fast path for sequences
stop = len(iterable) if stop is None else stop
i = start - 1
try:
while True:
yield (i := seq_index(value, i+1, stop))
except ValueError:
pass

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 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 sliding_window(iterable, n):
# sliding_window('ABCDEFG', 4) --> ABCD BCDE CDEF DEFG
it = iter(iterable)
window = collections.deque(islice(it, n-1), maxlen=n)
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):
"""Partition entries into false entries and true entries.

If *pred* is slow, consider wrapping it with functools.lru_cache().
"""
# 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 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 before_and_after(predicate, it):
""" Variant of takewhile() that allows complete

>>> 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 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):
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:
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 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 sum_of_squares(it):
"Add up the squares of the input values."
# sum_of_squares([10, 20, 30]) -> 1400
return math.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(math.sumprod, product(m1, transpose(m2))), n)

def convolve(signal, kernel):
"""Discrete linear convolution of two iterables.

The kernel is fully consumed before the calculations begin.
The signal is consumed lazily and can be infinite.

Convolutions are mathematically commutative.
If the signal and kernel are swapped,
the output will be the same.

Article:  https://betterexplained.com/articles/intuitive-convolution/
"""
# convolve(data, [0.25, 0.25, 0.25, 0.25]) --> Moving average (blur)
# convolve(data, [1/2, 0, -1/2]) --> 1st derivative estimate
# convolve(data, [1, -2, 1]) --> 2nd derivative estimate
kernel = tuple(kernel)[::-1]
n = len(kernel)
padded_signal = chain(repeat(0, n-1), signal, repeat(0, n-1))
return map(math.sumprod, repeat(kernel), windowed_signal)

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]
factors = zip(repeat(1), map(operator.neg, roots))
return list(functools.reduce(convolve, factors, [1]))

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 not n:
return type(x)(0)
powers = map(pow, repeat(x), reversed(range(n)))
return math.sumprod(coefficients, powers)

def polynomial_derivative(coefficients):
"""Compute the first derivative of a polynomial.

f(x)  =  x³ -4x² -17x + 60
f'(x) = 3x² -8x  -17
"""
# polynomial_derivative([1, -4, -17, 60]) -> [3, -8, -17]
n = len(coefficients)
powers = reversed(range(1, n))
return list(map(operator.mul, coefficients, powers))

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

def factor(n):
"Prime factors of n."
# factor(99) --> 3 3 11
# factor(1_000_000_000_000_007) --> 47 59 360620266859
# factor(1_000_000_000_000_403) --> 1000000000000403
for prime in sieve(math.isqrt(n) + 1):
while not n % prime:
yield prime
n //= prime
if n == 1:
return
if n > 1:
yield n

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