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