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