Doc/library/itertools.rst

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