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