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