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