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 it = iter(xrange(s.start or 0, s.stop or sys.maxint, s.step or 1)) 415 nexti = next(it) 416 for i, element in enumerate(iterable): 417 if i == nexti: 418 yield element 419 nexti = next(it) 420 421 If *start* is ``None``, then iteration starts at zero. If *step* is ``None``, 422 then the step defaults to one. 423 424 .. versionchanged:: 2.5 425 accept ``None`` values for default *start* and *step*. 426 427 428.. function:: izip(*iterables) 429 430 Make an iterator that aggregates elements from each of the iterables. Like 431 :func:`zip` except that it returns an iterator instead of a list. Used for 432 lock-step iteration over several iterables at a time. Roughly equivalent to:: 433 434 def izip(*iterables): 435 # izip('ABCD', 'xy') --> Ax By 436 iterators = map(iter, iterables) 437 while iterators: 438 yield tuple(map(next, iterators)) 439 440 .. versionchanged:: 2.4 441 When no iterables are specified, returns a zero length iterator instead of 442 raising a :exc:`TypeError` exception. 443 444 The left-to-right evaluation order of the iterables is guaranteed. This 445 makes possible an idiom for clustering a data series into n-length groups 446 using ``izip(*[iter(s)]*n)``. 447 448 :func:`izip` should only be used with unequal length inputs when you don't 449 care about trailing, unmatched values from the longer iterables. If those 450 values are important, use :func:`izip_longest` instead. 451 452 453.. function:: izip_longest(*iterables[, fillvalue]) 454 455 Make an iterator that aggregates elements from each of the iterables. If the 456 iterables are of uneven length, missing values are filled-in with *fillvalue*. 457 Iteration continues until the longest iterable is exhausted. Roughly equivalent to:: 458 459 class ZipExhausted(Exception): 460 pass 461 462 def izip_longest(*args, **kwds): 463 # izip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D- 464 fillvalue = kwds.get('fillvalue') 465 counter = [len(args) - 1] 466 def sentinel(): 467 if not counter[0]: 468 raise ZipExhausted 469 counter[0] -= 1 470 yield fillvalue 471 fillers = repeat(fillvalue) 472 iterators = [chain(it, sentinel(), fillers) for it in args] 473 try: 474 while iterators: 475 yield tuple(map(next, iterators)) 476 except ZipExhausted: 477 pass 478 479 If one of the iterables is potentially infinite, then the 480 :func:`izip_longest` function should be wrapped with something that limits 481 the number of calls (for example :func:`islice` or :func:`takewhile`). If 482 not specified, *fillvalue* defaults to ``None``. 483 484 .. versionadded:: 2.6 485 486.. function:: permutations(iterable[, r]) 487 488 Return successive *r* length permutations of elements in the *iterable*. 489 490 If *r* is not specified or is ``None``, then *r* defaults to the length 491 of the *iterable* and all possible full-length permutations 492 are generated. 493 494 Permutations are emitted in lexicographic sort order. So, if the 495 input *iterable* is sorted, the permutation tuples will be produced 496 in sorted order. 497 498 Elements are treated as unique based on their position, not on their 499 value. So if the input elements are unique, there will be no repeat 500 values in each permutation. 501 502 Roughly equivalent to:: 503 504 def permutations(iterable, r=None): 505 # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC 506 # permutations(range(3)) --> 012 021 102 120 201 210 507 pool = tuple(iterable) 508 n = len(pool) 509 r = n if r is None else r 510 if r > n: 511 return 512 indices = range(n) 513 cycles = range(n, n-r, -1) 514 yield tuple(pool[i] for i in indices[:r]) 515 while n: 516 for i in reversed(range(r)): 517 cycles[i] -= 1 518 if cycles[i] == 0: 519 indices[i:] = indices[i+1:] + indices[i:i+1] 520 cycles[i] = n - i 521 else: 522 j = cycles[i] 523 indices[i], indices[-j] = indices[-j], indices[i] 524 yield tuple(pool[i] for i in indices[:r]) 525 break 526 else: 527 return 528 529 The code for :func:`permutations` can be also expressed as a subsequence of 530 :func:`product`, filtered to exclude entries with repeated elements (those 531 from the same position in the input pool):: 532 533 def permutations(iterable, r=None): 534 pool = tuple(iterable) 535 n = len(pool) 536 r = n if r is None else r 537 for indices in product(range(n), repeat=r): 538 if len(set(indices)) == r: 539 yield tuple(pool[i] for i in indices) 540 541 The number of items returned is ``n! / (n-r)!`` when ``0 <= r <= n`` 542 or zero when ``r > n``. 543 544 .. versionadded:: 2.6 545 546.. function:: product(*iterables[, repeat]) 547 548 Cartesian product of input iterables. 549 550 Roughly equivalent to nested for-loops in a generator expression. For example, 551 ``product(A, B)`` returns the same as ``((x,y) for x in A for y in B)``. 552 553 The nested loops cycle like an odometer with the rightmost element advancing 554 on every iteration. This pattern creates a lexicographic ordering so that if 555 the input's iterables are sorted, the product tuples are emitted in sorted 556 order. 557 558 To compute the product of an iterable with itself, specify the number of 559 repetitions with the optional *repeat* keyword argument. For example, 560 ``product(A, repeat=4)`` means the same as ``product(A, A, A, A)``. 561 562 This function is roughly equivalent to the following code, except that the 563 actual implementation does not build up intermediate results in memory:: 564 565 def product(*args, **kwds): 566 # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy 567 # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111 568 pools = map(tuple, args) * kwds.get('repeat', 1) 569 result = [[]] 570 for pool in pools: 571 result = [x+[y] for x in result for y in pool] 572 for prod in result: 573 yield tuple(prod) 574 575 .. versionadded:: 2.6 576 577.. function:: repeat(object[, times]) 578 579 Make an iterator that returns *object* over and over again. Runs indefinitely 580 unless the *times* argument is specified. Used as argument to :func:`imap` for 581 invariant function parameters. Also used with :func:`izip` to create constant 582 fields in a tuple record. Roughly equivalent to:: 583 584 def repeat(object, times=None): 585 # repeat(10, 3) --> 10 10 10 586 if times is None: 587 while True: 588 yield object 589 else: 590 for i in xrange(times): 591 yield object 592 593 A common use for *repeat* is to supply a stream of constant values to *imap* 594 or *zip*:: 595 596 >>> list(imap(pow, xrange(10), repeat(2))) 597 [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] 598 599.. function:: starmap(function, iterable) 600 601 Make an iterator that computes the function using arguments obtained from 602 the iterable. Used instead of :func:`imap` when argument parameters are already 603 grouped in tuples from a single iterable (the data has been "pre-zipped"). The 604 difference between :func:`imap` and :func:`starmap` parallels the distinction 605 between ``function(a,b)`` and ``function(*c)``. Roughly equivalent to:: 606 607 def starmap(function, iterable): 608 # starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000 609 for args in iterable: 610 yield function(*args) 611 612 .. versionchanged:: 2.6 613 Previously, :func:`starmap` required the function arguments to be tuples. 614 Now, any iterable is allowed. 615 616.. function:: takewhile(predicate, iterable) 617 618 Make an iterator that returns elements from the iterable as long as the 619 predicate is true. Roughly equivalent to:: 620 621 def takewhile(predicate, iterable): 622 # takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4 623 for x in iterable: 624 if predicate(x): 625 yield x 626 else: 627 break 628 629 630.. function:: tee(iterable[, n=2]) 631 632 Return *n* independent iterators from a single iterable. Roughly equivalent to:: 633 634 def tee(iterable, n=2): 635 it = iter(iterable) 636 deques = [collections.deque() for i in range(n)] 637 def gen(mydeque): 638 while True: 639 if not mydeque: # when the local deque is empty 640 newval = next(it) # fetch a new value and 641 for d in deques: # load it to all the deques 642 d.append(newval) 643 yield mydeque.popleft() 644 return tuple(gen(d) for d in deques) 645 646 Once :func:`tee` has made a split, the original *iterable* should not be 647 used anywhere else; otherwise, the *iterable* could get advanced without 648 the tee objects being informed. 649 650 This itertool may require significant auxiliary storage (depending on how 651 much temporary data needs to be stored). In general, if one iterator uses 652 most or all of the data before another iterator starts, it is faster to use 653 :func:`list` instead of :func:`tee`. 654 655 .. versionadded:: 2.4 656 657 658.. _itertools-recipes: 659 660Recipes 661------- 662 663This section shows recipes for creating an extended toolset using the existing 664itertools as building blocks. 665 666The extended tools offer the same high performance as the underlying toolset. 667The superior memory performance is kept by processing elements one at a time 668rather than bringing the whole iterable into memory all at once. Code volume is 669kept small by linking the tools together in a functional style which helps 670eliminate temporary variables. High speed is retained by preferring 671"vectorized" building blocks over the use of for-loops and :term:`generator`\s 672which incur interpreter overhead. 673 674.. testcode:: 675 676 def take(n, iterable): 677 "Return first n items of the iterable as a list" 678 return list(islice(iterable, n)) 679 680 def tabulate(function, start=0): 681 "Return function(0), function(1), ..." 682 return imap(function, count(start)) 683 684 def consume(iterator, n): 685 "Advance the iterator n-steps ahead. If n is none, consume entirely." 686 # Use functions that consume iterators at C speed. 687 if n is None: 688 # feed the entire iterator into a zero-length deque 689 collections.deque(iterator, maxlen=0) 690 else: 691 # advance to the empty slice starting at position n 692 next(islice(iterator, n, n), None) 693 694 def nth(iterable, n, default=None): 695 "Returns the nth item or a default value" 696 return next(islice(iterable, n, None), default) 697 698 def all_equal(iterable): 699 "Returns True if all the elements are equal to each other" 700 g = groupby(iterable) 701 return next(g, True) and not next(g, False) 702 703 def quantify(iterable, pred=bool): 704 "Count how many times the predicate is true" 705 return sum(imap(pred, iterable)) 706 707 def padnone(iterable): 708 """Returns the sequence elements and then returns None indefinitely. 709 710 Useful for emulating the behavior of the built-in map() function. 711 """ 712 return chain(iterable, repeat(None)) 713 714 def ncycles(iterable, n): 715 "Returns the sequence elements n times" 716 return chain.from_iterable(repeat(tuple(iterable), n)) 717 718 def dotproduct(vec1, vec2): 719 return sum(imap(operator.mul, vec1, vec2)) 720 721 def flatten(listOfLists): 722 "Flatten one level of nesting" 723 return chain.from_iterable(listOfLists) 724 725 def repeatfunc(func, times=None, *args): 726 """Repeat calls to func with specified arguments. 727 728 Example: repeatfunc(random.random) 729 """ 730 if times is None: 731 return starmap(func, repeat(args)) 732 return starmap(func, repeat(args, times)) 733 734 def pairwise(iterable): 735 "s -> (s0,s1), (s1,s2), (s2, s3), ..." 736 a, b = tee(iterable) 737 next(b, None) 738 return izip(a, b) 739 740 def grouper(iterable, n, fillvalue=None): 741 "Collect data into fixed-length chunks or blocks" 742 # grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx 743 args = [iter(iterable)] * n 744 return izip_longest(fillvalue=fillvalue, *args) 745 746 def roundrobin(*iterables): 747 "roundrobin('ABC', 'D', 'EF') --> A D E B F C" 748 # Recipe credited to George Sakkis 749 pending = len(iterables) 750 nexts = cycle(iter(it).next for it in iterables) 751 while pending: 752 try: 753 for next in nexts: 754 yield next() 755 except StopIteration: 756 pending -= 1 757 nexts = cycle(islice(nexts, pending)) 758 759 def powerset(iterable): 760 "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" 761 s = list(iterable) 762 return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) 763 764 def unique_everseen(iterable, key=None): 765 "List unique elements, preserving order. Remember all elements ever seen." 766 # unique_everseen('AAAABBBCCDAABBB') --> A B C D 767 # unique_everseen('ABBCcAD', str.lower) --> A B C D 768 seen = set() 769 seen_add = seen.add 770 if key is None: 771 for element in ifilterfalse(seen.__contains__, iterable): 772 seen_add(element) 773 yield element 774 else: 775 for element in iterable: 776 k = key(element) 777 if k not in seen: 778 seen_add(k) 779 yield element 780 781 def unique_justseen(iterable, key=None): 782 "List unique elements, preserving order. Remember only the element just seen." 783 # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B 784 # unique_justseen('ABBCcAD', str.lower) --> A B C A D 785 return imap(next, imap(itemgetter(1), groupby(iterable, key))) 786 787 def iter_except(func, exception, first=None): 788 """ Call a function repeatedly until an exception is raised. 789 790 Converts a call-until-exception interface to an iterator interface. 791 Like __builtin__.iter(func, sentinel) but uses an exception instead 792 of a sentinel to end the loop. 793 794 Examples: 795 bsddbiter = iter_except(db.next, bsddb.error, db.first) 796 heapiter = iter_except(functools.partial(heappop, h), IndexError) 797 dictiter = iter_except(d.popitem, KeyError) 798 dequeiter = iter_except(d.popleft, IndexError) 799 queueiter = iter_except(q.get_nowait, Queue.Empty) 800 setiter = iter_except(s.pop, KeyError) 801 802 """ 803 try: 804 if first is not None: 805 yield first() 806 while 1: 807 yield func() 808 except exception: 809 pass 810 811 def random_product(*args, **kwds): 812 "Random selection from itertools.product(*args, **kwds)" 813 pools = map(tuple, args) * kwds.get('repeat', 1) 814 return tuple(random.choice(pool) for pool in pools) 815 816 def random_permutation(iterable, r=None): 817 "Random selection from itertools.permutations(iterable, r)" 818 pool = tuple(iterable) 819 r = len(pool) if r is None else r 820 return tuple(random.sample(pool, r)) 821 822 def random_combination(iterable, r): 823 "Random selection from itertools.combinations(iterable, r)" 824 pool = tuple(iterable) 825 n = len(pool) 826 indices = sorted(random.sample(xrange(n), r)) 827 return tuple(pool[i] for i in indices) 828 829 def random_combination_with_replacement(iterable, r): 830 "Random selection from itertools.combinations_with_replacement(iterable, r)" 831 pool = tuple(iterable) 832 n = len(pool) 833 indices = sorted(random.randrange(n) for i in xrange(r)) 834 return tuple(pool[i] for i in indices) 835 836 def tee_lookahead(t, i): 837 """Inspect the i-th upcomping value from a tee object 838 while leaving the tee object at its current position. 839 840 Raise an IndexError if the underlying iterator doesn't 841 have enough values. 842 843 """ 844 for value in islice(t.__copy__(), i, None): 845 return value 846 raise IndexError(i) 847 848Note, many of the above recipes can be optimized by replacing global lookups 849with local variables defined as default values. For example, the 850*dotproduct* recipe can be written as:: 851 852 def dotproduct(vec1, vec2, sum=sum, imap=imap, mul=operator.mul): 853 return sum(imap(mul, vec1, vec2)) 854