Debian Codegraph @

Doc/library/itertools.rst

raw
1 :mod:`!itertools` --- Functions creating iterators for efficient looping
2 ========================================================================
3
4 .. module:: itertools
5 :synopsis: Functions creating iterators for efficient looping.
6
7 .. moduleauthor:: Raymond Hettinger <[email protected]>
8 .. sectionauthor:: Raymond Hettinger <[email protected]>
9
10 .. testsetup::
11
12 from itertools import *
13 import collections
14 import math
15 import operator
16 import random
17
18 --------------
19
20 This module implements a number of :term:`iterator` building blocks inspired
21 by constructs from APL, Haskell, and SML. Each has been recast in a form
22 suitable for Python.
23
24 The module standardizes a core set of fast, memory efficient tools that are
25 useful by themselves or in combination. Together, they form an "iterator
26 algebra" making it possible to construct specialized tools succinctly and
27 efficiently in pure Python.
28
29 For instance, SML provides a tabulation tool: ``tabulate(f)`` which produces a
30 sequence ``f(0), f(1), ...``. The same effect can be achieved in Python
31 by combining :func:`map` and :func:`count` to form ``map(f, count())``.
32
33
34 **Infinite iterators:**
35
36 ================== ================= ================================================= =========================================
37 Iterator Arguments Results Example
38 ================== ================= ================================================= =========================================
39 :func:`count` [start[, step]] start, start+step, start+2*step, ... ``count(10) → 10 11 12 13 14 ...``
40 :func:`cycle` p p0, p1, ... plast, p0, p1, ... ``cycle('ABCD') → A B C D A B C D ...``
41 :func:`repeat` elem [,n] elem, elem, elem, ... endlessly or up to n times ``repeat(10, 3) → 10 10 10``
42 ================== ================= ================================================= =========================================
43
44 **Iterators terminating on the shortest input sequence:**
45
46 ============================ ============================ ================================================= =============================================================
47 Iterator Arguments Results Example
48 ============================ ============================ ================================================= =============================================================
49 :func:`accumulate` p [,func] p0, p0+p1, p0+p1+p2, ... ``accumulate([1,2,3,4,5]) → 1 3 6 10 15``
50 :func:`batched` p, n (p0, p1, ..., p_n-1), ... ``batched('ABCDEFG', n=3) → ABC DEF G``
51 :func:`chain` p, q, ... p0, p1, ... plast, q0, q1, ... ``chain('ABC', 'DEF') → A B C D E F``
52 :func:`chain.from_iterable` iterable p0, p1, ... plast, q0, q1, ... ``chain.from_iterable(['ABC', 'DEF']) → A B C D E F``
53 :func:`compress` data, selectors (d[0] if s[0]), (d[1] if s[1]), ... ``compress('ABCDEF', [1,0,1,0,1,1]) → A C E F``
54 :func:`dropwhile` predicate, seq seq[n], seq[n+1], starting when predicate fails ``dropwhile(lambda x: x<5, [1,4,6,3,8]) → 6 3 8``
55 :func:`filterfalse` predicate, seq elements of seq where predicate(elem) fails ``filterfalse(lambda x: x<5, [1,4,6,3,8]) → 6 8``
56 :func:`groupby` iterable[, key] sub-iterators grouped by value of key(v) ``groupby(['A','B','DEF'], len) → (1, A B) (3, DEF)``
57 :func:`islice` seq, [start,] stop [, step] elements from seq[start:stop:step] ``islice('ABCDEFG', 2, None) → C D E F G``
58 :func:`pairwise` iterable (p[0], p[1]), (p[1], p[2]) ``pairwise('ABCDEFG') → AB BC CD DE EF FG``
59 :func:`starmap` func, seq func(\*seq[0]), func(\*seq[1]), ... ``starmap(pow, [(2,5), (3,2), (10,3)]) → 32 9 1000``
60 :func:`takewhile` predicate, seq seq[0], seq[1], until predicate fails ``takewhile(lambda x: x<5, [1,4,6,3,8]) → 1 4``
61 :func:`tee` it, n it1, it2, ... itn splits one iterator into n
62 :func:`zip_longest` p, q, ... (p[0], q[0]), (p[1], q[1]), ... ``zip_longest('ABCD', 'xy', fillvalue='-') → Ax By C- D-``
63 ============================ ============================ ================================================= =============================================================
64
65 **Combinatoric iterators:**
66
67 ============================================== ==================== =============================================================
68 Iterator Arguments Results
69 ============================================== ==================== =============================================================
70 :func:`product` p, q, ... [repeat=1] cartesian product, equivalent to a nested for-loop
71 :func:`permutations` p[, r] r-length tuples, all possible orderings, no repeated elements
72 :func:`combinations` p, r r-length tuples, in sorted order, no repeated elements
73 :func:`combinations_with_replacement` p, r r-length tuples, in sorted order, with repeated elements
74 ============================================== ==================== =============================================================
75
76 ============================================== =============================================================
77 Examples Results
78 ============================================== =============================================================
79 ``product('ABCD', repeat=2)`` ``AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD``
80 ``permutations('ABCD', 2)`` ``AB AC AD BA BC BD CA CB CD DA DB DC``
81 ``combinations('ABCD', 2)`` ``AB AC AD BC BD CD``
82 ``combinations_with_replacement('ABCD', 2)`` ``AA AB AC AD BB BC BD CC CD DD``
83 ============================================== =============================================================
84
85
86 .. _itertools-functions:
87
88 Itertool Functions
89 ------------------
90
91 The following functions all construct and return iterators. Some provide
92 streams of infinite length, so they should only be accessed by functions or
93 loops that truncate the stream.
94
95
96 .. function:: accumulate(iterable[, function, *, initial=None])
97
98 Make an iterator that returns accumulated sums or accumulated
99 results from other binary functions.
100
101 The *function* defaults to addition. The *function* should accept
102 two arguments, an accumulated total and a value from the *iterable*.
103
104 If an *initial* value is provided, the accumulation will start with
105 that value and the output will have one more element than the input
106 iterable.
107
108 Roughly equivalent to::
109
110 def accumulate(iterable, function=operator.add, *, initial=None):
111 'Return running totals'
112 # accumulate([1,2,3,4,5]) → 1 3 6 10 15
113 # accumulate([1,2,3,4,5], initial=100) → 100 101 103 106 110 115
114 # accumulate([1,2,3,4,5], operator.mul) → 1 2 6 24 120
115
116 iterator = iter(iterable)
117 total = initial
118 if initial is None:
119 try:
120 total = next(iterator)
121 except StopIteration:
122 return
123
124 yield total
125 for element in iterator:
126 total = function(total, element)
127 yield total
128
129 To compute a running minimum, set *function* to :func:`min`.
130 For a running maximum, set *function* to :func:`max`.
131 Or for a running product, set *function* to :func:`operator.mul`.
132 To build an `amortization table
133 <https://www.ramseysolutions.com/real-estate/amortization-schedule>`_,
134 accumulate the interest and apply payments:
135
136 .. doctest::
137
138 >>> data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8]
139 >>> list(accumulate(data, max)) # running maximum
140 [3, 4, 6, 6, 6, 9, 9, 9, 9, 9]
141 >>> list(accumulate(data, operator.mul)) # running product
142 [3, 12, 72, 144, 144, 1296, 0, 0, 0, 0]
143
144 # Amortize a 5% loan of 1000 with 10 annual payments of 90
145 >>> update = lambda balance, payment: round(balance * 1.05) - payment
146 >>> list(accumulate(repeat(90, 10), update, initial=1_000))
147 [1000, 960, 918, 874, 828, 779, 728, 674, 618, 559, 497]
148
149 See :func:`functools.reduce` for a similar function that returns only the
150 final accumulated value.
151
152 .. versionadded:: 3.2
153
154 .. versionchanged:: 3.3
155 Added the optional *function* parameter.
156
157 .. versionchanged:: 3.8
158 Added the optional *initial* parameter.
159
160
161 .. function:: batched(iterable, n, *, strict=False)
162
163 Batch data from the *iterable* into tuples of length *n*. The last
164 batch may be shorter than *n*.
165
166 If *strict* is true, will raise a :exc:`ValueError` if the final
167 batch is shorter than *n*.
168
169 Loops over the input iterable and accumulates data into tuples up to
170 size *n*. The input is consumed lazily, just enough to fill a batch.
171 The result is yielded as soon as the batch is full or when the input
172 iterable is exhausted:
173
174 .. doctest::
175
176 >>> flattened_data = ['roses', 'red', 'violets', 'blue', 'sugar', 'sweet']
177 >>> unflattened = list(batched(flattened_data, 2))
178 >>> unflattened
179 [('roses', 'red'), ('violets', 'blue'), ('sugar', 'sweet')]
180
181 Roughly equivalent to::
182
183 def batched(iterable, n, *, strict=False):
184 # batched('ABCDEFG', 3) → ABC DEF G
185 if n < 1:
186 raise ValueError('n must be at least one')
187 iterator = iter(iterable)
188 while batch := tuple(islice(iterator, n)):
189 if strict and len(batch) != n:
190 raise ValueError('batched(): incomplete batch')
191 yield batch
192
193 .. versionadded:: 3.12
194
195 .. versionchanged:: 3.13
196 Added the *strict* option.
197
198
199 .. function:: chain(*iterables)
200
201 Make an iterator that returns elements from the first iterable until
202 it is exhausted, then proceeds to the next iterable, until all of the
203 iterables are exhausted. This combines multiple data sources into a
204 single iterator. Roughly equivalent to::
205
206 def chain(*iterables):
207 # chain('ABC', 'DEF') → A B C D E F
208 for iterable in iterables:
209 yield from iterable
210
211
212 .. classmethod:: chain.from_iterable(iterable)
213
214 Alternate constructor for :func:`chain`. Gets chained inputs from a
215 single iterable argument that is evaluated lazily. Roughly equivalent to::
216
217 def from_iterable(iterables):
218 # chain.from_iterable(['ABC', 'DEF']) → A B C D E F
219 for iterable in iterables:
220 yield from iterable
221
222
223 .. function:: combinations(iterable, r)
224
225 Return *r* length subsequences of elements from the input *iterable*.
226
227 The output is a subsequence of :func:`product` keeping only entries that
228 are subsequences of the *iterable*. The length of the output is given
229 by :func:`math.comb` which computes ``n! / r! / (n - r)!`` when ``0 ≤ r
230 ≤ n`` or zero when ``r > n``.
231
232 The combination tuples are emitted in lexicographic order according to
233 the order of the input *iterable*. If the input *iterable* is sorted,
234 the output tuples will be produced in sorted order.
235
236 Elements are treated as unique based on their position, not on their
237 value. If the input elements are unique, there will be no repeated
238 values within each combination.
239
240 Roughly equivalent to::
241
242 def combinations(iterable, r):
243 # combinations('ABCD', 2) → AB AC AD BC BD CD
244 # combinations(range(4), 3) → 012 013 023 123
245
246 pool = tuple(iterable)
247 n = len(pool)
248 if r > n:
249 return
250 indices = list(range(r))
251
252 yield tuple(pool[i] for i in indices)
253 while True:
254 for i in reversed(range(r)):
255 if indices[i] != i + n - r:
256 break
257 else:
258 return
259 indices[i] += 1
260 for j in range(i+1, r):
261 indices[j] = indices[j-1] + 1
262 yield tuple(pool[i] for i in indices)
263
264
265 .. function:: combinations_with_replacement(iterable, r)
266
267 Return *r* length subsequences of elements from the input *iterable*
268 allowing individual elements to be repeated more than once.
269
270 The output is a subsequence of :func:`product` that keeps only entries
271 that are subsequences (with possible repeated elements) of the
272 *iterable*. The number of subsequence returned is ``(n + r - 1)! / r! /
273 (n - 1)!`` when ``n > 0``.
274
275 The combination tuples are emitted in lexicographic order according to
276 the order of the input *iterable*. if the input *iterable* is sorted,
277 the output tuples will be produced in sorted order.
278
279 Elements are treated as unique based on their position, not on their
280 value. If the input elements are unique, the generated combinations
281 will also be unique.
282
283 Roughly equivalent to::
284
285 def combinations_with_replacement(iterable, r):
286 # combinations_with_replacement('ABC', 2) → AA AB AC BB BC CC
287
288 pool = tuple(iterable)
289 n = len(pool)
290 if not n and r:
291 return
292 indices = [0] * r
293
294 yield tuple(pool[i] for i in indices)
295 while True:
296 for i in reversed(range(r)):
297 if indices[i] != n - 1:
298 break
299 else:
300 return
301 indices[i:] = [indices[i] + 1] * (r - i)
302 yield tuple(pool[i] for i in indices)
303
304 .. versionadded:: 3.1
305
306
307 .. function:: compress(data, selectors)
308
309 Make an iterator that returns elements from *data* where the
310 corresponding element in *selectors* is true. Stops when either the
311 *data* or *selectors* iterables have been exhausted. Roughly
312 equivalent to::
313
314 def compress(data, selectors):
315 # compress('ABCDEF', [1,0,1,0,1,1]) → A C E F
316 return (datum for datum, selector in zip(data, selectors) if selector)
317
318 .. versionadded:: 3.1
319
320
321 .. function:: count(start=0, step=1)
322
323 Make an iterator that returns evenly spaced values beginning with
324 *start*. Can be used with :func:`map` to generate consecutive data
325 points or with :func:`zip` to add sequence numbers. Roughly
326 equivalent to::
327
328 def count(start=0, step=1):
329 # count(10) → 10 11 12 13 14 ...
330 # count(2.5, 0.5) → 2.5 3.0 3.5 ...
331 n = start
332 while True:
333 yield n
334 n += step
335
336 When counting with floating-point numbers, better accuracy can sometimes be
337 achieved by substituting multiplicative code such as: ``(start + step * i
338 for i in count())``.
339
340 .. versionchanged:: 3.1
341 Added *step* argument and allowed non-integer arguments.
342
343
344 .. function:: cycle(iterable)
345
346 Make an iterator returning elements from the *iterable* and saving a
347 copy of each. When the iterable is exhausted, return elements from
348 the saved copy. Repeats indefinitely. Roughly equivalent to::
349
350 def cycle(iterable):
351 # cycle('ABCD') → A B C D A B C D A B C D ...
352
353 saved = []
354 for element in iterable:
355 yield element
356 saved.append(element)
357
358 while saved:
359 for element in saved:
360 yield element
361
362 This itertool may require significant auxiliary storage (depending on
363 the length of the iterable).
364
365
366 .. function:: dropwhile(predicate, iterable)
367
368 Make an iterator that drops elements from the *iterable* while the
369 *predicate* is true and afterwards returns every element. Roughly
370 equivalent to::
371
372 def dropwhile(predicate, iterable):
373 # dropwhile(lambda x: x<5, [1,4,6,3,8]) → 6 3 8
374
375 iterator = iter(iterable)
376 for x in iterator:
377 if not predicate(x):
378 yield x
379 break
380
381 for x in iterator:
382 yield x
383
384 Note this does not produce *any* output until the predicate first
385 becomes false, so this itertool may have a lengthy start-up time.
386
387
388 .. function:: filterfalse(predicate, iterable)
389
390 Make an iterator that filters elements from the *iterable* returning
391 only those for which the *predicate* returns a false value. If
392 *predicate* is ``None``, returns the items that are false. Roughly
393 equivalent to::
394
395 def filterfalse(predicate, iterable):
396 # filterfalse(lambda x: x<5, [1,4,6,3,8]) → 6 8
397
398 if predicate is None:
399 predicate = bool
400
401 for x in iterable:
402 if not predicate(x):
403 yield x
404
405
406 .. function:: groupby(iterable, key=None)
407
408 Make an iterator that returns consecutive keys and groups from the *iterable*.
409 The *key* is a function computing a key value for each element. If not
410 specified or is ``None``, *key* defaults to an identity function and returns
411 the element unchanged. Generally, the iterable needs to already be sorted on
412 the same key function.
413
414 The operation of :func:`groupby` is similar to the ``uniq`` filter in Unix. It
415 generates a break or new group every time the value of the key function changes
416 (which is why it is usually necessary to have sorted the data using the same key
417 function). That behavior differs from SQL's GROUP BY which aggregates common
418 elements regardless of their input order.
419
420 The returned group is itself an iterator that shares the underlying iterable
421 with :func:`groupby`. Because the source is shared, when the :func:`groupby`
422 object is advanced, the previous group is no longer visible. So, if that data
423 is needed later, it should be stored as a list::
424
425 groups = []
426 uniquekeys = []
427 data = sorted(data, key=keyfunc)
428 for k, g in groupby(data, keyfunc):
429 groups.append(list(g)) # Store group iterator as a list
430 uniquekeys.append(k)
431
432 :func:`groupby` is roughly equivalent to::
433
434 def groupby(iterable, key=None):
435 # [k for k, g in groupby('AAAABBBCCDAABBB')] → A B C D A B
436 # [list(g) for k, g in groupby('AAAABBBCCD')] → AAAA BBB CC D
437
438 keyfunc = (lambda x: x) if key is None else key
439 iterator = iter(iterable)
440 exhausted = False
441
442 def _grouper(target_key):
443 nonlocal curr_value, curr_key, exhausted
444 yield curr_value
445 for curr_value in iterator:
446 curr_key = keyfunc(curr_value)
447 if curr_key != target_key:
448 return
449 yield curr_value
450 exhausted = True
451
452 try:
453 curr_value = next(iterator)
454 except StopIteration:
455 return
456 curr_key = keyfunc(curr_value)
457
458 while not exhausted:
459 target_key = curr_key
460 curr_group = _grouper(target_key)
461 yield curr_key, curr_group
462 if curr_key == target_key:
463 for _ in curr_group:
464 pass
465
466
467 .. function:: islice(iterable, stop)
468 islice(iterable, start, stop[, step])
469
470 Make an iterator that returns selected elements from the iterable.
471 Works like sequence slicing but does not support negative values for
472 *start*, *stop*, or *step*.
473
474 If *start* is zero or ``None``, iteration starts at zero. Otherwise,
475 elements from the iterable are skipped until *start* is reached.
476
477 If *stop* is ``None``, iteration continues until the input is
478 exhausted, if at all. Otherwise, it stops at the specified position.
479
480 If *step* is ``None``, the step defaults to one. Elements are returned
481 consecutively unless *step* is set higher than one which results in
482 items being skipped.
483
484 Roughly equivalent to::
485
486 def islice(iterable, *args):
487 # islice('ABCDEFG', 2) → A B
488 # islice('ABCDEFG', 2, 4) → C D
489 # islice('ABCDEFG', 2, None) → C D E F G
490 # islice('ABCDEFG', 0, None, 2) → A C E G
491
492 s = slice(*args)
493 start = 0 if s.start is None else s.start
494 stop = s.stop
495 step = 1 if s.step is None else s.step
496 if start < 0 or (stop is not None and stop < 0) or step <= 0:
497 raise ValueError
498
499 indices = count() if stop is None else range(max(start, stop))
500 next_i = start
501 for i, element in zip(indices, iterable):
502 if i == next_i:
503 yield element
504 next_i += step
505
506 If the input is an iterator, then fully consuming the *islice*
507 advances the input iterator by ``max(start, stop)`` steps regardless
508 of the *step* value.
509
510
511 .. function:: pairwise(iterable)
512
513 Return successive overlapping pairs taken from the input *iterable*.
514
515 The number of 2-tuples in the output iterator will be one fewer than the
516 number of inputs. It will be empty if the input iterable has fewer than
517 two values.
518
519 Roughly equivalent to::
520
521 def pairwise(iterable):
522 # pairwise('ABCDEFG') → AB BC CD DE EF FG
523
524 iterator = iter(iterable)
525 a = next(iterator, None)
526
527 for b in iterator:
528 yield a, b
529 a = b
530
531 .. versionadded:: 3.10
532
533
534 .. function:: permutations(iterable, r=None)
535
536 Return successive *r* length `permutations of elements
537 <https://www.britannica.com/science/permutation>`_ from the *iterable*.
538
539 If *r* is not specified or is ``None``, then *r* defaults to the length
540 of the *iterable* and all possible full-length permutations
541 are generated.
542
543 The output is a subsequence of :func:`product` where entries with
544 repeated elements have been filtered out. The length of the output is
545 given by :func:`math.perm` which computes ``n! / (n - r)!`` when
546 ``0 ≤ r ≤ n`` or zero when ``r > n``.
547
548 The permutation tuples are emitted in lexicographic order according to
549 the order of the input *iterable*. If the input *iterable* is sorted,
550 the output tuples will be produced in sorted order.
551
552 Elements are treated as unique based on their position, not on their
553 value. If the input elements are unique, there will be no repeated
554 values within a permutation.
555
556 Roughly equivalent to::
557
558 def permutations(iterable, r=None):
559 # permutations('ABCD', 2) → AB AC AD BA BC BD CA CB CD DA DB DC
560 # permutations(range(3)) → 012 021 102 120 201 210
561
562 pool = tuple(iterable)
563 n = len(pool)
564 r = n if r is None else r
565 if r > n:
566 return
567
568 indices = list(range(n))
569 cycles = list(range(n, n-r, -1))
570 yield tuple(pool[i] for i in indices[:r])
571
572 while n:
573 for i in reversed(range(r)):
574 cycles[i] -= 1
575 if cycles[i] == 0:
576 indices[i:] = indices[i+1:] + indices[i:i+1]
577 cycles[i] = n - i
578 else:
579 j = cycles[i]
580 indices[i], indices[-j] = indices[-j], indices[i]
581 yield tuple(pool[i] for i in indices[:r])
582 break
583 else:
584 return
585
586
587 .. function:: product(*iterables, repeat=1)
588
589 `Cartesian product <https://en.wikipedia.org/wiki/Cartesian_product>`_
590 of the input iterables.
591
592 Roughly equivalent to nested for-loops in a generator expression. For example,
593 ``product(A, B)`` returns the same as ``((x,y) for x in A for y in B)``.
594
595 The nested loops cycle like an odometer with the rightmost element advancing
596 on every iteration. This pattern creates a lexicographic ordering so that if
597 the input's iterables are sorted, the product tuples are emitted in sorted
598 order.
599
600 To compute the product of an iterable with itself, specify the number of
601 repetitions with the optional *repeat* keyword argument. For example,
602 ``product(A, repeat=4)`` means the same as ``product(A, A, A, A)``.
603
604 This function is roughly equivalent to the following code, except that the
605 actual implementation does not build up intermediate results in memory::
606
607 def product(*iterables, repeat=1):
608 # product('ABCD', 'xy') → Ax Ay Bx By Cx Cy Dx Dy
609 # product(range(2), repeat=3) → 000 001 010 011 100 101 110 111
610
611 if repeat < 0:
612 raise ValueError('repeat argument cannot be negative')
613 pools = [tuple(pool) for pool in iterables] * repeat
614
615 result = [[]]
616 for pool in pools:
617 result = [x+[y] for x in result for y in pool]
618
619 for prod in result:
620 yield tuple(prod)
621
622 Before :func:`product` runs, it completely consumes the input iterables,
623 keeping pools of values in memory to generate the products. Accordingly,
624 it is only useful with finite inputs.
625
626
627 .. function:: repeat(object[, times])
628
629 Make an iterator that returns *object* over and over again. Runs indefinitely
630 unless the *times* argument is specified.
631
632 Roughly equivalent to::
633
634 def repeat(object, times=None):
635 # repeat(10, 3) → 10 10 10
636 if times is None:
637 while True:
638 yield object
639 else:
640 for i in range(times):
641 yield object
642
643 A common use for *repeat* is to supply a stream of constant values to *map*
644 or *zip*:
645
646 .. doctest::
647
648 >>> list(map(pow, range(10), repeat(2)))
649 [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
650
651
652 .. function:: starmap(function, iterable)
653
654 Make an iterator that computes the *function* using arguments obtained
655 from the *iterable*. Used instead of :func:`map` when argument
656 parameters have already been "pre-zipped" into tuples.
657
658 The difference between :func:`map` and :func:`starmap` parallels the
659 distinction between ``function(a,b)`` and ``function(*c)``. Roughly
660 equivalent to::
661
662 def starmap(function, iterable):
663 # starmap(pow, [(2,5), (3,2), (10,3)]) → 32 9 1000
664 for args in iterable:
665 yield function(*args)
666
667
668 .. function:: takewhile(predicate, iterable)
669
670 Make an iterator that returns elements from the *iterable* as long as
671 the *predicate* is true. Roughly equivalent to::
672
673 def takewhile(predicate, iterable):
674 # takewhile(lambda x: x<5, [1,4,6,3,8]) → 1 4
675 for x in iterable:
676 if not predicate(x):
677 break
678 yield x
679
680 Note, the element that first fails the predicate condition is
681 consumed from the input iterator and there is no way to access it.
682 This could be an issue if an application wants to further consume the
683 input iterator after *takewhile* has been run to exhaustion. To work
684 around this problem, consider using `more-itertools before_and_after()
685 <https://more-itertools.readthedocs.io/en/stable/api.html#more_itertools.before_and_after>`_
686 instead.
687
688
689 .. function:: tee(iterable, n=2)
690
691 Return *n* independent iterators from a single iterable.
692
693 Roughly equivalent to::
694
695 def tee(iterable, n=2):
696 if n < 0:
697 raise ValueError
698 if n == 0:
699 return ()
700 iterator = _tee(iterable)
701 result = [iterator]
702 for _ in range(n - 1):
703 result.append(_tee(iterator))
704 return tuple(result)
705
706 class _tee:
707
708 def __init__(self, iterable):
709 it = iter(iterable)
710 if isinstance(it, _tee):
711 self.iterator = it.iterator
712 self.link = it.link
713 else:
714 self.iterator = it
715 self.link = [None, None]
716
717 def __iter__(self):
718 return self
719
720 def __next__(self):
721 link = self.link
722 if link[1] is None:
723 link[0] = next(self.iterator)
724 link[1] = [None, None]
725 value, self.link = link
726 return value
727
728 When the input *iterable* is already a tee iterator object, all
729 members of the return tuple are constructed as if they had been
730 produced by the upstream :func:`tee` call. This "flattening step"
731 allows nested :func:`tee` calls to share the same underlying data
732 chain and to have a single update step rather than a chain of calls.
733
734 The flattening property makes tee iterators efficiently peekable:
735
736 .. testcode::
737
738 def lookahead(tee_iterator):
739 "Return the next value without moving the input forward"
740 [forked_iterator] = tee(tee_iterator, 1)
741 return next(forked_iterator)
742
743 .. doctest::
744
745 >>> iterator = iter('abcdef')
746 >>> [iterator] = tee(iterator, 1) # Make the input peekable
747 >>> next(iterator) # Move the iterator forward
748 'a'
749 >>> lookahead(iterator) # Check next value
750 'b'
751 >>> next(iterator) # Continue moving forward
752 'b'
753
754 ``tee`` iterators are not threadsafe. A :exc:`RuntimeError` may be
755 raised when simultaneously using iterators returned by the same :func:`tee`
756 call, even if the original *iterable* is threadsafe.
757
758 This itertool may require significant auxiliary storage (depending on how
759 much temporary data needs to be stored). In general, if one iterator uses
760 most or all of the data before another iterator starts, it is faster to use
761 :func:`list` instead of :func:`tee`.
762
763
764 .. function:: zip_longest(*iterables, fillvalue=None)
765
766 Make an iterator that aggregates elements from each of the
767 *iterables*.
768
769 If the iterables are of uneven length, missing values are filled-in
770 with *fillvalue*. If not specified, *fillvalue* defaults to ``None``.
771
772 Iteration continues until the longest iterable is exhausted.
773
774 Roughly equivalent to::
775
776 def zip_longest(*iterables, fillvalue=None):
777 # zip_longest('ABCD', 'xy', fillvalue='-') → Ax By C- D-
778
779 iterators = list(map(iter, iterables))
780 num_active = len(iterators)
781 if not num_active:
782 return
783
784 while True:
785 values = []
786 for i, iterator in enumerate(iterators):
787 try:
788 value = next(iterator)
789 except StopIteration:
790 num_active -= 1
791 if not num_active:
792 return
793 iterators[i] = repeat(fillvalue)
794 value = fillvalue
795 values.append(value)
796 yield tuple(values)
797
798 If one of the iterables is potentially infinite, then the :func:`zip_longest`
799 function should be wrapped with something that limits the number of calls
800 (for example :func:`islice` or :func:`takewhile`).
801
802
803 .. _itertools-recipes:
804
805 Itertools Recipes
806 -----------------
807
808 This section shows recipes for creating an extended toolset using the existing
809 itertools as building blocks.
810
811 The primary purpose of the itertools recipes is educational. The recipes show
812 various ways of thinking about individual tools — for example, that
813 ``chain.from_iterable`` is related to the concept of flattening. The recipes
814 also give ideas about ways that the tools can be combined — for example, how
815 ``starmap()`` and ``repeat()`` can work together. The recipes also show patterns
816 for using itertools with the :mod:`operator` and :mod:`collections` modules as
817 well as with the built-in itertools such as ``map()``, ``filter()``,
818 ``reversed()``, and ``enumerate()``.
819
820 A secondary purpose of the recipes is to serve as an incubator. The
821 ``accumulate()``, ``compress()``, and ``pairwise()`` itertools started out as
822 recipes. Currently, the ``sliding_window()``, ``iter_index()``, and ``sieve()``
823 recipes are being tested to see whether they prove their worth.
824
825 Substantially all of these recipes and many, many others can be installed from
826 the :pypi:`more-itertools` project found
827 on the Python Package Index::
828
829 python -m pip install more-itertools
830
831 Many of the recipes offer the same high performance as the underlying toolset.
832 Superior memory performance is kept by processing elements one at a time rather
833 than bringing the whole iterable into memory all at once. Code volume is kept
834 small by linking the tools together in a `functional style
835 <https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf>`_. High speed
836 is retained by preferring "vectorized" building blocks over the use of for-loops
837 and :term:`generators <generator>` which incur interpreter overhead.
838
839 .. testcode::
840
841 from collections import Counter, deque
842 from contextlib import suppress
843 from functools import reduce
844 from math import comb, prod, sumprod, isqrt
845 from operator import itemgetter, getitem, mul, neg, truediv
846
847 def take(n, iterable):
848 "Return first n items of the iterable as a list."
849 return list(islice(iterable, n))
850
851 def prepend(value, iterable):
852 "Prepend a single value in front of an iterable."
853 # prepend(1, [2, 3, 4]) → 1 2 3 4
854 return chain([value], iterable)
855
856 def running_mean(iterable):
857 "Yield the average of all values seen so far."
858 # running_mean([8.5, 9.5, 7.5, 6.5]) → 8.5 9.0 8.5 8.0
859 return map(truediv, accumulate(iterable), count(1))
860
861 def repeatfunc(function, times=None, *args):
862 "Repeat calls to a function with specified arguments."
863 if times is None:
864 return starmap(function, repeat(args))
865 return starmap(function, repeat(args, times))
866
867 def flatten(list_of_lists):
868 "Flatten one level of nesting."
869 return chain.from_iterable(list_of_lists)
870
871 def ncycles(iterable, n):
872 "Returns the sequence elements n times."
873 return chain.from_iterable(repeat(tuple(iterable), n))
874
875 def loops(n):
876 "Loop n times. Like range(n) but without creating integers."
877 # for _ in loops(100): ...
878 return repeat(None, n)
879
880 def tail(n, iterable):
881 "Return an iterator over the last n items."
882 # tail(3, 'ABCDEFG') → E F G
883 return iter(deque(iterable, maxlen=n))
884
885 def consume(iterator, n=None):
886 "Advance the iterator n-steps ahead. If n is None, consume entirely."
887 # Use functions that consume iterators at C speed.
888 if n is None:
889 deque(iterator, maxlen=0)
890 else:
891 next(islice(iterator, n, n), None)
892
893 def nth(iterable, n, default=None):
894 "Returns the nth item or a default value."
895 return next(islice(iterable, n, None), default)
896
897 def quantify(iterable, predicate=bool):
898 "Given a predicate that returns True or False, count the True results."
899 return sum(map(predicate, iterable))
900
901 def first_true(iterable, default=False, predicate=None):
902 "Returns the first true value or the *default* if there is no true value."
903 # first_true([a,b,c], x) → a or b or c or x
904 # first_true([a,b], x, f) → a if f(a) else b if f(b) else x
905 return next(filter(predicate, iterable), default)
906
907 def all_equal(iterable, key=None):
908 "Returns True if all the elements are equal to each other."
909 # all_equal('4٤௪౪໔', key=int) → True
910 return len(take(2, groupby(iterable, key))) <= 1
911
912 def unique_justseen(iterable, key=None):
913 "Yield unique elements, preserving order. Remember only the element just seen."
914 # unique_justseen('AAAABBBCCDAABBB') → A B C D A B
915 # unique_justseen('ABBcCAD', str.casefold) → A B c A D
916 if key is None:
917 return map(itemgetter(0), groupby(iterable))
918 return map(next, map(itemgetter(1), groupby(iterable, key)))
919
920 def unique_everseen(iterable, key=None):
921 "Yield unique elements, preserving order. Remember all elements ever seen."
922 # unique_everseen('AAAABBBCCDAABBB') → A B C D
923 # unique_everseen('ABBcCAD', str.casefold) → A B c D
924 seen = set()
925 if key is None:
926 for element in filterfalse(seen.__contains__, iterable):
927 seen.add(element)
928 yield element
929 else:
930 for element in iterable:
931 k = key(element)
932 if k not in seen:
933 seen.add(k)
934 yield element
935
936 def unique(iterable, key=None, reverse=False):
937 "Yield unique elements in sorted order. Supports unhashable inputs."
938 # unique([[1, 2], [3, 4], [1, 2]]) → [1, 2] [3, 4]
939 sequenced = sorted(iterable, key=key, reverse=reverse)
940 return unique_justseen(sequenced, key=key)
941
942 def sliding_window(iterable, n):
943 "Collect data into overlapping fixed-length chunks or blocks."
944 # sliding_window('ABCDEFG', 4) → ABCD BCDE CDEF DEFG
945 iterator = iter(iterable)
946 window = deque(islice(iterator, n - 1), maxlen=n)
947 for x in iterator:
948 window.append(x)
949 yield tuple(window)
950
951 def grouper(iterable, n, *, incomplete='fill', fillvalue=None):
952 "Collect data into non-overlapping fixed-length chunks or blocks."
953 # grouper('ABCDEFG', 3, fillvalue='x') → ABC DEF Gxx
954 # grouper('ABCDEFG', 3, incomplete='strict') → ABC DEF ValueError
955 # grouper('ABCDEFG', 3, incomplete='ignore') → ABC DEF
956 iterators = [iter(iterable)] * n
957 match incomplete:
958 case 'fill':
959 return zip_longest(*iterators, fillvalue=fillvalue)
960 case 'strict':
961 return zip(*iterators, strict=True)
962 case 'ignore':
963 return zip(*iterators)
964 case _:
965 raise ValueError('Expected fill, strict, or ignore')
966
967 def roundrobin(*iterables):
968 "Visit input iterables in a cycle until each is exhausted."
969 # roundrobin('ABC', 'D', 'EF') → A D E B F C
970 # Algorithm credited to George Sakkis
971 iterators = map(iter, iterables)
972 for num_active in range(len(iterables), 0, -1):
973 iterators = cycle(islice(iterators, num_active))
974 yield from map(next, iterators)
975
976 def subslices(seq):
977 "Return all contiguous non-empty subslices of a sequence."
978 # subslices('ABCD') → A AB ABC ABCD B BC BCD C CD D
979 slices = starmap(slice, combinations(range(len(seq) + 1), 2))
980 return map(getitem, repeat(seq), slices)
981
982 def iter_index(iterable, value, start=0, stop=None):
983 "Return indices where a value occurs in a sequence or iterable."
984 # iter_index('AABCADEAF', 'A') → 0 1 4 7
985 seq_index = getattr(iterable, 'index', None)
986 if seq_index is None:
987 iterator = islice(iterable, start, stop)
988 for i, element in enumerate(iterator, start):
989 if element is value or element == value:
990 yield i
991 else:
992 stop = len(iterable) if stop is None else stop
993 i = start
994 with suppress(ValueError):
995 while True:
996 yield (i := seq_index(value, i, stop))
997 i += 1
998
999 def iter_except(function, exception, first=None):
1000 "Convert a call-until-exception interface to an iterator interface."
1001 # iter_except(d.popitem, KeyError) → non-blocking dictionary iterator
1002 with suppress(exception):
1003 if first is not None:
1004 yield first()
1005 while True:
1006 yield function()
1007
1008
1009 The following recipes have a more mathematical flavor:
1010
1011 .. testcode::
1012
1013 def multinomial(*counts):
1014 "Number of distinct arrangements of a multiset."
1015 # Counter('abracadabra').values() → 5 2 2 1 1
1016 # multinomial(5, 2, 2, 1, 1) → 83160
1017 return prod(map(comb, accumulate(counts), counts))
1018
1019 def powerset(iterable):
1020 "Subsequences of the iterable from shortest to longest."
1021 # powerset([1,2,3]) → () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)
1022 s = list(iterable)
1023 return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
1024
1025 def sum_of_squares(iterable):
1026 "Add up the squares of the input values."
1027 # sum_of_squares([10, 20, 30]) → 1400
1028 return sumprod(*tee(iterable))
1029
1030 def reshape(matrix, columns):
1031 "Reshape a 2-D matrix to have a given number of columns."
1032 # reshape([(0, 1), (2, 3), (4, 5)], 3) → (0, 1, 2), (3, 4, 5)
1033 return batched(chain.from_iterable(matrix), columns, strict=True)
1034
1035 def transpose(matrix):
1036 "Swap the rows and columns of a 2-D matrix."
1037 # transpose([(1, 2, 3), (11, 22, 33)]) → (1, 11) (2, 22) (3, 33)
1038 return zip(*matrix, strict=True)
1039
1040 def matmul(m1, m2):
1041 "Multiply two matrices."
1042 # matmul([(7, 5), (3, 5)], [(2, 5), (7, 9)]) → (49, 80), (41, 60)
1043 n = len(m2[0])
1044 return batched(starmap(sumprod, product(m1, transpose(m2))), n)
1045
1046 def convolve(signal, kernel):
1047 """Discrete linear convolution of two iterables.
1048 Equivalent to polynomial multiplication.
1049
1050 Convolutions are mathematically commutative; however, the inputs are
1051 evaluated differently. The signal is consumed lazily and can be
1052 infinite. The kernel is fully consumed before the calculations begin.
1053
1054 Article: https://betterexplained.com/articles/intuitive-convolution/
1055 Video: https://www.youtube.com/watch?v=KuXjwB4LzSA
1056 """
1057 # convolve([1, -1, -20], [1, -3]) → 1 -4 -17 60
1058 # convolve(data, [0.25, 0.25, 0.25, 0.25]) → Moving average (blur)
1059 # convolve(data, [1/2, 0, -1/2]) → 1st derivative estimate
1060 # convolve(data, [1, -2, 1]) → 2nd derivative estimate
1061 kernel = tuple(kernel)[::-1]
1062 n = len(kernel)
1063 padded_signal = chain(repeat(0, n-1), signal, repeat(0, n-1))
1064 windowed_signal = sliding_window(padded_signal, n)
1065 return map(sumprod, repeat(kernel), windowed_signal)
1066
1067 def polynomial_from_roots(roots):
1068 """Compute a polynomial's coefficients from its roots.
1069
1070 (x - 5) (x + 4) (x - 3) expands to: x³ -4x² -17x + 60
1071 """
1072 # polynomial_from_roots([5, -4, 3]) → [1, -4, -17, 60]
1073 factors = zip(repeat(1), map(neg, roots))
1074 return list(reduce(convolve, factors, [1]))
1075
1076 def polynomial_eval(coefficients, x):
1077 """Evaluate a polynomial at a specific value.
1078
1079 Computes with better numeric stability than Horner's method.
1080 """
1081 # Evaluate x³ -4x² -17x + 60 at x = 5
1082 # polynomial_eval([1, -4, -17, 60], x=5) → 0
1083 n = len(coefficients)
1084 if not n:
1085 return type(x)(0)
1086 powers = map(pow, repeat(x), reversed(range(n)))
1087 return sumprod(coefficients, powers)
1088
1089 def polynomial_derivative(coefficients):
1090 """Compute the first derivative of a polynomial.
1091
1092 f(x) = x³ -4x² -17x + 60
1093 f'(x) = 3x² -8x -17
1094 """
1095 # polynomial_derivative([1, -4, -17, 60]) → [3, -8, -17]
1096 n = len(coefficients)
1097 powers = reversed(range(1, n))
1098 return list(map(mul, coefficients, powers))
1099
1100 def sieve(n):
1101 "Primes less than n."
1102 # sieve(30) → 2 3 5 7 11 13 17 19 23 29
1103 if n > 2:
1104 yield 2
1105 data = bytearray((0, 1)) * (n // 2)
1106 for p in iter_index(data, 1, start=3, stop=isqrt(n) + 1):
1107 data[p*p : n : p+p] = bytes(len(range(p*p, n, p+p)))
1108 yield from iter_index(data, 1, start=3)
1109
1110 def factor(n):
1111 "Prime factors of n."
1112 # factor(99) → 3 3 11
1113 # factor(1_000_000_000_000_007) → 47 59 360620266859
1114 # factor(1_000_000_000_000_403) → 1000000000000403
1115 for prime in sieve(isqrt(n) + 1):
1116 while not n % prime:
1117 yield prime
1118 n //= prime
1119 if n == 1:
1120 return
1121 if n > 1:
1122 yield n
1123
1124 def is_prime(n):
1125 "Return True if n is prime."
1126 # is_prime(1_000_000_000_000_403) → True
1127 return n > 1 and next(factor(n)) == n
1128
1129 def totient(n):
1130 "Count of natural numbers up to n that are coprime to n."
1131 # https://mathworld.wolfram.com/TotientFunction.html
1132 # totient(12) → 4 because len([1, 5, 7, 11]) == 4
1133 for prime in set(factor(n)):
1134 n -= n // prime
1135 return n
1136
1137
1138 .. doctest::
1139 :hide:
1140
1141 These examples no longer appear in the docs but are guaranteed
1142 to keep working.
1143
1144 >>> amounts = [120.15, 764.05, 823.14]
1145 >>> for checknum, amount in zip(count(1200), amounts):
1146 ... print('Check %d is for $%.2f' % (checknum, amount))
1147 ...
1148 Check 1200 is for $120.15
1149 Check 1201 is for $764.05
1150 Check 1202 is for $823.14
1151
1152 >>> import operator
1153 >>> for cube in map(operator.pow, range(1,4), repeat(3)):
1154 ... print(cube)
1155 ...
1156 1
1157 8
1158 27
1159
1160 >>> reportlines = ['EuroPython', 'Roster', '', 'alex', '', 'laura', '', 'martin', '', 'walter', '', 'samuele']
1161 >>> for name in islice(reportlines, 3, None, 2):
1162 ... print(name.title())
1163 ...
1164 Alex
1165 Laura
1166 Martin
1167 Walter
1168 Samuele
1169
1170 >>> from operator import itemgetter
1171 >>> d = dict(a=1, b=2, c=1, d=2, e=1, f=2, g=3)
1172 >>> di = sorted(sorted(d.items()), key=itemgetter(1))
1173 >>> for k, g in groupby(di, itemgetter(1)):
1174 ... print(k, list(map(itemgetter(0), g)))
1175 ...
1176 1 ['a', 'c', 'e']
1177 2 ['b', 'd', 'f']
1178 3 ['g']
1179
1180 # Find runs of consecutive numbers using groupby. The key to the solution
1181 # is differencing with a range so that consecutive numbers all appear in
1182 # same group.
1183 >>> data = [ 1, 4,5,6, 10, 15,16,17,18, 22, 25,26,27,28]
1184 >>> for k, g in groupby(enumerate(data), lambda t:t[0]-t[1]):
1185 ... print(list(map(operator.itemgetter(1), g)))
1186 ...
1187 [1]
1188 [4, 5, 6]
1189 [10]
1190 [15, 16, 17, 18]
1191 [22]
1192 [25, 26, 27, 28]
1193
1194 Now, we test all of the itertool recipes
1195
1196 >>> take(10, count())
1197 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
1198 >>> # Verify that the input is consumed lazily
1199 >>> it = iter('abcdef')
1200 >>> take(3, it)
1201 ['a', 'b', 'c']
1202 >>> list(it)
1203 ['d', 'e', 'f']
1204
1205
1206 >>> list(prepend(1, [2, 3, 4]))
1207 [1, 2, 3, 4]
1208
1209
1210 >>> list(enumerate('abc'))
1211 [(0, 'a'), (1, 'b'), (2, 'c')]
1212
1213
1214 >>> list(running_mean([8.5, 9.5, 7.5, 6.5]))
1215 [8.5, 9.0, 8.5, 8.0]
1216
1217
1218 >>> for _ in loops(5):
1219 ... print('hi')
1220 ...
1221 hi
1222 hi
1223 hi
1224 hi
1225 hi
1226
1227
1228 >>> list(tail(3, 'ABCDEFG'))
1229 ['E', 'F', 'G']
1230 >>> # Verify the input is consumed greedily
1231 >>> input_iterator = iter('ABCDEFG')
1232 >>> output_iterator = tail(3, input_iterator)
1233 >>> list(input_iterator)
1234 []
1235
1236
1237 >>> it = iter(range(10))
1238 >>> consume(it, 3)
1239 >>> # Verify the input is consumed lazily
1240 >>> next(it)
1241 3
1242 >>> # Verify the input is consumed completely
1243 >>> consume(it)
1244 >>> next(it, 'Done')
1245 'Done'
1246
1247
1248 >>> nth('abcde', 3)
1249 'd'
1250 >>> nth('abcde', 9) is None
1251 True
1252 >>> # Verify that the input is consumed lazily
1253 >>> it = iter('abcde')
1254 >>> nth(it, 2)
1255 'c'
1256 >>> list(it)
1257 ['d', 'e']
1258
1259
1260 >>> [all_equal(s) for s in ('', 'A', 'AAAA', 'AAAB', 'AAABA')]
1261 [True, True, True, False, False]
1262 >>> [all_equal(s, key=str.casefold) for s in ('', 'A', 'AaAa', 'AAAB', 'AAABA')]
1263 [True, True, True, False, False]
1264 >>> # Verify that the input is consumed lazily and that only
1265 >>> # one element of a second equivalence class is used to disprove
1266 >>> # the assertion that all elements are equal.
1267 >>> it = iter('aaabbbccc')
1268 >>> all_equal(it)
1269 False
1270 >>> ''.join(it)
1271 'bbccc'
1272
1273
1274 >>> quantify(range(99), lambda x: x%2==0)
1275 50
1276 >>> quantify([True, False, False, True, True])
1277 3
1278 >>> quantify(range(12), predicate=lambda x: x%2==1)
1279 6
1280
1281
1282 >>> a = [[1, 2, 3], [4, 5, 6]]
1283 >>> list(flatten(a))
1284 [1, 2, 3, 4, 5, 6]
1285
1286
1287 >>> list(ncycles('abc', 3))
1288 ['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c']
1289 >>> # Verify greedy consumption of input iterator
1290 >>> input_iterator = iter('abc')
1291 >>> output_iterator = ncycles(input_iterator, 3)
1292 >>> list(input_iterator)
1293 []
1294
1295
1296 >>> sum_of_squares([10, 20, 30])
1297 1400
1298
1299
1300 >>> list(reshape([(0, 1), (2, 3), (4, 5)], 3))
1301 [(0, 1, 2), (3, 4, 5)]
1302 >>> M = [(0, 1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11)]
1303 >>> list(reshape(M, 1))
1304 [(0,), (1,), (2,), (3,), (4,), (5,), (6,), (7,), (8,), (9,), (10,), (11,)]
1305 >>> list(reshape(M, 2))
1306 [(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11)]
1307 >>> list(reshape(M, 3))
1308 [(0, 1, 2), (3, 4, 5), (6, 7, 8), (9, 10, 11)]
1309 >>> list(reshape(M, 4))
1310 [(0, 1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11)]
1311 >>> list(reshape(M, 5))
1312 Traceback (most recent call last):
1313 ...
1314 ValueError: batched(): incomplete batch
1315 >>> list(reshape(M, 6))
1316 [(0, 1, 2, 3, 4, 5), (6, 7, 8, 9, 10, 11)]
1317 >>> list(reshape(M, 12))
1318 [(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)]
1319
1320
1321 >>> list(transpose([(1, 2, 3), (11, 22, 33)]))
1322 [(1, 11), (2, 22), (3, 33)]
1323 >>> # Verify that the inputs are consumed lazily
1324 >>> input1 = iter([1, 2, 3])
1325 >>> input2 = iter([11, 22, 33])
1326 >>> output_iterator = transpose([input1, input2])
1327 >>> next(output_iterator)
1328 (1, 11)
1329 >>> list(zip(input1, input2))
1330 [(2, 22), (3, 33)]
1331
1332
1333 >>> list(matmul([(7, 5), (3, 5)], [[2, 5], [7, 9]]))
1334 [(49, 80), (41, 60)]
1335 >>> list(matmul([[2, 5], [7, 9], [3, 4]], [[7, 11, 5, 4, 9], [3, 5, 2, 6, 3]]))
1336 [(29, 47, 20, 38, 33), (76, 122, 53, 82, 90), (33, 53, 23, 36, 39)]
1337
1338
1339 >>> list(convolve([1, -1, -20], [1, -3])) == [1, -4, -17, 60]
1340 True
1341 >>> data = [20, 40, 24, 32, 20, 28, 16]
1342 >>> list(convolve(data, [0.25, 0.25, 0.25, 0.25]))
1343 [5.0, 15.0, 21.0, 29.0, 29.0, 26.0, 24.0, 16.0, 11.0, 4.0]
1344 >>> list(convolve(data, [1, -1]))
1345 [20, 20, -16, 8, -12, 8, -12, -16]
1346 >>> list(convolve(data, [1, -2, 1]))
1347 [20, 0, -36, 24, -20, 20, -20, -4, 16]
1348 >>> # Verify signal is consumed lazily and the kernel greedily
1349 >>> signal_iterator = iter([10, 20, 30, 40, 50])
1350 >>> kernel_iterator = iter([1, 2, 3])
1351 >>> output_iterator = convolve(signal_iterator, kernel_iterator)
1352 >>> list(kernel_iterator)
1353 []
1354 >>> next(output_iterator)
1355 10
1356 >>> next(output_iterator)
1357 40
1358 >>> list(signal_iterator)
1359 [30, 40, 50]
1360
1361
1362 >>> from fractions import Fraction
1363 >>> from decimal import Decimal
1364 >>> polynomial_eval([1, -4, -17, 60], x=5)
1365 0
1366 >>> x = 5; x**3 - 4*x**2 -17*x + 60
1367 0
1368 >>> polynomial_eval([1, -4, -17, 60], x=2.5)
1369 8.125
1370 >>> x = 2.5; x**3 - 4*x**2 -17*x + 60
1371 8.125
1372 >>> polynomial_eval([1, -4, -17, 60], x=Fraction(2, 3))
1373 Fraction(1274, 27)
1374 >>> x = Fraction(2, 3); x**3 - 4*x**2 -17*x + 60
1375 Fraction(1274, 27)
1376 >>> polynomial_eval([1, -4, -17, 60], x=Decimal('1.75'))
1377 Decimal('23.359375')
1378 >>> x = Decimal('1.75'); x**3 - 4*x**2 -17*x + 60
1379 Decimal('23.359375')
1380 >>> polynomial_eval([], 2)
1381 0
1382 >>> polynomial_eval([], 2.5)
1383 0.0
1384 >>> polynomial_eval([], Fraction(2, 3))
1385 Fraction(0, 1)
1386 >>> polynomial_eval([], Decimal('1.75'))
1387 Decimal('0')
1388 >>> polynomial_eval([11], 7) == 11
1389 True
1390 >>> polynomial_eval([11, 2], 7) == 11 * 7 + 2
1391 True
1392
1393
1394 >>> polynomial_from_roots([5, -4, 3])
1395 [1, -4, -17, 60]
1396 >>> factored = lambda x: (x - 5) * (x + 4) * (x - 3)
1397 >>> expanded = lambda x: x**3 -4*x**2 -17*x + 60
1398 >>> all(factored(x) == expanded(x) for x in range(-10, 11))
1399 True
1400
1401
1402 >>> polynomial_derivative([1, -4, -17, 60])
1403 [3, -8, -17]
1404
1405
1406 >>> list(iter_index('AABCADEAF', 'A'))
1407 [0, 1, 4, 7]
1408 >>> list(iter_index('AABCADEAF', 'B'))
1409 [2]
1410 >>> list(iter_index('AABCADEAF', 'X'))
1411 []
1412 >>> list(iter_index('', 'X'))
1413 []
1414 >>> list(iter_index('AABCADEAF', 'A', 1))
1415 [1, 4, 7]
1416 >>> list(iter_index(iter('AABCADEAF'), 'A', 1))
1417 [1, 4, 7]
1418 >>> list(iter_index('AABCADEAF', 'A', 2))
1419 [4, 7]
1420 >>> list(iter_index(iter('AABCADEAF'), 'A', 2))
1421 [4, 7]
1422 >>> list(iter_index('AABCADEAF', 'A', 10))
1423 []
1424 >>> list(iter_index(iter('AABCADEAF'), 'A', 10))
1425 []
1426 >>> list(iter_index('AABCADEAF', 'A', 1, 7))
1427 [1, 4]
1428 >>> list(iter_index(iter('AABCADEAF'), 'A', 1, 7))
1429 [1, 4]
1430 >>> # Verify that ValueErrors not swallowed (gh-107208)
1431 >>> def assert_no_value(iterable, forbidden_value):
1432 ... for item in iterable:
1433 ... if item == forbidden_value:
1434 ... raise ValueError
1435 ... yield item
1436 ...
1437 >>> list(iter_index(assert_no_value('AABCADEAF', 'B'), 'A'))
1438 Traceback (most recent call last):
1439 ...
1440 ValueError
1441 >>> # Verify that both paths can find identical NaN values
1442 >>> x = float('NaN')
1443 >>> y = float('NaN')
1444 >>> list(iter_index([0, x, x, y, 0], x))
1445 [1, 2]
1446 >>> list(iter_index(iter([0, x, x, y, 0]), x))
1447 [1, 2]
1448 >>> # Test list input. Lists do not support None for the stop argument
1449 >>> list(iter_index(list('AABCADEAF'), 'A'))
1450 [0, 1, 4, 7]
1451 >>> # Verify that input is consumed lazily
1452 >>> input_iterator = iter('AABCADEAF')
1453 >>> output_iterator = iter_index(input_iterator, 'A')
1454 >>> next(output_iterator)
1455 0
1456 >>> next(output_iterator)
1457 1
1458 >>> next(output_iterator)
1459 4
1460 >>> ''.join(input_iterator)
1461 'DEAF'
1462
1463
1464 >>> # Verify that the target value can be a sequence.
1465 >>> seq = [[10, 20], [30, 40], 30, 40, [30, 40], 50]
1466 >>> target = [30, 40]
1467 >>> list(iter_index(seq, target))
1468 [1, 4]
1469
1470
1471 >>> # Verify faithfulness to type specific index() method behaviors.
1472 >>> # For example, bytes and str perform continuous-subsequence searches
1473 >>> # that do not match the general behavior specified
1474 >>> # in collections.abc.Sequence.index().
1475 >>> seq = 'abracadabra'
1476 >>> target = 'ab'
1477 >>> list(iter_index(seq, target))
1478 [0, 7]
1479
1480
1481 >>> list(sieve(30))
1482 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
1483 >>> small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
1484 >>> all(list(sieve(n)) == [p for p in small_primes if p < n] for n in range(101))
1485 True
1486 >>> len(list(sieve(100)))
1487 25
1488 >>> len(list(sieve(1_000)))
1489 168
1490 >>> len(list(sieve(10_000)))
1491 1229
1492 >>> len(list(sieve(100_000)))
1493 9592
1494 >>> len(list(sieve(1_000_000)))
1495 78498
1496 >>> carmichael = {561, 1105, 1729, 2465, 2821, 6601, 8911} # https://oeis.org/A002997
1497 >>> set(sieve(10_000)).isdisjoint(carmichael)
1498 True
1499
1500
1501 >>> small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
1502 >>> list(filter(is_prime, range(-100, 100))) == small_primes
1503 True
1504 >>> carmichael = {561, 1105, 1729, 2465, 2821, 6601, 8911} # https://oeis.org/A002997
1505 >>> any(map(is_prime, carmichael))
1506 False
1507 >>> # https://www.wolframalpha.com/input?i=is+128884753939+prime
1508 >>> is_prime(128_884_753_939) # large prime
1509 True
1510 >>> is_prime(999953 * 999983) # large semiprime
1511 False
1512 >>> is_prime(1_000_000_000_000_007) # factor() example
1513 False
1514 >>> is_prime(1_000_000_000_000_403) # factor() example
1515 True
1516
1517
1518 >>> list(factor(99)) # Code example 1
1519 [3, 3, 11]
1520 >>> list(factor(1_000_000_000_000_007)) # Code example 2
1521 [47, 59, 360620266859]
1522 >>> list(factor(1_000_000_000_000_403)) # Code example 3
1523 [1000000000000403]
1524 >>> list(factor(0))
1525 []
1526 >>> list(factor(1))
1527 []
1528 >>> list(factor(2))
1529 [2]
1530 >>> list(factor(3))
1531 [3]
1532 >>> list(factor(4))
1533 [2, 2]
1534 >>> list(factor(5))
1535 [5]
1536 >>> list(factor(6))
1537 [2, 3]
1538 >>> list(factor(7))
1539 [7]
1540 >>> list(factor(8))
1541 [2, 2, 2]
1542 >>> list(factor(9))
1543 [3, 3]
1544 >>> list(factor(10))
1545 [2, 5]
1546 >>> list(factor(128_884_753_939)) # large prime
1547 [128884753939]
1548 >>> list(factor(999953 * 999983)) # large semiprime
1549 [999953, 999983]
1550 >>> list(factor(6 ** 20)) == [2] * 20 + [3] * 20 # large power
1551 True
1552 >>> list(factor(909_909_090_909)) # large multiterm composite
1553 [3, 3, 7, 13, 13, 751, 113797]
1554 >>> math.prod([3, 3, 7, 13, 13, 751, 113797])
1555 909909090909
1556 >>> all(math.prod(factor(n)) == n for n in range(1, 2_000))
1557 True
1558 >>> all(set(factor(n)) <= set(sieve(n+1)) for n in range(2_000))
1559 True
1560 >>> all(list(factor(n)) == sorted(factor(n)) for n in range(2_000))
1561 True
1562
1563
1564 >>> totient(0) # https://www.wolframalpha.com/input?i=totient+0
1565 0
1566 >>> first_totients = [1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6,
1567 ... 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18,
1568 ... 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36,
1569 ... 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44] # https://oeis.org/A000010
1570 ...
1571 >>> list(map(totient, range(1, 70))) == first_totients
1572 True
1573 >>> reference_totient = lambda n: sum(math.gcd(t, n) == 1 for t in range(1, n+1))
1574 >>> all(totient(n) == reference_totient(n) for n in range(1000))
1575 True
1576 >>> totient(128_884_753_939) == 128_884_753_938 # large prime
1577 True
1578 >>> totient(999953 * 999983) == 999952 * 999982 # large semiprime
1579 True
1580 >>> totient(6 ** 20) == 1 * 2**19 * 2 * 3**19 # repeated primes
1581 True
1582
1583
1584 >>> list(flatten([('a', 'b'), (), ('c', 'd', 'e'), ('f',), ('g', 'h', 'i')]))
1585 ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']
1586
1587
1588 >>> list(repeatfunc(pow, 5, 2, 3))
1589 [8, 8, 8, 8, 8]
1590 >>> take(5, map(int, repeatfunc(random.random)))
1591 [0, 0, 0, 0, 0]
1592 >>> random.seed(85753098575309)
1593 >>> list(repeatfunc(random.random, 3))
1594 [0.16370491282496968, 0.45889608687313455, 0.3747076837820118]
1595 >>> list(repeatfunc(chr, 3, 65))
1596 ['A', 'A', 'A']
1597 >>> list(repeatfunc(pow, 3, 2, 5))
1598 [32, 32, 32]
1599
1600
1601 >>> list(grouper('abcdefg', 3, fillvalue='x'))
1602 [('a', 'b', 'c'), ('d', 'e', 'f'), ('g', 'x', 'x')]
1603
1604
1605 >>> it = grouper('abcdefg', 3, incomplete='strict')
1606 >>> next(it)
1607 ('a', 'b', 'c')
1608 >>> next(it)
1609 ('d', 'e', 'f')
1610 >>> next(it)
1611 Traceback (most recent call last):
1612 ...
1613 ValueError: zip() argument 2 is shorter than argument 1
1614
1615 >>> list(grouper('abcdefg', n=3, incomplete='ignore'))
1616 [('a', 'b', 'c'), ('d', 'e', 'f')]
1617
1618
1619 >>> list(sliding_window('ABCDEFG', 1))
1620 [('A',), ('B',), ('C',), ('D',), ('E',), ('F',), ('G',)]
1621 >>> list(sliding_window('ABCDEFG', 2))
1622 [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'F'), ('F', 'G')]
1623 >>> list(sliding_window('ABCDEFG', 3))
1624 [('A', 'B', 'C'), ('B', 'C', 'D'), ('C', 'D', 'E'), ('D', 'E', 'F'), ('E', 'F', 'G')]
1625 >>> list(sliding_window('ABCDEFG', 4))
1626 [('A', 'B', 'C', 'D'), ('B', 'C', 'D', 'E'), ('C', 'D', 'E', 'F'), ('D', 'E', 'F', 'G')]
1627 >>> list(sliding_window('ABCDEFG', 5))
1628 [('A', 'B', 'C', 'D', 'E'), ('B', 'C', 'D', 'E', 'F'), ('C', 'D', 'E', 'F', 'G')]
1629 >>> list(sliding_window('ABCDEFG', 6))
1630 [('A', 'B', 'C', 'D', 'E', 'F'), ('B', 'C', 'D', 'E', 'F', 'G')]
1631 >>> list(sliding_window('ABCDEFG', 7))
1632 [('A', 'B', 'C', 'D', 'E', 'F', 'G')]
1633 >>> list(sliding_window('ABCDEFG', 8))
1634 []
1635 >>> try:
1636 ... list(sliding_window('ABCDEFG', -1))
1637 ... except ValueError:
1638 ... 'zero or negative n not supported'
1639 ...
1640 'zero or negative n not supported'
1641 >>> try:
1642 ... list(sliding_window('ABCDEFG', 0))
1643 ... except ValueError:
1644 ... 'zero or negative n not supported'
1645 ...
1646 'zero or negative n not supported'
1647
1648
1649 >>> list(roundrobin('abc', 'd', 'ef'))
1650 ['a', 'd', 'e', 'b', 'f', 'c']
1651 >>> ranges = [range(5, 1000), range(4, 3000), range(0), range(3, 2000), range(2, 5000), range(1, 3500)]
1652 >>> collections.Counter(roundrobin(*ranges)) == collections.Counter(chain(*ranges))
1653 True
1654 >>> # Verify that the inputs are consumed lazily
1655 >>> input_iterators = list(map(iter, ['abcd', 'ef', '', 'ghijk', 'l', 'mnopqr']))
1656 >>> output_iterator = roundrobin(*input_iterators)
1657 >>> ''.join(islice(output_iterator, 10))
1658 'aeglmbfhnc'
1659 >>> ''.join(chain(*input_iterators))
1660 'dijkopqr'
1661
1662
1663 >>> list(subslices('ABCD'))
1664 ['A', 'AB', 'ABC', 'ABCD', 'B', 'BC', 'BCD', 'C', 'CD', 'D']
1665
1666
1667 >>> list(powerset([1,2,3]))
1668 [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
1669 >>> all(len(list(powerset(range(n)))) == 2**n for n in range(18))
1670 True
1671 >>> list(powerset('abcde')) == sorted(sorted(set(powerset('abcde'))), key=len)
1672 True
1673
1674
1675 >>> list(unique_everseen('AAAABBBCCDAABBB'))
1676 ['A', 'B', 'C', 'D']
1677 >>> list(unique_everseen('ABBCcAD', str.casefold))
1678 ['A', 'B', 'C', 'D']
1679 >>> list(unique_everseen('ABBcCAD', str.casefold))
1680 ['A', 'B', 'c', 'D']
1681 >>> # Verify that the input is consumed lazily
1682 >>> input_iterator = iter('AAAABBBCCDAABBB')
1683 >>> output_iterator = unique_everseen(input_iterator)
1684 >>> next(output_iterator)
1685 'A'
1686 >>> ''.join(input_iterator)
1687 'AAABBBCCDAABBB'
1688
1689
1690 >>> list(unique_justseen('AAAABBBCCDAABBB'))
1691 ['A', 'B', 'C', 'D', 'A', 'B']
1692 >>> list(unique_justseen('ABBCcAD', str.casefold))
1693 ['A', 'B', 'C', 'A', 'D']
1694 >>> list(unique_justseen('ABBcCAD', str.casefold))
1695 ['A', 'B', 'c', 'A', 'D']
1696 >>> # Verify that the input is consumed lazily
1697 >>> input_iterator = iter('AAAABBBCCDAABBB')
1698 >>> output_iterator = unique_justseen(input_iterator)
1699 >>> next(output_iterator)
1700 'A'
1701 >>> ''.join(input_iterator)
1702 'AAABBBCCDAABBB'
1703
1704
1705 >>> list(unique([[1, 2], [3, 4], [1, 2]]))
1706 [[1, 2], [3, 4]]
1707 >>> list(unique('ABBcCAD', str.casefold))
1708 ['A', 'B', 'c', 'D']
1709 >>> list(unique('ABBcCAD', str.casefold, reverse=True))
1710 ['D', 'c', 'B', 'A']
1711
1712
1713 >>> d = dict(a=1, b=2, c=3)
1714 >>> it = iter_except(d.popitem, KeyError)
1715 >>> d['d'] = 4
1716 >>> next(it)
1717 ('d', 4)
1718 >>> next(it)
1719 ('c', 3)
1720 >>> next(it)
1721 ('b', 2)
1722 >>> d['e'] = 5
1723 >>> next(it)
1724 ('e', 5)
1725 >>> next(it)
1726 ('a', 1)
1727 >>> next(it, 'empty')
1728 'empty'
1729
1730
1731 >>> first_true('ABC0DEF1', '9', str.isdigit)
1732 '0'
1733 >>> # Verify that inputs are consumed lazily
1734 >>> it = iter('ABC0DEF1')
1735 >>> first_true(it, predicate=str.isdigit)
1736 '0'
1737 >>> ''.join(it)
1738 'DEF1'
1739
1740 >>> multinomial(5, 2, 2, 1, 1)
1741 83160
1742 >>> word = 'coffee'
1743 >>> multinomial(*Counter(word).values()) == len(set(permutations(word)))
1744 True
1745
1746
1747 .. testcode::
1748 :hide:
1749
1750 # Old recipes and their tests which are guaranteed to continue to work.
1751
1752 def tabulate(function, start=0):
1753 "Return function(0), function(1), ..."
1754 return map(function, count(start))
1755
1756 def old_sumprod_recipe(vec1, vec2):
1757 "Compute a sum of products."
1758 return sum(starmap(operator.mul, zip(vec1, vec2, strict=True)))
1759
1760 def dotproduct(vec1, vec2):
1761 return sum(map(operator.mul, vec1, vec2))
1762
1763 def pad_none(iterable):
1764 """Returns the sequence elements and then returns None indefinitely.
1765
1766 Useful for emulating the behavior of the built-in map() function.
1767 """
1768 return chain(iterable, repeat(None))
1769
1770 def triplewise(iterable):
1771 "Return overlapping triplets from an iterable"
1772 # triplewise('ABCDEFG') → ABC BCD CDE DEF EFG
1773 for (a, _), (b, c) in pairwise(pairwise(iterable)):
1774 yield a, b, c
1775
1776 def nth_combination(iterable, r, index):
1777 "Equivalent to list(combinations(iterable, r))[index]"
1778 pool = tuple(iterable)
1779 n = len(pool)
1780 c = math.comb(n, r)
1781 if index < 0:
1782 index += c
1783 if index < 0 or index >= c:
1784 raise IndexError
1785 result = []
1786 while r:
1787 c, n, r = c*r//n, n-1, r-1
1788 while index >= c:
1789 index -= c
1790 c, n = c*(n-r)//n, n-1
1791 result.append(pool[-1-n])
1792 return tuple(result)
1793
1794 def before_and_after(predicate, it):
1795 """ Variant of takewhile() that allows complete
1796 access to the remainder of the iterator.
1797
1798 >>> it = iter('ABCdEfGhI')
1799 >>> all_upper, remainder = before_and_after(str.isupper, it)
1800 >>> ''.join(all_upper)
1801 'ABC'
1802 >>> ''.join(remainder) # takewhile() would lose the 'd'
1803 'dEfGhI'
1804
1805 Note that the true iterator must be fully consumed
1806 before the remainder iterator can generate valid results.
1807 """
1808 it = iter(it)
1809 transition = []
1810
1811 def true_iterator():
1812 for elem in it:
1813 if predicate(elem):
1814 yield elem
1815 else:
1816 transition.append(elem)
1817 return
1818
1819 return true_iterator(), chain(transition, it)
1820
1821 def partition(predicate, iterable):
1822 """Partition entries into false entries and true entries.
1823
1824 If *predicate* is slow, consider wrapping it with functools.lru_cache().
1825 """
1826 # partition(is_odd, range(10)) → 0 2 4 6 8 and 1 3 5 7 9
1827 t1, t2 = tee(iterable)
1828 return filterfalse(predicate, t1), filter(predicate, t2)
1829
1830
1831
1832 .. doctest::
1833 :hide:
1834
1835 >>> list(islice(tabulate(lambda x: 2*x), 4))
1836 [0, 2, 4, 6]
1837
1838
1839 >>> dotproduct([1,2,3], [4,5,6])
1840 32
1841
1842
1843 >>> old_sumprod_recipe([1,2,3], [4,5,6])
1844 32
1845
1846
1847 >>> list(islice(pad_none('abc'), 0, 6))
1848 ['a', 'b', 'c', None, None, None]
1849
1850
1851 >>> list(triplewise('ABCDEFG'))
1852 [('A', 'B', 'C'), ('B', 'C', 'D'), ('C', 'D', 'E'), ('D', 'E', 'F'), ('E', 'F', 'G')]
1853
1854
1855 >>> population = 'ABCDEFGH'
1856 >>> for r in range(len(population) + 1):
1857 ... seq = list(combinations(population, r))
1858 ... for i in range(len(seq)):
1859 ... assert nth_combination(population, r, i) == seq[i]
1860 ... for i in range(-len(seq), 0):
1861 ... assert nth_combination(population, r, i) == seq[i]
1862 ...
1863 >>> iterable = 'abcde'
1864 >>> r = 3
1865 >>> combos = list(combinations(iterable, r))
1866 >>> all(nth_combination(iterable, r, i) == comb for i, comb in enumerate(combos))
1867 True
1868
1869
1870 >>> it = iter('ABCdEfGhI')
1871 >>> all_upper, remainder = before_and_after(str.isupper, it)
1872 >>> ''.join(all_upper)
1873 'ABC'
1874 >>> ''.join(remainder)
1875 'dEfGhI'
1876
1877
1878 >>> def is_odd(x):
1879 ... return x % 2 == 1
1880 ...
1881 >>> evens, odds = partition(is_odd, range(10))
1882 >>> list(evens)
1883 [0, 2, 4, 6, 8]
1884 >>> list(odds)
1885 [1, 3, 5, 7, 9]
1886 >>> # Verify that the input is consumed lazily
1887 >>> input_iterator = iter(range(10))
1888 >>> evens, odds = partition(is_odd, input_iterator)
1889 >>> next(odds)
1890 1
1891 >>> next(odds)
1892 3
1893 >>> next(evens)
1894 0
1895 >>> list(input_iterator)
1896 [4, 5, 6, 7, 8, 9]