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 <python@rcn.com> 8.. sectionauthor:: Raymond Hettinger <python@rcn.com> 9 10.. testsetup:: 11 12 from itertools import * 13 14-------------- 15 16This module implements a number of :term:`iterator` building blocks inspired 17by constructs from APL, Haskell, and SML. Each has been recast in a form 18suitable for Python. 19 20The module standardizes a core set of fast, memory efficient tools that are 21useful by themselves or in combination. Together, they form an "iterator 22algebra" making it possible to construct specialized tools succinctly and 23efficiently in pure Python. 24 25For instance, SML provides a tabulation tool: ``tabulate(f)`` which produces a 26sequence ``f(0), f(1), ...``. The same effect can be achieved in Python 27by combining :func:`map` and :func:`count` to form ``map(f, count())``. 28 29These tools and their built-in counterparts also work well with the high-speed 30functions in the :mod:`operator` module. For example, the multiplication 31operator can be mapped across two vectors to form an efficient dot-product: 32``sum(map(operator.mul, vector1, vector2))``. 33 34 35**Infinite iterators:** 36 37================== ================= ================================================= ========================================= 38Iterator Arguments Results Example 39================== ================= ================================================= ========================================= 40:func:`count` start, [step] start, start+step, start+2*step, ... ``count(10) --> 10 11 12 13 14 ...`` 41:func:`cycle` p p0, p1, ... plast, p0, p1, ... ``cycle('ABCD') --> A B C D A B C D ...`` 42:func:`repeat` elem [,n] elem, elem, elem, ... endlessly or up to n times ``repeat(10, 3) --> 10 10 10`` 43================== ================= ================================================= ========================================= 44 45**Iterators terminating on the shortest input sequence:** 46 47============================ ============================ ================================================= ============================================================= 48Iterator Arguments Results Example 49============================ ============================ ================================================= ============================================================= 50:func:`accumulate` p [,func] p0, p0+p1, p0+p1+p2, ... ``accumulate([1,2,3,4,5]) --> 1 3 6 10 15`` 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` pred, seq seq[n], seq[n+1], starting when pred fails ``dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1`` 55:func:`filterfalse` pred, seq elements of seq where pred(elem) is false ``filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8`` 56:func:`groupby` iterable[, key] sub-iterators grouped by value of key(v) 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` pred, seq seq[0], seq[1], until pred fails ``takewhile(lambda x: x<5, [1,4,6,4,1]) --> 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============================================== ==================== ============================================================= 68Iterator 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============================================== ============================================================= 77Examples 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 88Itertool functions 89------------------ 90 91The following module functions all construct and return iterators. Some provide 92streams of infinite length, so they should only be accessed by functions or 93loops that truncate the stream. 94 95.. function:: accumulate(iterable[, func, *, initial=None]) 96 97 Make an iterator that returns accumulated sums, or accumulated 98 results of other binary functions (specified via the optional 99 *func* argument). 100 101 If *func* is supplied, it should be a function 102 of two arguments. Elements of the input *iterable* may be any type 103 that can be accepted as arguments to *func*. (For example, with 104 the default operation of addition, elements may be any addable 105 type including :class:`~decimal.Decimal` or 106 :class:`~fractions.Fraction`.) 107 108 Usually, the number of elements output matches the input iterable. 109 However, if the keyword argument *initial* is provided, the 110 accumulation leads off with the *initial* value so that the output 111 has one more element than the input iterable. 112 113 Roughly equivalent to:: 114 115 def accumulate(iterable, func=operator.add, *, initial=None): 116 'Return running totals' 117 # accumulate([1,2,3,4,5]) --> 1 3 6 10 15 118 # accumulate([1,2,3,4,5], initial=100) --> 100 101 103 106 110 115 119 # accumulate([1,2,3,4,5], operator.mul) --> 1 2 6 24 120 120 it = iter(iterable) 121 total = initial 122 if initial is None: 123 try: 124 total = next(it) 125 except StopIteration: 126 return 127 yield total 128 for element in it: 129 total = func(total, element) 130 yield total 131 132 There are a number of uses for the *func* argument. It can be set to 133 :func:`min` for a running minimum, :func:`max` for a running maximum, or 134 :func:`operator.mul` for a running product. Amortization tables can be 135 built by accumulating interest and applying payments. First-order 136 `recurrence relations <https://en.wikipedia.org/wiki/Recurrence_relation>`_ 137 can be modeled by supplying the initial value in the iterable and using only 138 the accumulated total in *func* argument:: 139 140 >>> data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8] 141 >>> list(accumulate(data, operator.mul)) # running product 142 [3, 12, 72, 144, 144, 1296, 0, 0, 0, 0] 143 >>> list(accumulate(data, max)) # running maximum 144 [3, 4, 6, 6, 6, 9, 9, 9, 9, 9] 145 146 # Amortize a 5% loan of 1000 with 4 annual payments of 90 147 >>> cashflows = [1000, -90, -90, -90, -90] 148 >>> list(accumulate(cashflows, lambda bal, pmt: bal*1.05 + pmt)) 149 [1000, 960.0, 918.0, 873.9000000000001, 827.5950000000001] 150 151 # Chaotic recurrence relation https://en.wikipedia.org/wiki/Logistic_map 152 >>> logistic_map = lambda x, _: r * x * (1 - x) 153 >>> r = 3.8 154 >>> x0 = 0.4 155 >>> inputs = repeat(x0, 36) # only the initial value is used 156 >>> [format(x, '.2f') for x in accumulate(inputs, logistic_map)] 157 ['0.40', '0.91', '0.30', '0.81', '0.60', '0.92', '0.29', '0.79', '0.63', 158 '0.88', '0.39', '0.90', '0.33', '0.84', '0.52', '0.95', '0.18', '0.57', 159 '0.93', '0.25', '0.71', '0.79', '0.63', '0.88', '0.39', '0.91', '0.32', 160 '0.83', '0.54', '0.95', '0.20', '0.60', '0.91', '0.30', '0.80', '0.60'] 161 162 See :func:`functools.reduce` for a similar function that returns only the 163 final accumulated value. 164 165 .. versionadded:: 3.2 166 167 .. versionchanged:: 3.3 168 Added the optional *func* parameter. 169 170 .. versionchanged:: 3.8 171 Added the optional *initial* parameter. 172 173.. function:: chain(*iterables) 174 175 Make an iterator that returns elements from the first iterable until it is 176 exhausted, then proceeds to the next iterable, until all of the iterables are 177 exhausted. Used for treating consecutive sequences as a single sequence. 178 Roughly equivalent to:: 179 180 def chain(*iterables): 181 # chain('ABC', 'DEF') --> A B C D E F 182 for it in iterables: 183 for element in it: 184 yield element 185 186 187.. classmethod:: chain.from_iterable(iterable) 188 189 Alternate constructor for :func:`chain`. Gets chained inputs from a 190 single iterable argument that is evaluated lazily. Roughly equivalent to:: 191 192 def from_iterable(iterables): 193 # chain.from_iterable(['ABC', 'DEF']) --> A B C D E F 194 for it in iterables: 195 for element in it: 196 yield element 197 198 199.. function:: combinations(iterable, r) 200 201 Return *r* length subsequences of elements from the input *iterable*. 202 203 The combination tuples are emitted in lexicographic ordering according to 204 the order of the input *iterable*. So, if the input *iterable* is sorted, 205 the combination tuples will be produced in sorted order. 206 207 Elements are treated as unique based on their position, not on their 208 value. So if the input elements are unique, there will be no repeat 209 values in each combination. 210 211 Roughly equivalent to:: 212 213 def combinations(iterable, r): 214 # combinations('ABCD', 2) --> AB AC AD BC BD CD 215 # combinations(range(4), 3) --> 012 013 023 123 216 pool = tuple(iterable) 217 n = len(pool) 218 if r > n: 219 return 220 indices = list(range(r)) 221 yield tuple(pool[i] for i in indices) 222 while True: 223 for i in reversed(range(r)): 224 if indices[i] != i + n - r: 225 break 226 else: 227 return 228 indices[i] += 1 229 for j in range(i+1, r): 230 indices[j] = indices[j-1] + 1 231 yield tuple(pool[i] for i in indices) 232 233 The code for :func:`combinations` can be also expressed as a subsequence 234 of :func:`permutations` after filtering entries where the elements are not 235 in sorted order (according to their position in the input pool):: 236 237 def combinations(iterable, r): 238 pool = tuple(iterable) 239 n = len(pool) 240 for indices in permutations(range(n), r): 241 if sorted(indices) == list(indices): 242 yield tuple(pool[i] for i in indices) 243 244 The number of items returned is ``n! / r! / (n-r)!`` when ``0 <= r <= n`` 245 or zero when ``r > n``. 246 247.. function:: combinations_with_replacement(iterable, r) 248 249 Return *r* length subsequences of elements from the input *iterable* 250 allowing individual elements to be repeated more than once. 251 252 The combination tuples are emitted in lexicographic ordering according to 253 the order of the input *iterable*. So, if the input *iterable* is sorted, 254 the combination tuples will be produced in sorted order. 255 256 Elements are treated as unique based on their position, not on their 257 value. So if the input elements are unique, the generated combinations 258 will also be unique. 259 260 Roughly equivalent to:: 261 262 def combinations_with_replacement(iterable, r): 263 # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC 264 pool = tuple(iterable) 265 n = len(pool) 266 if not n and r: 267 return 268 indices = [0] * r 269 yield tuple(pool[i] for i in indices) 270 while True: 271 for i in reversed(range(r)): 272 if indices[i] != n - 1: 273 break 274 else: 275 return 276 indices[i:] = [indices[i] + 1] * (r - i) 277 yield tuple(pool[i] for i in indices) 278 279 The code for :func:`combinations_with_replacement` can be also expressed as 280 a subsequence of :func:`product` after filtering entries where the elements 281 are not in sorted order (according to their position in the input pool):: 282 283 def combinations_with_replacement(iterable, r): 284 pool = tuple(iterable) 285 n = len(pool) 286 for indices in product(range(n), repeat=r): 287 if sorted(indices) == list(indices): 288 yield tuple(pool[i] for i in indices) 289 290 The number of items returned is ``(n+r-1)! / r! / (n-1)!`` when ``n > 0``. 291 292 .. versionadded:: 3.1 293 294 295.. function:: compress(data, selectors) 296 297 Make an iterator that filters elements from *data* returning only those that 298 have a corresponding element in *selectors* that evaluates to ``True``. 299 Stops when either the *data* or *selectors* iterables has been exhausted. 300 Roughly equivalent to:: 301 302 def compress(data, selectors): 303 # compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F 304 return (d for d, s in zip(data, selectors) if s) 305 306 .. versionadded:: 3.1 307 308 309.. function:: count(start=0, step=1) 310 311 Make an iterator that returns evenly spaced values starting with number *start*. Often 312 used as an argument to :func:`map` to generate consecutive data points. 313 Also, used with :func:`zip` to add sequence numbers. Roughly equivalent to:: 314 315 def count(start=0, step=1): 316 # count(10) --> 10 11 12 13 14 ... 317 # count(2.5, 0.5) -> 2.5 3.0 3.5 ... 318 n = start 319 while True: 320 yield n 321 n += step 322 323 When counting with floating point numbers, better accuracy can sometimes be 324 achieved by substituting multiplicative code such as: ``(start + step * i 325 for i in count())``. 326 327 .. versionchanged:: 3.1 328 Added *step* argument and allowed non-integer arguments. 329 330.. function:: cycle(iterable) 331 332 Make an iterator returning elements from the iterable and saving a copy of each. 333 When the iterable is exhausted, return elements from the saved copy. Repeats 334 indefinitely. Roughly equivalent to:: 335 336 def cycle(iterable): 337 # cycle('ABCD') --> A B C D A B C D A B C D ... 338 saved = [] 339 for element in iterable: 340 yield element 341 saved.append(element) 342 while saved: 343 for element in saved: 344 yield element 345 346 Note, this member of the toolkit may require significant auxiliary storage 347 (depending on the length of the iterable). 348 349 350.. function:: dropwhile(predicate, iterable) 351 352 Make an iterator that drops elements from the iterable as long as the predicate 353 is true; afterwards, returns every element. Note, the iterator does not produce 354 *any* output until the predicate first becomes false, so it may have a lengthy 355 start-up time. Roughly equivalent to:: 356 357 def dropwhile(predicate, iterable): 358 # dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1 359 iterable = iter(iterable) 360 for x in iterable: 361 if not predicate(x): 362 yield x 363 break 364 for x in iterable: 365 yield x 366 367.. function:: filterfalse(predicate, iterable) 368 369 Make an iterator that filters elements from iterable returning only those for 370 which the predicate is ``False``. If *predicate* is ``None``, return the items 371 that are false. Roughly equivalent to:: 372 373 def filterfalse(predicate, iterable): 374 # filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8 375 if predicate is None: 376 predicate = bool 377 for x in iterable: 378 if not predicate(x): 379 yield x 380 381 382.. function:: groupby(iterable, key=None) 383 384 Make an iterator that returns consecutive keys and groups from the *iterable*. 385 The *key* is a function computing a key value for each element. If not 386 specified or is ``None``, *key* defaults to an identity function and returns 387 the element unchanged. Generally, the iterable needs to already be sorted on 388 the same key function. 389 390 The operation of :func:`groupby` is similar to the ``uniq`` filter in Unix. It 391 generates a break or new group every time the value of the key function changes 392 (which is why it is usually necessary to have sorted the data using the same key 393 function). That behavior differs from SQL's GROUP BY which aggregates common 394 elements regardless of their input order. 395 396 The returned group is itself an iterator that shares the underlying iterable 397 with :func:`groupby`. Because the source is shared, when the :func:`groupby` 398 object is advanced, the previous group is no longer visible. So, if that data 399 is needed later, it should be stored as a list:: 400 401 groups = [] 402 uniquekeys = [] 403 data = sorted(data, key=keyfunc) 404 for k, g in groupby(data, keyfunc): 405 groups.append(list(g)) # Store group iterator as a list 406 uniquekeys.append(k) 407 408 :func:`groupby` is roughly equivalent to:: 409 410 class groupby: 411 # [k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B 412 # [list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D 413 def __init__(self, iterable, key=None): 414 if key is None: 415 key = lambda x: x 416 self.keyfunc = key 417 self.it = iter(iterable) 418 self.tgtkey = self.currkey = self.currvalue = object() 419 def __iter__(self): 420 return self 421 def __next__(self): 422 self.id = object() 423 while self.currkey == self.tgtkey: 424 self.currvalue = next(self.it) # Exit on StopIteration 425 self.currkey = self.keyfunc(self.currvalue) 426 self.tgtkey = self.currkey 427 return (self.currkey, self._grouper(self.tgtkey, self.id)) 428 def _grouper(self, tgtkey, id): 429 while self.id is id and self.currkey == tgtkey: 430 yield self.currvalue 431 try: 432 self.currvalue = next(self.it) 433 except StopIteration: 434 return 435 self.currkey = self.keyfunc(self.currvalue) 436 437 438.. function:: islice(iterable, stop) 439 islice(iterable, start, stop[, step]) 440 441 Make an iterator that returns selected elements from the iterable. If *start* is 442 non-zero, then elements from the iterable are skipped until start is reached. 443 Afterward, elements are returned consecutively unless *step* is set higher than 444 one which results in items being skipped. If *stop* is ``None``, then iteration 445 continues until the iterator is exhausted, if at all; otherwise, it stops at the 446 specified position. Unlike regular slicing, :func:`islice` does not support 447 negative values for *start*, *stop*, or *step*. Can be used to extract related 448 fields from data where the internal structure has been flattened (for example, a 449 multi-line report may list a name field on every third line). Roughly equivalent to:: 450 451 def islice(iterable, *args): 452 # islice('ABCDEFG', 2) --> A B 453 # islice('ABCDEFG', 2, 4) --> C D 454 # islice('ABCDEFG', 2, None) --> C D E F G 455 # islice('ABCDEFG', 0, None, 2) --> A C E G 456 s = slice(*args) 457 start, stop, step = s.start or 0, s.stop or sys.maxsize, s.step or 1 458 it = iter(range(start, stop, step)) 459 try: 460 nexti = next(it) 461 except StopIteration: 462 # Consume *iterable* up to the *start* position. 463 for i, element in zip(range(start), iterable): 464 pass 465 return 466 try: 467 for i, element in enumerate(iterable): 468 if i == nexti: 469 yield element 470 nexti = next(it) 471 except StopIteration: 472 # Consume to *stop*. 473 for i, element in zip(range(i + 1, stop), iterable): 474 pass 475 476 If *start* is ``None``, then iteration starts at zero. If *step* is ``None``, 477 then the step defaults to one. 478 479.. function:: pairwise(iterable) 480 481 Return successive overlapping pairs taken from the input *iterable*. 482 483 The number of 2-tuples in the output iterator will be one fewer than the 484 number of inputs. It will be empty if the input iterable has fewer than 485 two values. 486 487 Roughly equivalent to:: 488 489 def pairwise(iterable): 490 # pairwise('ABCDEFG') --> AB BC CD DE EF FG 491 a, b = tee(iterable) 492 next(b, None) 493 return zip(a, b) 494 495 .. versionadded:: 3.10 496 497 498.. function:: permutations(iterable, r=None) 499 500 Return successive *r* length permutations of elements in the *iterable*. 501 502 If *r* is not specified or is ``None``, then *r* defaults to the length 503 of the *iterable* and all possible full-length permutations 504 are generated. 505 506 The permutation tuples are emitted in lexicographic ordering according to 507 the order of the input *iterable*. So, if the input *iterable* is sorted, 508 the combination tuples will be produced in sorted order. 509 510 Elements are treated as unique based on their position, not on their 511 value. So if the input elements are unique, there will be no repeat 512 values in each permutation. 513 514 Roughly equivalent to:: 515 516 def permutations(iterable, r=None): 517 # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC 518 # permutations(range(3)) --> 012 021 102 120 201 210 519 pool = tuple(iterable) 520 n = len(pool) 521 r = n if r is None else r 522 if r > n: 523 return 524 indices = list(range(n)) 525 cycles = list(range(n, n-r, -1)) 526 yield tuple(pool[i] for i in indices[:r]) 527 while n: 528 for i in reversed(range(r)): 529 cycles[i] -= 1 530 if cycles[i] == 0: 531 indices[i:] = indices[i+1:] + indices[i:i+1] 532 cycles[i] = n - i 533 else: 534 j = cycles[i] 535 indices[i], indices[-j] = indices[-j], indices[i] 536 yield tuple(pool[i] for i in indices[:r]) 537 break 538 else: 539 return 540 541 The code for :func:`permutations` can be also expressed as a subsequence of 542 :func:`product`, filtered to exclude entries with repeated elements (those 543 from the same position in the input pool):: 544 545 def permutations(iterable, r=None): 546 pool = tuple(iterable) 547 n = len(pool) 548 r = n if r is None else r 549 for indices in product(range(n), repeat=r): 550 if len(set(indices)) == r: 551 yield tuple(pool[i] for i in indices) 552 553 The number of items returned is ``n! / (n-r)!`` when ``0 <= r <= n`` 554 or zero when ``r > n``. 555 556.. function:: product(*iterables, repeat=1) 557 558 Cartesian product of input iterables. 559 560 Roughly equivalent to nested for-loops in a generator expression. For example, 561 ``product(A, B)`` returns the same as ``((x,y) for x in A for y in B)``. 562 563 The nested loops cycle like an odometer with the rightmost element advancing 564 on every iteration. This pattern creates a lexicographic ordering so that if 565 the input's iterables are sorted, the product tuples are emitted in sorted 566 order. 567 568 To compute the product of an iterable with itself, specify the number of 569 repetitions with the optional *repeat* keyword argument. For example, 570 ``product(A, repeat=4)`` means the same as ``product(A, A, A, A)``. 571 572 This function is roughly equivalent to the following code, except that the 573 actual implementation does not build up intermediate results in memory:: 574 575 def product(*args, repeat=1): 576 # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy 577 # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111 578 pools = [tuple(pool) for pool in args] * repeat 579 result = [[]] 580 for pool in pools: 581 result = [x+[y] for x in result for y in pool] 582 for prod in result: 583 yield tuple(prod) 584 585 Before :func:`product` runs, it completely consumes the input iterables, 586 keeping pools of values in memory to generate the products. Accordingly, 587 it is only useful with finite inputs. 588 589.. function:: repeat(object[, times]) 590 591 Make an iterator that returns *object* over and over again. Runs indefinitely 592 unless the *times* argument is specified. Used as argument to :func:`map` for 593 invariant parameters to the called function. Also used with :func:`zip` to 594 create an invariant part of a tuple record. 595 596 Roughly equivalent to:: 597 598 def repeat(object, times=None): 599 # repeat(10, 3) --> 10 10 10 600 if times is None: 601 while True: 602 yield object 603 else: 604 for i in range(times): 605 yield object 606 607 A common use for *repeat* is to supply a stream of constant values to *map* 608 or *zip*:: 609 610 >>> list(map(pow, range(10), repeat(2))) 611 [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] 612 613.. function:: starmap(function, iterable) 614 615 Make an iterator that computes the function using arguments obtained from 616 the iterable. Used instead of :func:`map` when argument parameters are already 617 grouped in tuples from a single iterable (the data has been "pre-zipped"). The 618 difference between :func:`map` and :func:`starmap` parallels the distinction 619 between ``function(a,b)`` and ``function(*c)``. Roughly equivalent to:: 620 621 def starmap(function, iterable): 622 # starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000 623 for args in iterable: 624 yield function(*args) 625 626 627.. function:: takewhile(predicate, iterable) 628 629 Make an iterator that returns elements from the iterable as long as the 630 predicate is true. Roughly equivalent to:: 631 632 def takewhile(predicate, iterable): 633 # takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4 634 for x in iterable: 635 if predicate(x): 636 yield x 637 else: 638 break 639 640 641.. function:: tee(iterable, n=2) 642 643 Return *n* independent iterators from a single iterable. 644 645 The following Python code helps explain what *tee* does (although the actual 646 implementation is more complex and uses only a single underlying 647 :abbr:`FIFO (first-in, first-out)` queue). 648 649 Roughly equivalent to:: 650 651 def tee(iterable, n=2): 652 it = iter(iterable) 653 deques = [collections.deque() for i in range(n)] 654 def gen(mydeque): 655 while True: 656 if not mydeque: # when the local deque is empty 657 try: 658 newval = next(it) # fetch a new value and 659 except StopIteration: 660 return 661 for d in deques: # load it to all the deques 662 d.append(newval) 663 yield mydeque.popleft() 664 return tuple(gen(d) for d in deques) 665 666 Once :func:`tee` has made a split, the original *iterable* should not be 667 used anywhere else; otherwise, the *iterable* could get advanced without 668 the tee objects being informed. 669 670 ``tee`` iterators are not threadsafe. A :exc:`RuntimeError` may be 671 raised when using simultaneously iterators returned by the same :func:`tee` 672 call, even if the original *iterable* is threadsafe. 673 674 This itertool may require significant auxiliary storage (depending on how 675 much temporary data needs to be stored). In general, if one iterator uses 676 most or all of the data before another iterator starts, it is faster to use 677 :func:`list` instead of :func:`tee`. 678 679 680.. function:: zip_longest(*iterables, fillvalue=None) 681 682 Make an iterator that aggregates elements from each of the iterables. If the 683 iterables are of uneven length, missing values are filled-in with *fillvalue*. 684 Iteration continues until the longest iterable is exhausted. Roughly equivalent to:: 685 686 def zip_longest(*args, fillvalue=None): 687 # zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D- 688 iterators = [iter(it) for it in args] 689 num_active = len(iterators) 690 if not num_active: 691 return 692 while True: 693 values = [] 694 for i, it in enumerate(iterators): 695 try: 696 value = next(it) 697 except StopIteration: 698 num_active -= 1 699 if not num_active: 700 return 701 iterators[i] = repeat(fillvalue) 702 value = fillvalue 703 values.append(value) 704 yield tuple(values) 705 706 If one of the iterables is potentially infinite, then the :func:`zip_longest` 707 function should be wrapped with something that limits the number of calls 708 (for example :func:`islice` or :func:`takewhile`). If not specified, 709 *fillvalue* defaults to ``None``. 710 711 712.. _itertools-recipes: 713 714Itertools Recipes 715----------------- 716 717This section shows recipes for creating an extended toolset using the existing 718itertools as building blocks. 719 720Substantially all of these recipes and many, many others can be installed from 721the `more-itertools project <https://pypi.org/project/more-itertools/>`_ found 722on the Python Package Index:: 723 724 pip install more-itertools 725 726The extended tools offer the same high performance as the underlying toolset. 727The superior memory performance is kept by processing elements one at a time 728rather than bringing the whole iterable into memory all at once. Code volume is 729kept small by linking the tools together in a functional style which helps 730eliminate temporary variables. High speed is retained by preferring 731"vectorized" building blocks over the use of for-loops and :term:`generator`\s 732which incur interpreter overhead. 733 734.. testcode:: 735 736 def take(n, iterable): 737 "Return first n items of the iterable as a list" 738 return list(islice(iterable, n)) 739 740 def prepend(value, iterator): 741 "Prepend a single value in front of an iterator" 742 # prepend(1, [2, 3, 4]) -> 1 2 3 4 743 return chain([value], iterator) 744 745 def tabulate(function, start=0): 746 "Return function(0), function(1), ..." 747 return map(function, count(start)) 748 749 def tail(n, iterable): 750 "Return an iterator over the last n items" 751 # tail(3, 'ABCDEFG') --> E F G 752 return iter(collections.deque(iterable, maxlen=n)) 753 754 def consume(iterator, n=None): 755 "Advance the iterator n-steps ahead. If n is None, consume entirely." 756 # Use functions that consume iterators at C speed. 757 if n is None: 758 # feed the entire iterator into a zero-length deque 759 collections.deque(iterator, maxlen=0) 760 else: 761 # advance to the empty slice starting at position n 762 next(islice(iterator, n, n), None) 763 764 def nth(iterable, n, default=None): 765 "Returns the nth item or a default value" 766 return next(islice(iterable, n, None), default) 767 768 def all_equal(iterable): 769 "Returns True if all the elements are equal to each other" 770 g = groupby(iterable) 771 return next(g, True) and not next(g, False) 772 773 def quantify(iterable, pred=bool): 774 "Count how many times the predicate is true" 775 return sum(map(pred, iterable)) 776 777 def pad_none(iterable): 778 """Returns the sequence elements and then returns None indefinitely. 779 780 Useful for emulating the behavior of the built-in map() function. 781 """ 782 return chain(iterable, repeat(None)) 783 784 def ncycles(iterable, n): 785 "Returns the sequence elements n times" 786 return chain.from_iterable(repeat(tuple(iterable), n)) 787 788 def dotproduct(vec1, vec2): 789 return sum(map(operator.mul, vec1, vec2)) 790 791 def convolve(signal, kernel): 792 # See: https://betterexplained.com/articles/intuitive-convolution/ 793 # convolve(data, [0.25, 0.25, 0.25, 0.25]) --> Moving average (blur) 794 # convolve(data, [1, -1]) --> 1st finite difference (1st derivative) 795 # convolve(data, [1, -2, 1]) --> 2nd finite difference (2nd derivative) 796 kernel = tuple(kernel)[::-1] 797 n = len(kernel) 798 window = collections.deque([0], maxlen=n) * n 799 for x in chain(signal, repeat(0, n-1)): 800 window.append(x) 801 yield sum(map(operator.mul, kernel, window)) 802 803 def flatten(list_of_lists): 804 "Flatten one level of nesting" 805 return chain.from_iterable(list_of_lists) 806 807 def repeatfunc(func, times=None, *args): 808 """Repeat calls to func with specified arguments. 809 810 Example: repeatfunc(random.random) 811 """ 812 if times is None: 813 return starmap(func, repeat(args)) 814 return starmap(func, repeat(args, times)) 815 816 def grouper(iterable, n, fillvalue=None): 817 "Collect data into non-overlapping fixed-length chunks or blocks" 818 # grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx 819 args = [iter(iterable)] * n 820 return zip_longest(*args, fillvalue=fillvalue) 821 822 def triplewise(iterable): 823 "Return overlapping triplets from an iterable" 824 # triplewise('ABCDEFG') -> ABC BCD CDE DEF EFG 825 for (a, _), (b, c) in pairwise(pairwise(iterable)): 826 yield a, b, c 827 828 def sliding_window(iterable, n): 829 # sliding_window('ABCDEFG', 4) -> ABCD BCDE CDEF DEFG 830 it = iter(iterable) 831 window = collections.deque(islice(it, n), maxlen=n) 832 if len(window) == n: 833 yield tuple(window) 834 for x in it: 835 window.append(x) 836 yield tuple(window) 837 838 def roundrobin(*iterables): 839 "roundrobin('ABC', 'D', 'EF') --> A D E B F C" 840 # Recipe credited to George Sakkis 841 num_active = len(iterables) 842 nexts = cycle(iter(it).__next__ for it in iterables) 843 while num_active: 844 try: 845 for next in nexts: 846 yield next() 847 except StopIteration: 848 # Remove the iterator we just exhausted from the cycle. 849 num_active -= 1 850 nexts = cycle(islice(nexts, num_active)) 851 852 def partition(pred, iterable): 853 "Use a predicate to partition entries into false entries and true entries" 854 # partition(is_odd, range(10)) --> 0 2 4 6 8 and 1 3 5 7 9 855 t1, t2 = tee(iterable) 856 return filterfalse(pred, t1), filter(pred, t2) 857 858 def before_and_after(predicate, it): 859 """ Variant of takewhile() that allows complete 860 access to the remainder of the iterator. 861 862 >>> it = iter('ABCdEfGhI') 863 >>> all_upper, remainder = before_and_after(str.isupper, it) 864 >>> ''.join(all_upper) 865 'ABC' 866 >>> ''.join(remainder) # takewhile() would lose the 'd' 867 'dEfGhI' 868 869 Note that the first iterator must be fully 870 consumed before the second iterator can 871 generate valid results. 872 """ 873 it = iter(it) 874 transition = [] 875 def true_iterator(): 876 for elem in it: 877 if predicate(elem): 878 yield elem 879 else: 880 transition.append(elem) 881 return 882 def remainder_iterator(): 883 yield from transition 884 yield from it 885 return true_iterator(), remainder_iterator() 886 887 def powerset(iterable): 888 "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" 889 s = list(iterable) 890 return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) 891 892 def unique_everseen(iterable, key=None): 893 "List unique elements, preserving order. Remember all elements ever seen." 894 # unique_everseen('AAAABBBCCDAABBB') --> A B C D 895 # unique_everseen('ABBCcAD', str.lower) --> A B C D 896 seen = set() 897 seen_add = seen.add 898 if key is None: 899 for element in filterfalse(seen.__contains__, iterable): 900 seen_add(element) 901 yield element 902 else: 903 for element in iterable: 904 k = key(element) 905 if k not in seen: 906 seen_add(k) 907 yield element 908 909 def unique_justseen(iterable, key=None): 910 "List 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.lower) --> A B C A D 913 return map(next, map(operator.itemgetter(1), groupby(iterable, key))) 914 915 def iter_except(func, exception, first=None): 916 """ Call a function repeatedly until an exception is raised. 917 918 Converts a call-until-exception interface to an iterator interface. 919 Like builtins.iter(func, sentinel) but uses an exception instead 920 of a sentinel to end the loop. 921 922 Examples: 923 iter_except(functools.partial(heappop, h), IndexError) # priority queue iterator 924 iter_except(d.popitem, KeyError) # non-blocking dict iterator 925 iter_except(d.popleft, IndexError) # non-blocking deque iterator 926 iter_except(q.get_nowait, Queue.Empty) # loop over a producer Queue 927 iter_except(s.pop, KeyError) # non-blocking set iterator 928 929 """ 930 try: 931 if first is not None: 932 yield first() # For database APIs needing an initial cast to db.first() 933 while True: 934 yield func() 935 except exception: 936 pass 937 938 def first_true(iterable, default=False, pred=None): 939 """Returns the first true value in the iterable. 940 941 If no true value is found, returns *default* 942 943 If *pred* is not None, returns the first item 944 for which pred(item) is true. 945 946 """ 947 # first_true([a,b,c], x) --> a or b or c or x 948 # first_true([a,b], x, f) --> a if f(a) else b if f(b) else x 949 return next(filter(pred, iterable), default) 950 951 def random_product(*args, repeat=1): 952 "Random selection from itertools.product(*args, **kwds)" 953 pools = [tuple(pool) for pool in args] * repeat 954 return tuple(map(random.choice, pools)) 955 956 def random_permutation(iterable, r=None): 957 "Random selection from itertools.permutations(iterable, r)" 958 pool = tuple(iterable) 959 r = len(pool) if r is None else r 960 return tuple(random.sample(pool, r)) 961 962 def random_combination(iterable, r): 963 "Random selection from itertools.combinations(iterable, r)" 964 pool = tuple(iterable) 965 n = len(pool) 966 indices = sorted(random.sample(range(n), r)) 967 return tuple(pool[i] for i in indices) 968 969 def random_combination_with_replacement(iterable, r): 970 "Random selection from itertools.combinations_with_replacement(iterable, r)" 971 pool = tuple(iterable) 972 n = len(pool) 973 indices = sorted(random.choices(range(n), k=r)) 974 return tuple(pool[i] for i in indices) 975 976 def nth_combination(iterable, r, index): 977 "Equivalent to list(combinations(iterable, r))[index]" 978 pool = tuple(iterable) 979 n = len(pool) 980 if r < 0 or r > n: 981 raise ValueError 982 c = 1 983 k = min(r, n-r) 984 for i in range(1, k+1): 985 c = c * (n - k + i) // i 986 if index < 0: 987 index += c 988 if index < 0 or index >= c: 989 raise IndexError 990 result = [] 991 while r: 992 c, n, r = c*r//n, n-1, r-1 993 while index >= c: 994 index -= c 995 c, n = c*(n-r)//n, n-1 996 result.append(pool[-1-n]) 997 return tuple(result) 998