Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/more_itertools/recipes.py: 28%

Shortcuts on this page

r m x   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

425 statements  

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)