1"""Imported from the recipes section of the itertools documentation.
2
3All functions taken from the recipes section of the itertools library docs
4[1]_.
5Some backward-compatible usability improvements have been made.
6
7.. [1] http://docs.python.org/library/itertools.html#recipes
8
9"""
10
11import random
12
13from bisect import bisect_left, insort
14from collections import deque
15from contextlib import suppress
16from dataclasses import dataclass
17from functools import lru_cache, reduce
18from heapq import heappush, heappushpop
19from itertools import (
20 accumulate,
21 chain,
22 combinations,
23 compress,
24 count,
25 cycle,
26 filterfalse,
27 groupby,
28 islice,
29 pairwise as itertools_pairwise,
30 product,
31 repeat,
32 starmap,
33 takewhile,
34 tee,
35 zip_longest,
36)
37from math import prod, comb, isqrt, gcd
38from operator import mul, getitem, index as _index, is_, itemgetter, truediv
39from random import randrange, sample, choice, shuffle
40from sys import hexversion
41
42__all__ = [
43 'Stats',
44 'all_equal',
45 'batched',
46 'before_and_after',
47 'consume',
48 'convolve',
49 'dotproduct',
50 'factor',
51 'first_true',
52 'flatten',
53 'grouper',
54 'is_prime',
55 'iter_except',
56 'iter_index',
57 'loops',
58 'matmul',
59 'multinomial',
60 'ncycles',
61 'nth',
62 'nth_combination',
63 'pad_none',
64 'padnone',
65 'pairwise',
66 'partition',
67 'polynomial_derivative',
68 'polynomial_eval',
69 'polynomial_from_roots',
70 'powerset',
71 'prepend',
72 'quantify',
73 'random_combination',
74 'random_combination_with_replacement',
75 'random_derangement',
76 'random_permutation',
77 'random_product',
78 'repeatfunc',
79 'reshape',
80 'roundrobin',
81 'running_max',
82 'running_mean',
83 'running_median',
84 'running_min',
85 'running_statistics',
86 'sieve',
87 'sliding_window',
88 'subslices',
89 'sum_of_squares',
90 'tabulate',
91 'tail',
92 'take',
93 'totient',
94 'transpose',
95 'triplewise',
96 'unique',
97 'unique_everseen',
98 'unique_justseen',
99]
100
101_marker = object()
102
103
104# heapq max-heap functions are available for Python 3.14+
105try:
106 from heapq import heappush_max, heappushpop_max
107except ImportError: # pragma: no cover
108 _max_heap_available = False
109else: # pragma: no cover
110 _max_heap_available = True
111
112
113def take(n, iterable):
114 """Return first *n* items of the *iterable* as a list.
115
116 >>> take(3, range(10))
117 [0, 1, 2]
118
119 If there are fewer than *n* items in the iterable, all of them are
120 returned.
121
122 >>> take(10, range(3))
123 [0, 1, 2]
124
125 """
126 return list(islice(iterable, n))
127
128
129def tabulate(function, start=0):
130 """Return an iterator over the results of ``func(start)``,
131 ``func(start + 1)``, ``func(start + 2)``...
132
133 *func* should be a function that accepts one integer argument.
134
135 If *start* is not specified it defaults to 0. It will be incremented each
136 time the iterator is advanced.
137
138 >>> square = lambda x: x ** 2
139 >>> iterator = tabulate(square, -3)
140 >>> take(4, iterator)
141 [9, 4, 1, 0]
142
143 """
144 return map(function, count(start))
145
146
147def tail(n, iterable):
148 """Return an iterator over the last *n* items of *iterable*.
149
150 >>> t = tail(3, 'ABCDEFG')
151 >>> list(t)
152 ['E', 'F', 'G']
153
154 """
155 try:
156 size = len(iterable)
157 except TypeError:
158 return iter(deque(iterable, maxlen=n))
159 else:
160 return islice(iterable, max(0, size - n), None)
161
162
163def consume(iterator, n=None):
164 """Advance *iterable* by *n* steps. If *n* is ``None``, consume it
165 entirely.
166
167 Efficiently exhausts an iterator without returning values. Defaults to
168 consuming the whole iterator, but an optional second argument may be
169 provided to limit consumption.
170
171 >>> i = (x for x in range(10))
172 >>> next(i)
173 0
174 >>> consume(i, 3)
175 >>> next(i)
176 4
177 >>> consume(i)
178 >>> next(i)
179 Traceback (most recent call last):
180 File "<stdin>", line 1, in <module>
181 StopIteration
182
183 If the iterator has fewer items remaining than the provided limit, the
184 whole iterator will be consumed.
185
186 >>> i = (x for x in range(3))
187 >>> consume(i, 5)
188 >>> next(i)
189 Traceback (most recent call last):
190 File "<stdin>", line 1, in <module>
191 StopIteration
192
193 """
194 # Use functions that consume iterators at C speed.
195 if n is None:
196 # feed the entire iterator into a zero-length deque
197 deque(iterator, maxlen=0)
198 else:
199 # advance to the empty slice starting at position n
200 next(islice(iterator, n, n), None)
201
202
203def nth(iterable, n, default=None):
204 """Returns the nth item or a default value.
205
206 >>> l = range(10)
207 >>> nth(l, 3)
208 3
209 >>> nth(l, 20, "zebra")
210 'zebra'
211
212 """
213 return next(islice(iterable, n, None), default)
214
215
216def all_equal(iterable, key=None):
217 """
218 Returns ``True`` if all the elements are equal to each other.
219
220 >>> all_equal('aaaa')
221 True
222 >>> all_equal('aaab')
223 False
224
225 A function that accepts a single argument and returns a transformed version
226 of each input item can be specified with *key*:
227
228 >>> all_equal('AaaA', key=str.casefold)
229 True
230 >>> all_equal([1, 2, 3], key=lambda x: x < 10)
231 True
232
233 """
234 iterator = groupby(iterable, key)
235 for first in iterator:
236 for second in iterator:
237 return False
238 return True
239 return True
240
241
242def quantify(iterable, pred=bool):
243 """Return the how many times the predicate is true.
244
245 >>> quantify([True, False, True])
246 2
247 >>> quantify(range(100, 200), pred=lambda x: x<120)
248 20
249
250 """
251 return sum(map(pred, iterable))
252
253
254def pad_none(iterable):
255 """Returns the sequence of elements and then returns ``None`` indefinitely.
256
257 >>> take(5, pad_none(range(3)))
258 [0, 1, 2, None, None]
259
260 Useful for emulating the behavior of the built-in :func:`map` function.
261
262 See also :func:`padded`.
263
264 """
265 return chain(iterable, repeat(None))
266
267
268padnone = pad_none
269
270
271def ncycles(iterable, n):
272 """Returns the sequence elements *n* times
273
274 >>> list(ncycles(["a", "b"], 3))
275 ['a', 'b', 'a', 'b', 'a', 'b']
276
277 """
278 return chain.from_iterable(repeat(tuple(iterable), n))
279
280
281def dotproduct(vec1, vec2):
282 """Returns the dot product of the two iterables.
283
284 >>> dotproduct([10, 15, 12], [0.65, 0.80, 1.25])
285 33.5
286 >>> 10 * 0.65 + 15 * 0.80 + 12 * 1.25
287 33.5
288
289 In Python 3.12 and later, use ``math.sumprod()`` instead.
290 """
291 return sum(map(mul, vec1, vec2))
292
293
294# math.sumprod is available for Python 3.12+
295try:
296 from math import sumprod as _sumprod
297except ImportError: # pragma: no cover
298 _sumprod = dotproduct
299
300
301def flatten(list_of_lists):
302 """Return an iterator flattening one level of nesting in a list of lists.
303
304 >>> list(flatten([[0, 1], [2, 3]]))
305 [0, 1, 2, 3]
306
307 See also :func:`collapse`, which can flatten multiple levels of nesting.
308
309 """
310 return chain.from_iterable(list_of_lists)
311
312
313def repeatfunc(function, times=None, *args):
314 """Call *function* with *args* repeatedly, returning an iterable over the
315 results.
316
317 If *times* is specified, the iterable will terminate after that many
318 repetitions:
319
320 >>> from operator import add
321 >>> times = 4
322 >>> args = 3, 5
323 >>> list(repeatfunc(add, times, *args))
324 [8, 8, 8, 8]
325
326 If *times* is ``None`` the iterable will not terminate:
327
328 >>> from random import randrange
329 >>> times = None
330 >>> args = 1, 11
331 >>> take(6, repeatfunc(randrange, times, *args)) # doctest:+SKIP
332 [2, 4, 8, 1, 8, 4]
333
334 """
335 if times is None:
336 return starmap(function, repeat(args))
337 return starmap(function, repeat(args, times))
338
339
340def pairwise(iterable):
341 """
342 Wrapper for :func:`itertools.pairwise`.
343
344 .. deprecated:: 11.0.0
345 Will be removed in a future major release.
346 """
347 return itertools_pairwise(iterable)
348
349
350def grouper(iterable, n, incomplete='fill', fillvalue=None):
351 """Group elements from *iterable* into fixed-length groups of length *n*.
352
353 >>> list(grouper('ABCDEF', 3))
354 [('A', 'B', 'C'), ('D', 'E', 'F')]
355
356 The keyword arguments *incomplete* and *fillvalue* control what happens for
357 iterables whose length is not a multiple of *n*.
358
359 When *incomplete* is `'fill'`, the last group will contain instances of
360 *fillvalue*.
361
362 >>> list(grouper('ABCDEFG', 3, incomplete='fill', fillvalue='x'))
363 [('A', 'B', 'C'), ('D', 'E', 'F'), ('G', 'x', 'x')]
364
365 When *incomplete* is `'ignore'`, the last group will not be emitted.
366
367 >>> list(grouper('ABCDEFG', 3, incomplete='ignore', fillvalue='x'))
368 [('A', 'B', 'C'), ('D', 'E', 'F')]
369
370 When *incomplete* is `'strict'`, a `ValueError` will be raised.
371
372 >>> iterator = grouper('ABCDEFG', 3, incomplete='strict')
373 >>> list(iterator) # doctest: +IGNORE_EXCEPTION_DETAIL
374 Traceback (most recent call last):
375 ...
376 ValueError
377
378 """
379 iterators = [iter(iterable)] * n
380 match incomplete:
381 case 'fill':
382 return zip_longest(*iterators, fillvalue=fillvalue)
383 case 'strict':
384 return zip(*iterators, strict=True)
385 case 'ignore':
386 return zip(*iterators)
387 case _:
388 raise ValueError('Expected fill, strict, or ignore')
389
390
391def roundrobin(*iterables):
392 """Visit input iterables in a cycle until each is exhausted.
393
394 >>> list(roundrobin('ABC', 'D', 'EF'))
395 ['A', 'D', 'E', 'B', 'F', 'C']
396
397 This function produces the same output as :func:`interleave_longest`, but
398 may perform better for some inputs (in particular when the number of
399 iterables is small).
400
401 """
402 # Algorithm credited to George Sakkis
403 iterators = map(iter, iterables)
404 for num_active in range(len(iterables), 0, -1):
405 iterators = cycle(islice(iterators, num_active))
406 yield from map(next, iterators)
407
408
409def partition(pred, iterable):
410 """
411 Returns a 2-tuple of iterables derived from the input iterable.
412 The first yields the items that have ``pred(item) == False``.
413 The second yields the items that have ``pred(item) == True``.
414
415 >>> is_odd = lambda x: x % 2 != 0
416 >>> iterable = range(10)
417 >>> even_items, odd_items = partition(is_odd, iterable)
418 >>> list(even_items), list(odd_items)
419 ([0, 2, 4, 6, 8], [1, 3, 5, 7, 9])
420
421 If *pred* is None, :func:`bool` is used.
422
423 >>> iterable = [0, 1, False, True, '', ' ']
424 >>> false_items, true_items = partition(None, iterable)
425 >>> list(false_items), list(true_items)
426 ([0, False, ''], [1, True, ' '])
427
428 """
429 if pred is None:
430 pred = bool
431 iterator = iter(iterable)
432
433 false_queue = deque()
434 true_queue = deque()
435
436 def gen(queue):
437 append_false = false_queue.append
438 append_true = true_queue.append
439 while True:
440 while queue:
441 yield queue.popleft()
442 for value in iterator:
443 (append_true if pred(value) else append_false)(value)
444 break
445 else:
446 return
447
448 return gen(false_queue), gen(true_queue)
449
450
451def powerset(iterable):
452 """Yields all possible subsets of the iterable.
453
454 >>> list(powerset([1, 2, 3]))
455 [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
456
457 :func:`powerset` will operate on iterables that aren't :class:`set`
458 instances, so repeated elements in the input will produce repeated elements
459 in the output.
460
461 >>> seq = [1, 1, 0]
462 >>> list(powerset(seq))
463 [(), (1,), (1,), (0,), (1, 1), (1, 0), (1, 0), (1, 1, 0)]
464
465 For a variant that efficiently yields actual :class:`set` instances, see
466 :func:`powerset_of_sets`.
467 """
468 s = list(iterable)
469 return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))
470
471
472def unique_everseen(iterable, key=None):
473 """Yield unique elements, preserving order. Remember all elements ever seen.
474
475 >>> list(unique_everseen('AAAABBBCCDAABBB'))
476 ['A', 'B', 'C', 'D']
477 >>> list(unique_everseen('ABBCcAD', str.casefold))
478 ['A', 'B', 'C', 'D']
479
480 Raises ``TypeError`` for unhashable items.
481
482 Some unhashable objects can be converted to hashable objects
483 using the *key* parameter:
484
485 * For ``list`` objects, try ``key=tuple``.
486 * For ``set`` objects, try ``key=frozenset``.
487 * For ``dict`` objects, try ``key=lambda x: frozenset(x.items())``
488 or in Python 3.15 and later, set ``key=frozendict``.
489
490 Alternatively, consider the ``unique()`` itertool recipe. It sorts
491 the data and then uses equality to eliminate duplicates. Hashability
492 is not required.
493
494 """
495 seen = set()
496 if key is None:
497 for element in filterfalse(seen.__contains__, iterable):
498 seen.add(element)
499 yield element
500 else:
501 for element in iterable:
502 k = key(element)
503 if k not in seen:
504 seen.add(k)
505 yield element
506
507
508def unique_justseen(iterable, key=None):
509 """Yields elements in order, ignoring serial duplicates
510
511 >>> list(unique_justseen('AAAABBBCCDAABBB'))
512 ['A', 'B', 'C', 'D', 'A', 'B']
513 >>> list(unique_justseen('ABBCcAD', str.lower))
514 ['A', 'B', 'C', 'A', 'D']
515
516 """
517 if key is None:
518 return map(itemgetter(0), groupby(iterable))
519
520 return map(next, map(itemgetter(1), groupby(iterable, key)))
521
522
523def unique(iterable, key=None, reverse=False):
524 """Yields unique elements in sorted order.
525
526 >>> list(unique([[1, 2], [3, 4], [1, 2]]))
527 [[1, 2], [3, 4]]
528
529 *key* and *reverse* are passed to :func:`sorted`.
530
531 >>> list(unique('ABBcCAD', str.casefold))
532 ['A', 'B', 'c', 'D']
533 >>> list(unique('ABBcCAD', str.casefold, reverse=True))
534 ['D', 'c', 'B', 'A']
535
536 The elements in *iterable* need not be hashable, but they must be
537 comparable for sorting to work.
538 """
539 sequenced = sorted(iterable, key=key, reverse=reverse)
540 return unique_justseen(sequenced, key=key)
541
542
543def iter_except(function, exception, first=None):
544 """Yields results from a function repeatedly until an exception is raised.
545
546 Converts a call-until-exception interface to an iterator interface.
547 Like ``iter(function, sentinel)``, but uses an exception instead of a sentinel
548 to end the loop.
549
550 Examples:
551 iter_except(functools.partial(heappop, h), IndexError) # priority queue iterator
552 iter_except(d.popitem, KeyError) # non-blocking dict iterator
553 iter_except(d.popleft, IndexError) # non-blocking deque iterator
554 iter_except(q.get_nowait, Queue.Empty) # loop over a producer Queue
555 iter_except(s.pop, KeyError) # non-blocking set iterator
556
557 Multiple exceptions can be specified as a stopping condition, for example
558 ``(IndexError, TypeError)``.
559
560 """
561 with suppress(exception):
562 if first is not None:
563 yield first()
564 while True:
565 yield function()
566
567
568def first_true(iterable, default=None, pred=None):
569 """
570 Returns the first true value in the iterable.
571
572 If no true value is found, returns *default*
573
574 If *pred* is not None, returns the first item for which
575 ``pred(item) == True`` .
576
577 >>> first_true(range(10))
578 1
579 >>> first_true(range(10), pred=lambda x: x > 5)
580 6
581 >>> first_true(range(10), default='missing', pred=lambda x: x > 9)
582 'missing'
583
584 """
585 return next(filter(pred, iterable), default)
586
587
588def random_product(*iterables, repeat=1):
589 """Draw an item at random from each of the input iterables.
590
591 >>> random_product('abc', range(4), 'XYZ') # doctest:+SKIP
592 ('c', 3, 'Z')
593
594 If *repeat* is provided as a keyword argument, that many items will be
595 drawn from each iterable.
596
597 >>> random_product('abcd', range(4), repeat=2) # doctest:+SKIP
598 ('a', 2, 'd', 3)
599
600 This is equivalent to taking a random selection from
601 ``itertools.product(*args, repeat=repeat)``.
602
603 """
604 pools = tuple(map(tuple, iterables)) * repeat
605 return tuple(map(choice, pools))
606
607
608def random_permutation(iterable, r=None):
609 """Return a random *r* length permutation of the elements in *iterable*.
610
611 If *r* is not specified or is ``None``, then *r* defaults to the length of
612 *iterable*.
613
614 >>> random_permutation(range(5)) # doctest:+SKIP
615 (3, 4, 0, 1, 2)
616
617 This is equivalent to taking a random selection from
618 ``itertools.permutations(iterable, r)``.
619
620 """
621 pool = tuple(iterable)
622 r = len(pool) if r is None else r
623 return tuple(sample(pool, r))
624
625
626def random_combination(iterable, r):
627 """Return a random *r* length subsequence of the elements in *iterable*.
628
629 >>> random_combination(range(5), 3) # doctest:+SKIP
630 (2, 3, 4)
631
632 This is equivalent to taking a random selection from
633 ``itertools.combinations(iterable, r)``.
634
635 """
636 pool = tuple(iterable)
637 n = len(pool)
638 indices = sorted(sample(range(n), r))
639 return tuple([pool[i] for i in indices])
640
641
642def random_combination_with_replacement(iterable, r):
643 """Return a random *r* length subsequence of elements in *iterable*,
644 allowing individual elements to be repeated.
645
646 >>> random_combination_with_replacement(range(3), 5) # doctest:+SKIP
647 (0, 0, 1, 2, 2)
648
649 This is equivalent to taking a random selection from
650 ``itertools.combinations_with_replacement(iterable, r)``.
651
652 """
653 pool = tuple(iterable)
654 n = len(pool)
655 indices = sorted(randrange(n) for i in range(r))
656 return tuple([pool[i] for i in indices])
657
658
659def nth_combination(iterable, r, index):
660 """Equivalent to ``list(combinations(iterable, r))[index]``.
661
662 The subsequences of *iterable* that are of length *r* can be ordered
663 lexicographically. :func:`nth_combination` computes the subsequence at
664 sort position *index* directly, without computing the previous
665 subsequences.
666
667 >>> nth_combination(range(5), 3, 5)
668 (0, 3, 4)
669
670 ``ValueError`` will be raised if *r* is negative.
671 ``IndexError`` will be raised if the given *index* is invalid.
672 """
673 pool = tuple(iterable)
674 n = len(pool)
675 c = comb(n, r)
676
677 if index < 0:
678 index += c
679 if not 0 <= index < c:
680 raise IndexError
681
682 result = []
683 while r:
684 c, n, r = c * r // n, n - 1, r - 1
685 while index >= c:
686 index -= c
687 c, n = c * (n - r) // n, n - 1
688 result.append(pool[-1 - n])
689
690 return tuple(result)
691
692
693def prepend(value, iterable):
694 """Yield *value*, followed by the elements in *iterable*.
695
696 >>> value = '0'
697 >>> iterable = ['1', '2', '3']
698 >>> list(prepend(value, iterable))
699 ['0', '1', '2', '3']
700
701 To prepend multiple values, see :func:`itertools.chain`
702 or :func:`value_chain`.
703
704 """
705 return chain([value], iterable)
706
707
708def convolve(signal, kernel):
709 """Discrete linear convolution of two iterables.
710 Equivalent to polynomial multiplication.
711
712 For example, multiplying ``(x² -x - 20)`` by ``(x - 3)``
713 gives ``(x³ -4x² -17x + 60)``.
714
715 >>> list(convolve([1, -1, -20], [1, -3]))
716 [1, -4, -17, 60]
717
718 Examples of useful kernels:
719
720 * The kernel ``[0.25, 0.25, 0.25, 0.25]`` computes a moving average.
721 For image data, this blurs the image and reduces noise.
722 * The kernel ``[1/2, 0, -1/2]`` estimates the first derivative of
723 a function evaluated at evenly spaced inputs.
724 * The kernel ``[1, -2, 1]`` estimates the second derivative of a
725 function evaluated at evenly spaced inputs.
726
727 Convolutions are mathematically commutative. However, the input iterables are
728 evaluated differently by this function. *signal* is consumed lazily and can be
729 infinite. *kernel* is fully consumed before calculations begin.
730
731 Supports all numeric types: int, float, complex, Decimal, Fraction.
732 Note that empty input iterables will produce meaningless output.
733
734 References:
735
736 * Article: https://betterexplained.com/articles/intuitive-convolution/
737 * Video by 3Blue1Brown: https://www.youtube.com/watch?v=KuXjwB4LzSA
738
739 """
740 # This implementation comes from an older version of the itertools
741 # documentation. While the newer implementation is a bit clearer,
742 # this one was kept because the inlined window logic is faster
743 # and it avoids an unnecessary deque-to-tuple conversion.
744 kernel = tuple(kernel)[::-1]
745 n = len(kernel)
746 window = deque([0], maxlen=n) * n
747 for x in chain(signal, repeat(0, n - 1)):
748 window.append(x)
749 yield _sumprod(kernel, window)
750
751
752def before_and_after(predicate, it):
753 """A variant of :func:`takewhile` that allows complete access to the
754 remainder of the iterator.
755
756 >>> it = iter('ABCdEfGhI')
757 >>> all_upper, remainder = before_and_after(str.isupper, it)
758 >>> ''.join(all_upper)
759 'ABC'
760 >>> ''.join(remainder) # takewhile() would lose the 'd'
761 'dEfGhI'
762
763 Note that the first iterator must be fully consumed before the second
764 iterator can generate valid results.
765 """
766 trues, after = tee(it)
767 trues = compress(takewhile(predicate, trues), zip(after))
768 return trues, after
769
770
771def triplewise(iterable):
772 """Return overlapping triplets from *iterable*.
773
774 >>> list(triplewise('ABCDE'))
775 [('A', 'B', 'C'), ('B', 'C', 'D'), ('C', 'D', 'E')]
776
777 """
778 # This deviates from the itertools documentation recipe - see
779 # https://github.com/more-itertools/more-itertools/issues/889
780 t1, t2, t3 = tee(iterable, 3)
781 next(t3, None)
782 next(t3, None)
783 next(t2, None)
784 return zip(t1, t2, t3)
785
786
787def _sliding_window_islice(iterable, n):
788 # Fast path for small, non-zero values of n.
789 iterators = tee(iterable, n)
790 for i, iterator in enumerate(iterators):
791 next(islice(iterator, i, i), None)
792 return zip(*iterators)
793
794
795def _sliding_window_deque(iterable, n):
796 # Normal path for other values of n.
797 iterator = iter(iterable)
798 window = deque(islice(iterator, n - 1), maxlen=n)
799 for x in iterator:
800 window.append(x)
801 yield tuple(window)
802
803
804def sliding_window(iterable, n):
805 """Return a sliding window of width *n* over *iterable*.
806
807 >>> list(sliding_window(range(6), 4))
808 [(0, 1, 2, 3), (1, 2, 3, 4), (2, 3, 4, 5)]
809
810 If *iterable* has fewer than *n* items, then nothing is yielded:
811
812 >>> list(sliding_window(range(3), 4))
813 []
814
815 For a variant with more features, see :func:`windowed`.
816 """
817 if n > 20:
818 return _sliding_window_deque(iterable, n)
819 elif n > 2:
820 return _sliding_window_islice(iterable, n)
821 elif n == 2:
822 return pairwise(iterable)
823 elif n == 1:
824 return zip(iterable)
825 else:
826 raise ValueError(f'n should be at least one, not {n}')
827
828
829def subslices(iterable):
830 """Return all contiguous non-empty subslices of *iterable*.
831
832 >>> list(subslices('ABC'))
833 [['A'], ['A', 'B'], ['A', 'B', 'C'], ['B'], ['B', 'C'], ['C']]
834
835 This is similar to :func:`substrings`, but emits items in a different
836 order.
837 """
838 seq = list(iterable)
839 slices = starmap(slice, combinations(range(len(seq) + 1), 2))
840 return map(getitem, repeat(seq), slices)
841
842
843def polynomial_from_roots(roots):
844 """Compute a polynomial's coefficients from its roots.
845
846 >>> roots = [5, -4, 3] # (x - 5) * (x + 4) * (x - 3)
847 >>> polynomial_from_roots(roots) # x³ - 4 x² - 17 x + 60
848 [1, -4, -17, 60]
849
850 Note that polynomial coefficients are specified in descending power order.
851
852 Supports all numeric types: int, float, complex, Decimal, Fraction.
853 """
854
855 # This recipe differs from the one in itertools docs in that it
856 # applies list() after each call to convolve(). This avoids
857 # hitting stack limits with nested generators.
858
859 poly = [1]
860 for root in roots:
861 poly = list(convolve(poly, (1, -root)))
862 return poly
863
864
865def iter_index(iterable, value, start=0, stop=None):
866 """Yield the index of each place in *iterable* that *value* occurs,
867 beginning with index *start* and ending before index *stop*.
868
869 >>> list(iter_index('AABCADEAF', 'A'))
870 [0, 1, 4, 7]
871 >>> list(iter_index('AABCADEAF', 'A', 1)) # start index is inclusive
872 [1, 4, 7]
873 >>> list(iter_index('AABCADEAF', 'A', 1, 7)) # stop index is not inclusive
874 [1, 4]
875
876 The behavior for non-scalar *value* arguments matches the built-in Python types.
877
878 >>> list(iter_index('ABCDABCD', 'AB'))
879 [0, 4]
880 >>> list(iter_index([0, 1, 2, 3, 0, 1, 2, 3], [0, 1]))
881 []
882 >>> list(iter_index([[0, 1], [2, 3], [0, 1], [2, 3]], [0, 1]))
883 [0, 2]
884
885 For ``range`` objects (and other objects whose ``index`` method's behavior doesn't
886 match that of ``list``), wrap *iterable* with ``iter``:
887
888 >>> list(iter_index(iter(range(5)), 2))
889 [2]
890
891 See :func:`locate` for a more general means of finding the indexes
892 associated with particular values.
893
894 """
895 seq_index = getattr(iterable, 'index', None)
896 if seq_index is None:
897 # Slow path for general iterables
898 iterator = islice(iterable, start, stop)
899 for i, element in enumerate(iterator, start):
900 if element is value or element == value:
901 yield i
902 else:
903 # Fast path for sequences
904 stop = len(iterable) if stop is None else stop
905 i = start - 1
906 with suppress(ValueError):
907 while True:
908 yield (i := seq_index(value, i + 1, stop))
909
910
911def sieve(n):
912 """Yield the primes less than n.
913
914 >>> list(sieve(30))
915 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
916
917 """
918 # This implementation comes from an older version of the itertools
919 # documentation. The newer implementation is easier to read but is
920 # less lazy.
921 if n > 2:
922 yield 2
923 start = 3
924 data = bytearray((0, 1)) * (n // 2)
925 for p in iter_index(data, 1, start, stop=isqrt(n) + 1):
926 yield from iter_index(data, 1, start, p * p)
927 data[p * p : n : p + p] = bytes(len(range(p * p, n, p + p)))
928 start = p * p
929 yield from iter_index(data, 1, start)
930
931
932def _batched(iterable, n, *, strict=False): # pragma: no cover
933 """Batch data into tuples of length *n*. If the number of items in
934 *iterable* is not divisible by *n*:
935 * The last batch will be shorter if *strict* is ``False``.
936 * :exc:`ValueError` will be raised if *strict* is ``True``.
937
938 >>> list(batched('ABCDEFG', 3))
939 [('A', 'B', 'C'), ('D', 'E', 'F'), ('G',)]
940
941 On Python 3.13 and above, this is an alias for :func:`itertools.batched`.
942 """
943 if n < 1:
944 raise ValueError('n must be at least one')
945 iterator = iter(iterable)
946 while batch := tuple(islice(iterator, n)):
947 if strict and len(batch) != n:
948 raise ValueError('batched(): incomplete batch')
949 yield batch
950
951
952if hexversion >= 0x30D00A2: # pragma: no cover
953 from itertools import batched as itertools_batched
954
955 def batched(iterable, n, *, strict=False):
956 return itertools_batched(iterable, n, strict=strict)
957
958 batched.__doc__ = _batched.__doc__
959else: # pragma: no cover
960 batched = _batched
961
962
963def transpose(matrix):
964 """Swap the rows and columns of the input matrix.
965
966 >>> list(transpose([(1, 2, 3), (11, 22, 33)]))
967 [(1, 11), (2, 22), (3, 33)]
968
969 The caller should ensure that the dimensions of the input are compatible.
970 If the input is empty, no output will be produced.
971 """
972 return zip(*matrix, strict=True)
973
974
975def _is_scalar(value, stringlike=(str, bytes)):
976 "Scalars are bytes, strings, and non-iterables."
977 try:
978 iter(value)
979 except TypeError:
980 return True
981 return isinstance(value, stringlike)
982
983
984def _flatten_tensor(tensor):
985 "Depth-first iterator over scalars in a tensor."
986 iterator = iter(tensor)
987 while True:
988 try:
989 value = next(iterator)
990 except StopIteration:
991 return iterator
992 iterator = chain((value,), iterator)
993 if _is_scalar(value):
994 return iterator
995 iterator = chain.from_iterable(iterator)
996
997
998def reshape(matrix, shape):
999 """Change the shape of a *matrix*.
1000
1001 If *shape* is an integer, the matrix must be two dimensional
1002 and the shape is interpreted as the desired number of columns:
1003
1004 >>> matrix = [(0, 1), (2, 3), (4, 5)]
1005 >>> cols = 3
1006 >>> list(reshape(matrix, cols))
1007 [(0, 1, 2), (3, 4, 5)]
1008
1009 If *shape* is a tuple (or other iterable), the input matrix can have
1010 any number of dimensions. It will first be flattened and then rebuilt
1011 to the desired shape which can also be multidimensional:
1012
1013 >>> matrix = [(0, 1), (2, 3), (4, 5)] # Start with a 3 x 2 matrix
1014
1015 >>> list(reshape(matrix, (2, 3))) # Make a 2 x 3 matrix
1016 [(0, 1, 2), (3, 4, 5)]
1017
1018 >>> list(reshape(matrix, (6,))) # Make a vector of length six
1019 [0, 1, 2, 3, 4, 5]
1020
1021 >>> list(reshape(matrix, (2, 1, 3, 1))) # Make 2 x 1 x 3 x 1 tensor
1022 [(((0,), (1,), (2,)),), (((3,), (4,), (5,)),)]
1023
1024 Each dimension is assumed to be uniform, either all arrays or all scalars.
1025 Flattening stops when the first value in a dimension is a scalar.
1026 Scalars are bytes, strings, and non-iterables.
1027 The reshape iterator stops when the requested shape is complete
1028 or when the input is exhausted, whichever comes first.
1029
1030 """
1031 if isinstance(shape, int):
1032 return batched(chain.from_iterable(matrix), shape)
1033 first_dim, *dims = shape
1034 scalar_stream = _flatten_tensor(matrix)
1035 reshaped = reduce(batched, reversed(dims), scalar_stream)
1036 return islice(reshaped, first_dim)
1037
1038
1039def matmul(m1, m2):
1040 """Multiply two matrices.
1041
1042 >>> list(matmul([(7, 5), (3, 5)], [(2, 5), (7, 9)]))
1043 [(49, 80), (41, 60)]
1044
1045 The caller should ensure that the dimensions of the input matrices are
1046 compatible with each other.
1047
1048 Supports all numeric types: int, float, complex, Decimal, Fraction.
1049 """
1050 n = len(m2[0])
1051 return batched(starmap(_sumprod, product(m1, transpose(m2))), n)
1052
1053
1054def _factor_pollard(n):
1055 # Return a factor of n using Pollard's rho algorithm.
1056 # Efficient when n is odd and composite.
1057 for b in range(1, n):
1058 x = y = 2
1059 d = 1
1060 while d == 1:
1061 x = (x * x + b) % n
1062 y = (y * y + b) % n
1063 y = (y * y + b) % n
1064 d = gcd(x - y, n)
1065 if d != n:
1066 return d
1067 raise ValueError('prime or under 5') # pragma: no cover
1068
1069
1070_primes_below_211 = tuple(sieve(211))
1071
1072
1073def factor(n):
1074 """Yield the prime factors of n.
1075
1076 >>> list(factor(360))
1077 [2, 2, 2, 3, 3, 5]
1078
1079 Finds small factors with trial division. Larger factors are
1080 either verified as prime with ``is_prime`` or split into
1081 smaller factors with Pollard's rho algorithm.
1082 """
1083
1084 # Corner case reduction
1085 if n < 2:
1086 return
1087
1088 # Trial division reduction
1089 for prime in _primes_below_211:
1090 while not n % prime:
1091 yield prime
1092 n //= prime
1093
1094 # Pollard's rho reduction
1095 primes = []
1096 todo = [n] if n > 1 else []
1097 for n in todo:
1098 if n < 211**2 or is_prime(n):
1099 primes.append(n)
1100 else:
1101 fact = _factor_pollard(n)
1102 todo += (fact, n // fact)
1103 yield from sorted(primes)
1104
1105
1106def polynomial_eval(coefficients, x):
1107 """Evaluate a polynomial at a specific value.
1108
1109 Computes with better numeric stability than Horner's method.
1110
1111 Evaluate ``x^3 - 4 * x^2 - 17 * x + 60`` at ``x = 2.5``:
1112
1113 >>> coefficients = [1, -4, -17, 60]
1114 >>> x = 2.5
1115 >>> polynomial_eval(coefficients, x)
1116 8.125
1117
1118 Note that polynomial coefficients are specified in descending power order.
1119
1120 Supports all numeric types: int, float, complex, Decimal, Fraction.
1121 """
1122 n = len(coefficients)
1123 if n == 0:
1124 return type(x)(0)
1125 powers = map(pow, repeat(x), reversed(range(n)))
1126 return _sumprod(coefficients, powers)
1127
1128
1129def sum_of_squares(iterable):
1130 """Return the sum of the squares of the input values.
1131
1132 >>> sum_of_squares([10, 20, 30])
1133 1400
1134
1135 Supports all numeric types: int, float, complex, Decimal, Fraction.
1136 """
1137 return _sumprod(*tee(iterable))
1138
1139
1140def polynomial_derivative(coefficients):
1141 """Compute the first derivative of a polynomial.
1142
1143 Evaluate the derivative of ``x³ - 4 x² - 17 x + 60``:
1144
1145 >>> coefficients = [1, -4, -17, 60]
1146 >>> derivative_coefficients = polynomial_derivative(coefficients)
1147 >>> derivative_coefficients
1148 [3, -8, -17]
1149
1150 Note that polynomial coefficients are specified in descending power order.
1151
1152 Supports all numeric types: int, float, complex, Decimal, Fraction.
1153 """
1154 n = len(coefficients)
1155 powers = reversed(range(1, n))
1156 return list(map(mul, coefficients, powers))
1157
1158
1159def totient(n):
1160 """Return the count of natural numbers up to *n* that are coprime with *n*.
1161
1162 Euler's totient function φ(n) gives the number of totatives.
1163 Totative are integers k in the range 1 ≤ k ≤ n such that gcd(n, k) = 1.
1164
1165 >>> n = 9
1166 >>> totient(n)
1167 6
1168
1169 >>> totatives = [x for x in range(1, n) if gcd(n, x) == 1]
1170 >>> totatives
1171 [1, 2, 4, 5, 7, 8]
1172 >>> len(totatives)
1173 6
1174
1175 Reference: https://en.wikipedia.org/wiki/Euler%27s_totient_function
1176
1177 """
1178 for prime in set(factor(n)):
1179 n -= n // prime
1180 return n
1181
1182
1183# Miller–Rabin primality test: https://oeis.org/A014233
1184_perfect_tests = [
1185 (2047, (2,)),
1186 (9080191, (31, 73)),
1187 (4759123141, (2, 7, 61)),
1188 (1122004669633, (2, 13, 23, 1662803)),
1189 (2152302898747, (2, 3, 5, 7, 11)),
1190 (3474749660383, (2, 3, 5, 7, 11, 13)),
1191 (18446744073709551616, (2, 325, 9375, 28178, 450775, 9780504, 1795265022)),
1192 (
1193 3317044064679887385961981,
1194 (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41),
1195 ),
1196]
1197
1198
1199@lru_cache
1200def _shift_to_odd(n):
1201 'Return s, d such that 2**s * d == n'
1202 s = ((n - 1) ^ n).bit_length() - 1
1203 d = n >> s
1204 assert (1 << s) * d == n and d & 1 and s >= 0
1205 return s, d
1206
1207
1208def _strong_probable_prime(n, base):
1209 assert (n > 2) and (n & 1) and (2 <= base < n)
1210
1211 s, d = _shift_to_odd(n - 1)
1212
1213 x = pow(base, d, n)
1214 if x == 1 or x == n - 1:
1215 return True
1216
1217 for _ in range(s - 1):
1218 x = x * x % n
1219 if x == n - 1:
1220 return True
1221
1222 return False
1223
1224
1225# Separate instance of Random() that doesn't share state
1226# with the default user instance of Random().
1227_private_randrange = random.Random().randrange
1228
1229
1230def is_prime(n):
1231 """Return ``True`` if *n* is prime and ``False`` otherwise.
1232
1233 Basic examples:
1234
1235 >>> is_prime(37)
1236 True
1237 >>> is_prime(3 * 13)
1238 False
1239 >>> is_prime(18_446_744_073_709_551_557)
1240 True
1241
1242 Find the next prime over one billion:
1243
1244 >>> next(filter(is_prime, count(10**9)))
1245 1000000007
1246
1247 Generate random primes up to 200 bits and up to 60 decimal digits:
1248
1249 >>> from random import seed, randrange, getrandbits
1250 >>> seed(18675309)
1251
1252 >>> next(filter(is_prime, map(getrandbits, repeat(200))))
1253 893303929355758292373272075469392561129886005037663238028407
1254
1255 >>> next(filter(is_prime, map(randrange, repeat(10**60))))
1256 269638077304026462407872868003560484232362454342414618963649
1257
1258 This function is exact for values of *n* below 10**24. For larger inputs,
1259 the probabilistic Miller-Rabin primality test has a less than 1 in 2**128
1260 chance of a false positive.
1261 """
1262
1263 if n < 17:
1264 return n in {2, 3, 5, 7, 11, 13}
1265
1266 if not (n & 1 and n % 3 and n % 5 and n % 7 and n % 11 and n % 13):
1267 return False
1268
1269 for limit, bases in _perfect_tests:
1270 if n < limit:
1271 break
1272 else:
1273 bases = (_private_randrange(2, n - 1) for i in range(64))
1274
1275 return all(_strong_probable_prime(n, base) for base in bases)
1276
1277
1278def loops(n):
1279 """Returns an iterable with *n* elements for efficient looping.
1280 Like ``range(n)`` but doesn't create integers.
1281
1282 >>> i = 0
1283 >>> for _ in loops(5):
1284 ... i += 1
1285 >>> i
1286 5
1287
1288 """
1289 return repeat(None, n)
1290
1291
1292def multinomial(*counts):
1293 """Number of distinct arrangements of a multiset.
1294
1295 The expression ``multinomial(3, 4, 2)`` has several equivalent
1296 interpretations:
1297
1298 * In the expansion of ``(a + b + c)⁹``, the coefficient of the
1299 ``a³b⁴c²`` term is 1260.
1300
1301 * There are 1260 distinct ways to arrange 9 balls consisting of 3 reds, 4
1302 greens, and 2 blues.
1303
1304 * There are 1260 unique ways to place 9 distinct objects into three bins
1305 with sizes 3, 4, and 2.
1306
1307 The :func:`multinomial` function computes the length of
1308 :func:`distinct_permutations`. For example, there are 83,160 distinct
1309 anagrams of the word "abracadabra":
1310
1311 >>> from more_itertools import distinct_permutations, ilen
1312 >>> ilen(distinct_permutations('abracadabra'))
1313 83160
1314
1315 This can be computed directly from the letter counts, 5a 2b 2r 1c 1d:
1316
1317 >>> from collections import Counter
1318 >>> list(Counter('abracadabra').values())
1319 [5, 2, 2, 1, 1]
1320 >>> multinomial(5, 2, 2, 1, 1)
1321 83160
1322
1323 A binomial coefficient is a special case of multinomial where there are
1324 only two categories. For example, the number of ways to arrange 12 balls
1325 with 5 reds and 7 blues is ``multinomial(5, 7)`` or ``math.comb(12, 5)``.
1326
1327 Likewise, factorial is a special case of multinomial where
1328 the multiplicities are all just 1 so that
1329 ``multinomial(1, 1, 1, 1, 1, 1, 1) == math.factorial(7)``.
1330
1331 Reference: https://en.wikipedia.org/wiki/Multinomial_theorem
1332
1333 """
1334 return prod(map(comb, accumulate(counts), counts))
1335
1336
1337def _running_median_minheap_and_maxheap(iterator): # pragma: no cover
1338 "Non-windowed running_median() for Python 3.14+"
1339
1340 read = iterator.__next__
1341 lo = [] # max-heap
1342 hi = [] # min-heap (same size as or one smaller than lo)
1343
1344 with suppress(StopIteration):
1345 while True:
1346 heappush_max(lo, heappushpop(hi, read()))
1347 yield lo[0]
1348
1349 heappush(hi, heappushpop_max(lo, read()))
1350 yield (lo[0] + hi[0]) / 2
1351
1352
1353def _running_median_minheap_only(iterator): # pragma: no cover
1354 "Backport of non-windowed running_median() for Python 3.13 and prior."
1355
1356 read = iterator.__next__
1357 lo = [] # max-heap (actually a minheap with negated values)
1358 hi = [] # min-heap (same size as or one smaller than lo)
1359
1360 with suppress(StopIteration):
1361 while True:
1362 heappush(lo, -heappushpop(hi, read()))
1363 yield -lo[0]
1364
1365 heappush(hi, -heappushpop(lo, -read()))
1366 yield (hi[0] - lo[0]) / 2
1367
1368
1369def _running_median_windowed(iterator, maxlen):
1370 "Yield median of values in a sliding window."
1371
1372 window = deque()
1373 ordered = []
1374
1375 for x in iterator:
1376 window.append(x)
1377 insort(ordered, x)
1378
1379 if len(ordered) > maxlen:
1380 i = bisect_left(ordered, window.popleft())
1381 del ordered[i]
1382
1383 n = len(ordered)
1384 m = n // 2
1385 yield ordered[m] if n & 1 else (ordered[m - 1] + ordered[m]) / 2
1386
1387
1388def running_median(iterable, *, maxlen=None):
1389 """Cumulative median of values seen so far or values in a sliding window.
1390
1391 Set *maxlen* to a positive integer to specify the maximum size
1392 of the sliding window. The default of *None* is equivalent to
1393 an unbounded window.
1394
1395 For example:
1396
1397 >>> list(running_median([5.0, 9.0, 4.0, 12.0, 8.0, 9.0]))
1398 [5.0, 7.0, 5.0, 7.0, 8.0, 8.5]
1399 >>> list(running_median([5.0, 9.0, 4.0, 12.0, 8.0, 9.0], maxlen=3))
1400 [5.0, 7.0, 5.0, 9.0, 8.0, 9.0]
1401
1402 Supports numeric types such as int, float, Decimal, and Fraction,
1403 but not complex numbers which are unorderable.
1404
1405 On version Python 3.13 and prior, max-heaps are simulated with
1406 negative values. The negation causes Decimal inputs to apply context
1407 rounding, making the results slightly different than that obtained
1408 by statistics.median().
1409 """
1410
1411 iterator = iter(iterable)
1412
1413 if maxlen is not None:
1414 maxlen = _index(maxlen)
1415 if maxlen <= 0:
1416 raise ValueError('Window size should be positive')
1417 return _running_median_windowed(iterator, maxlen)
1418
1419 if not _max_heap_available:
1420 return _running_median_minheap_only(iterator) # pragma: no cover
1421
1422 return _running_median_minheap_and_maxheap(iterator) # pragma: no cover
1423
1424
1425def _windowed_running_mean(iterator, n):
1426 window = deque()
1427 running_sum = 0
1428 for value in iterator:
1429 window.append(value)
1430 running_sum += value
1431 if len(window) > n:
1432 running_sum -= window.popleft()
1433 yield running_sum / len(window)
1434
1435
1436def running_mean(iterable, *, maxlen=None):
1437 """Cumulative mean of values seen so far or values in a sliding window.
1438
1439 Set *maxlen* to a positive integer to specify the maximum size
1440 of the sliding window. The default of *None* is equivalent to
1441 an unbounded window.
1442
1443 For example:
1444
1445 >>> list(running_mean([40, 30, 50, 46, 39, 44]))
1446 [40.0, 35.0, 40.0, 41.5, 41.0, 41.5]
1447
1448 >>> list(running_mean([40, 30, 50, 46, 39, 44], maxlen=3))
1449 [40.0, 35.0, 40.0, 42.0, 45.0, 43.0]
1450
1451 Supports numeric types such as int, float, complex, Decimal, and Fraction.
1452
1453 No extra effort is made to reduce round-off errors for float inputs.
1454 So the results may be slightly different from `statistics.mean`.
1455
1456 """
1457
1458 iterator = iter(iterable)
1459
1460 if maxlen is None:
1461 return map(truediv, accumulate(iterator), count(1))
1462
1463 maxlen = _index(maxlen)
1464 if maxlen <= 0:
1465 raise ValueError('Window size should be positive')
1466
1467 return _windowed_running_mean(iterator, maxlen)
1468
1469
1470def _windowed_running_min(iterator, maxlen):
1471 # Monotonically increasing subsequence of potential minimums,
1472 # ordered by arrival time, with the window minimum at s[0]
1473 # and the newest value at s[-1].
1474 s = deque()
1475
1476 for index, value in enumerate(iterator):
1477 if s and s[0][0] == index - maxlen:
1478 s.popleft()
1479 while s and value < s[-1][1]:
1480 s.pop()
1481 s.append((index, value))
1482 yield s[0][1]
1483
1484
1485def running_min(iterable, *, maxlen=None):
1486 """Smallest of values seen so far or values in a sliding window.
1487
1488 Set *maxlen* to a positive integer to specify the maximum size
1489 of the sliding window. The default of *None* is equivalent to
1490 an unbounded window.
1491
1492 For example:
1493
1494 >>> list(running_min([4, 3, 7, 0, 8, 1, 6, 2, 9, 5]))
1495 [4, 3, 3, 0, 0, 0, 0, 0, 0, 0]
1496
1497 >>> list(running_min([4, 3, 7, 0, 8, 1, 6, 2, 9, 5], maxlen=3))
1498 [4, 3, 3, 0, 0, 0, 1, 1, 2, 2]
1499
1500 Supports numeric types such as int, float, Decimal, and Fraction,
1501 but not complex numbers which are unorderable.
1502 """
1503
1504 iterator = iter(iterable)
1505
1506 if maxlen is None:
1507 return accumulate(iterator, func=min)
1508
1509 maxlen = _index(maxlen)
1510 if maxlen <= 0:
1511 raise ValueError('Window size should be positive')
1512
1513 return _windowed_running_min(iterator, maxlen)
1514
1515
1516def _windowed_running_max(iterator, maxlen):
1517 # Monotonically decreasing subsequence of potential maximums,
1518 # ordered by arrival time, with the window maximum at s[0]
1519 # and the newest value at s[-1].
1520 s = deque()
1521
1522 for index, value in enumerate(iterator):
1523 if s and s[0][0] == index - maxlen:
1524 s.popleft()
1525 while s and value > s[-1][1]:
1526 s.pop()
1527 s.append((index, value))
1528 yield s[0][1]
1529
1530
1531def running_max(iterable, *, maxlen=None):
1532 """Largest of values seen so far or values in a sliding window.
1533
1534 Set *maxlen* to a positive integer to specify the maximum size
1535 of the sliding window. The default of *None* is equivalent to
1536 an unbounded window.
1537
1538 For example:
1539
1540 >>> list(running_max([4, 3, 7, 0, 8, 1, 6, 2, 9, 5]))
1541 [4, 4, 7, 7, 8, 8, 8, 8, 9, 9]
1542
1543 >>> list(running_max([4, 3, 7, 0, 8, 1, 6, 2, 9, 5], maxlen=3))
1544 [4, 4, 7, 7, 8, 8, 8, 6, 9, 9]
1545
1546 Supports numeric types such as int, float, Decimal, and Fraction,
1547 but not complex numbers which are unorderable.
1548 """
1549
1550 iterator = iter(iterable)
1551
1552 if maxlen is None:
1553 return accumulate(iterator, func=max)
1554
1555 maxlen = _index(maxlen)
1556 if maxlen <= 0:
1557 raise ValueError('Window size should be positive')
1558
1559 return _windowed_running_max(iterator, maxlen)
1560
1561
1562@dataclass(frozen=True, slots=True)
1563class Stats:
1564 size: int
1565 minimum: float
1566 median: float
1567 maximum: float
1568 mean: float
1569
1570
1571def running_statistics(iterable, *, maxlen=None):
1572 """Statistics for values seen so far or values in a sliding window.
1573
1574 Set *maxlen* to a positive integer to specify the maximum size
1575 of the sliding window. The default of *None* is equivalent to
1576 an unbounded window.
1577
1578 Yields instances of a ``Stats`` dataclass with fields for the dataset *size*,
1579 *minimum* value, *median* value, *maximum* value, and the arithmetic *mean*.
1580
1581 Supports numeric types such as int, float, Decimal, and Fraction,
1582 but not complex numbers which are unorderable.
1583 """
1584
1585 if maxlen is not None:
1586 maxlen = _index(maxlen)
1587
1588 # fmt: off
1589 t0, t1, t2, t3 = tee(iterable, 4)
1590 return map(
1591 Stats,
1592 count(1) if maxlen is None else chain(range(1, maxlen), repeat(maxlen)),
1593 running_min(t0, maxlen=maxlen),
1594 running_median(t1, maxlen=maxlen),
1595 running_max(t2, maxlen=maxlen),
1596 running_mean(t3, maxlen=maxlen),
1597 )
1598 # fmt: on
1599
1600
1601def random_derangement(iterable):
1602 """Return a random derangement of elements in the iterable.
1603
1604 Equivalent to but much faster than ``choice(list(derangements(iterable)))``.
1605
1606 """
1607 seq = tuple(iterable)
1608 if len(seq) < 2:
1609 if len(seq) == 0:
1610 return ()
1611 raise IndexError('No derangments to choose from')
1612 perm = list(range(len(seq)))
1613 start = tuple(perm)
1614 while True:
1615 shuffle(perm)
1616 if not any(map(is_, start, perm)):
1617 return itemgetter(*perm)(seq)