itertools.md
1> **Источник:** https://python-all.ru/2.7/library/itertools.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# 9.7. [`itertools`](https://python-all.ru/2.7/library/itertools.html#module-itertools) – Функции, создающие итераторы для эффективного перебора89Новое в версии 2.3.1011Этот модуль реализует ряд строительных блоков [итераторов](https://python-all.ru/2.7/glossary.html#term-iterator), вдохновлённых конструкциями из APL, Haskell и SML. Каждый из них переработан в форму, подходящую для Python.1213Модуль стандартизирует основной набор быстрых и эффективных по памяти инструментов, которые полезны сами по себе или в комбинации. Вместе они образуют «алгебру итераторов», позволяющую создавать специализированные инструменты кратко и эффективно на чистом Python.1415Например, SML предоставляет инструмент табуляции: `tabulate(f)`, который порождает последовательность `f(0), f(1), ...`. Того же эффекта можно достичь в Python скомбинировав [`imap()`](https://python-all.ru/2.7/library/itertools.html#itertools.imap) и [`count()`](https://python-all.ru/2.7/library/itertools.html#itertools.count) для получения `imap(f, count())`.1617Эти инструменты и их встроенные аналоги также хорошо работают с высокоскоростными функциями из модуля [`operator`](https://python-all.ru/2.7/library/operator.html#module-operator). Например, оператор умножения можно применить к двум векторам, чтобы получить эффективное скалярное произведение: `sum(imap(operator.mul, vector1, vector2))`.1819**Бесконечные итераторы:**2021| Итератор | Аргументы | Результаты | Пример |22| --- | --- | --- | --- |23| [`count()`](https://python-all.ru/2.7/library/itertools.html#itertools.count) | start, \[step\] | start, start+step, start+2\*step, … | `count(10) --> 10 11 12 13 14 ...` |24| [`cycle()`](https://python-all.ru/2.7/library/itertools.html#itertools.cycle) | p | p0, p1, … plast, p0, p1, … | `cycle('ABCD') --> A B C D A B C D ...` |25| [`repeat()`](https://python-all.ru/2.7/library/itertools.html#itertools.repeat) | elem \[,n\] | elem, elem, elem, … бесконечно или до n раз | `repeat(10, 3) --> 10 10 10` |2627**Итераторы, завершающиеся по кратчайшей входной последовательности:**2829| Итератор | Аргументы | Результаты | Пример |30| --- | --- | --- | --- |31| [`chain()`](https://python-all.ru/2.7/library/itertools.html#itertools.chain) | p, q, … | p0, p1, … plast, q0, q1, … | `chain('ABC', 'DEF') --> A B C D E F` |32| [`compress()`](https://python-all.ru/2.7/library/itertools.html#itertools.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` |33| [`dropwhile()`](https://python-all.ru/2.7/library/itertools.html#itertools.dropwhile) | pred, seq | seq\[n\], seq\[n+1\], начиная с момента, когда pred не выполняется | `dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1` |34| [`groupby()`](https://python-all.ru/2.7/library/itertools.html#itertools.groupby) | iterable\[, keyfunc\] | под-итераторы, сгруппированные по значению keyfunc(v) | |35| [`ifilter()`](https://python-all.ru/2.7/library/itertools.html#itertools.ifilter) | pred, seq | элементы seq, для которых pred(elem) истинно | `ifilter(lambda x: x%2, range(10)) --> 1 3 5 7 9` |36| [`ifilterfalse()`](https://python-all.ru/2.7/library/itertools.html#itertools.ifilterfalse) | pred, seq | элементы seq, для которых pred(elem) ложно | `ifilterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8` |37| [`islice()`](https://python-all.ru/2.7/library/itertools.html#itertools.islice) | seq, \[start,\] stop \[, step\] | элементы из seq\[start:stop:step\] | `islice('ABCDEFG', 2, None) --> C D E F G` |38| [`imap()`](https://python-all.ru/2.7/library/itertools.html#itertools.imap) | func, p, q, … | func(p0, q0), func(p1, q1), … | `imap(pow, (2,3,10), (5,2,3)) --> 32 9 1000` |39| [`starmap()`](https://python-all.ru/2.7/library/itertools.html#itertools.starmap) | func, seq | func(\*seq\[0\]), func(\*seq\[1\]), … | `starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000` |40| [`tee()`](https://python-all.ru/2.7/library/itertools.html#itertools.tee) | it, n | it1, it2, … itn разделяет один итератор на n | |41| [`takewhile()`](https://python-all.ru/2.7/library/itertools.html#itertools.takewhile) | pred, seq | seq\[0\], seq\[1\], пока pred не вернёт ложь | `takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4` |42| [`izip()`](https://python-all.ru/2.7/library/itertools.html#itertools.izip) | p, q, … | (p\[0\], q\[0\]), (p\[1\], q\[1\]), … | `izip('ABCD', 'xy') --> Ax By` |43| [`izip_longest()`](https://python-all.ru/2.7/library/itertools.html#itertools.izip_longest) | p, q, … | (p\[0\], q\[0\]), (p\[1\], q\[1\]), … | `izip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-` |4445**Комбинаторные генераторы:**4647| Итератор | Аргументы | Результаты |48| --- | --- | --- |49| [`product()`](https://python-all.ru/2.7/library/itertools.html#itertools.product) | p, q, … \[repeat=1\] | декартово произведение, эквивалентно вложенному циклу for |50| [`permutations()`](https://python-all.ru/2.7/library/itertools.html#itertools.permutations) | p\[, r\] | кортежи длиной r, все возможные перестановки, без повторяющихся элементов |51| [`combinations()`](https://python-all.ru/2.7/library/itertools.html#itertools.combinations) | p, r | кортежи длиной r, в отсортированном порядке, без повторяющихся элементов |52| [`combinations_with_replacement()`](https://python-all.ru/2.7/library/itertools.html#itertools.combinations_with_replacement) | p, r | кортежи длиной r, в отсортированном порядке, с повторяющимися элементами |53| `product('ABCD', repeat=2)` | | `AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD` |54| `permutations('ABCD', 2)` | | `AB AC AD BA BC BD CA CB CD DA DB DC` |55| `combinations('ABCD', 2)` | | `AB AC AD BC BD CD` |56| `combinations_with_replacement('ABCD', 2)` | | `AA AB AC AD BB BC BD CC CD DD` |5758## 9.7.1. Функции itertools5960Следующие функции модуля создают и возвращают итераторы. Некоторые из них порождают потоки бесконечной длины, поэтому обращаться к ним следует только с помощью функций или циклов, которые обрывают поток.6162#### `itertools.chain(*iterables)`6364Создаёт итератор, который возвращает элементы из первого итерируемого объекта, пока он не будет исчерпан, затем переходит к следующему, пока все итерируемые объекты не будут исчерпаны. Используется для объединения последовательностей в одну. Приблизительный эквивалент:6566```python67def chain(*iterables):68 # chain('ABC', 'DEF') --> A B C D E F69 for it in iterables:70 for element in it:71 yield element72```7374#### `classmethod chain.from_iterable(iterable)`7576Альтернативный конструктор для [`chain()`](https://python-all.ru/2.7/library/itertools.html#itertools.chain). Получает цепочку входных данных из одного аргумента iterable, который вычисляется лениво. Примерная реализация:7778```python79def from_iterable(iterables):80 # chain.from_iterable(['ABC', 'DEF']) --> A B C D E F81 for it in iterables:82 for element in it:83 yield element84```8586Новое в версии 2.6.8788#### `itertools.combinations(iterable, r)`8990Возвращает подпоследовательности элементов длины *r* из входного *iterable*.9192Комбинации выдаются в лексикографическом порядке. Таким образом, если входной *итерируемый объект* отсортирован, кортежи комбинаций будут созданы в отсортированном порядке.9394Элементы считаются уникальными на основе их позиции, а не значения. Поэтому если входные элементы уникальны, то в каждой комбинации не будет повторяющихся значений.9596Примерно эквивалентно:9798```python99def combinations(iterable, r):100 # combinations('ABCD', 2) --> AB AC AD BC BD CD101 # combinations(range(4), 3) --> 012 013 023 123102 pool = tuple(iterable)103 n = len(pool)104 if r > n:105 return106 indices = range(r)107 yield tuple(pool[i] for i in indices)108 while True:109 for i in reversed(range(r)):110 if indices[i] != i + n - r:111 break112 else:113 return114 indices[i] += 1115 for j in range(i+1, r):116 indices[j] = indices[j-1] + 1117 yield tuple(pool[i] for i in indices)118```119120Код для [`combinations()`](https://python-all.ru/2.7/library/itertools.html#itertools.combinations) можно также выразить как подпоследовательность [`permutations()`](https://python-all.ru/2.7/library/itertools.html#itertools.permutations) после фильтрации записей, где элементы не находятся в отсортированном порядке (согласно их позиции во входном пуле):121122```python123def combinations(iterable, r):124 pool = tuple(iterable)125 n = len(pool)126 for indices in permutations(range(n), r):127 if sorted(indices) == list(indices):128 yield tuple(pool[i] for i in indices)129```130131Количество возвращаемых элементов равно `n! / r! / (n-r)!`, когда `0 <= r <= n`, или нулю, когда `r > n`.132133Новое в версии 2.6.134135#### `itertools.combinations_with_replacement(iterable, r)`136137Возвращает подпоследовательности элементов длины *r* из входного *iterable*, допуская повторение отдельных элементов.138139Комбинации выдаются в лексикографическом порядке. Таким образом, если входной *итерируемый объект* отсортирован, кортежи комбинаций будут созданы в отсортированном порядке.140141Элементы считаются уникальными по их позиции, а не по значению. Поэтому если входные элементы уникальны, сгенерированные комбинации также будут уникальны.142143Примерно эквивалентно:144145```python146def combinations_with_replacement(iterable, r):147 # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC148 pool = tuple(iterable)149 n = len(pool)150 if not n and r:151 return152 indices = [0] * r153 yield tuple(pool[i] for i in indices)154 while True:155 for i in reversed(range(r)):156 if indices[i] != n - 1:157 break158 else:159 return160 indices[i:] = [indices[i] + 1] * (r - i)161 yield tuple(pool[i] for i in indices)162```163164Код для [`combinations_with_replacement()`](https://python-all.ru/2.7/library/itertools.html#itertools.combinations_with_replacement) можно также выразить как подпоследовательность [`product()`](https://python-all.ru/2.7/library/itertools.html#itertools.product) после фильтрации записей, где элементы не находятся в отсортированном порядке (согласно их позиции во входном пуле):165166```python167def combinations_with_replacement(iterable, r):168 pool = tuple(iterable)169 n = len(pool)170 for indices in product(range(n), repeat=r):171 if sorted(indices) == list(indices):172 yield tuple(pool[i] for i in indices)173```174175Количество возвращаемых элементов равно `(n+r-1)! / r! / (n-1)!`, когда `n > 0`.176177Новое в версии 2.7.178179#### `itertools.compress(data, selectors)`180181Создаёт итератор, который фильтрует элементы из *data*, возвращая только те, для которых в *selectors* есть соответствующий элемент, вычисляемый как `True`. Останавливается, когда исчерпан либо итерабельный объект *data*, либо *selectors*. Примерно эквивалентен:182183```python184def compress(data, selectors):185 # compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F186 return (d for d, s in izip(data, selectors) if s)187```188189Новое в версии 2.7.190191#### `itertools.count(start=0, step=1)`192193Создаёт итератор, который возвращает равномерно распределённые значения, начиная с *n*. Часто используется как аргумент для [`imap()`](https://python-all.ru/2.7/library/itertools.html#itertools.imap) для генерации последовательных точек данных. Также используется с [`izip()`](https://python-all.ru/2.7/library/itertools.html#itertools.izip) для добавления порядковых номеров. Эквивалентно:194195```python196def count(start=0, step=1):197 # count(10) --> 10 11 12 13 14 ...198 # count(2.5, 0.5) -> 2.5 3.0 3.5 ...199 n = start200 while True:201 yield n202 n += step203```204205При подсчёте с числами с плавающей запятой иногда можно добиться лучшей точности, заменив код на мультипликативный, например: `(start + step * i for i in count())`.206207Изменено в версии 2.7: добавлен аргумент *step* и разрешены нецелые аргументы.208209#### `itertools.cycle(iterable)`210211Создаёт итератор, возвращающий элементы из итерабельного объекта и сохраняющий копию каждого. Когда итерабельный объект исчерпан, возвращает элементы из сохранённой копии. Повторяется бесконечно. Примерно эквивалентен:212213```python214def cycle(iterable):215 # cycle('ABCD') --> A B C D A B C D A B C D ...216 saved = []217 for element in iterable:218 yield element219 saved.append(element)220 while saved:221 for element in saved:222 yield element223```224225Примечание: этот элемент набора инструментов может потребовать значительного дополнительного хранилища (в зависимости от длины итерабельного объекта).226227#### `itertools.dropwhile(predicate, iterable)`228229Создаёт итератор, который отбрасывает элементы из итерабельного объекта, пока предикат истинен; после этого возвращает каждый элемент. Примечание: итератор не выдаёт *никакого* вывода, пока предикат впервые не станет ложным, поэтому время запуска может быть большим. Примерно эквивалентен:230231```python232def dropwhile(predicate, iterable):233 # dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1234 iterable = iter(iterable)235 for x in iterable:236 if not predicate(x):237 yield x238 break239 for x in iterable:240 yield x241```242243#### `itertools.groupby(iterable[, key])`244245Make an iterator that returns consecutive keys and groups from the *iterable*. The *key* is a function computing a key value for each element. If not specified or is `None`, *key* defaults to an identity function and returns the element unchanged. Generally, the iterable needs to already be sorted on the same key function.246247Работа [`groupby()`](https://python-all.ru/2.7/library/itertools.html#itertools.groupby) аналогична фильтру `uniq` в Unix. Она создает разрыв или новую группу каждый раз, когда изменяется значение ключевой функции (поэтому обычно необходимо отсортировать данные с помощью той же ключевой функции). Такое поведение отличается от SQL GROUP BY, которая объединяет общие элементы независимо от порядка их ввода.248249Возвращаемая группа сама является итератором, который использует общий исходный итерируемый объект с [`groupby()`](https://python-all.ru/2.7/library/itertools.html#itertools.groupby). Поскольку источник общий, при продвижении объекта [`groupby()`](https://python-all.ru/2.7/library/itertools.html#itertools.groupby) предыдущая группа перестает быть видимой. Поэтому, если эти данные понадобятся позже, их следует сохранить в виде списка:250251```python252groups = []253uniquekeys = []254data = sorted(data, key=keyfunc)255for k, g in groupby(data, keyfunc):256 groups.append(list(g)) # Сохранить групповой итератор как список257 uniquekeys.append(k)258```259260[`groupby()`](https://python-all.ru/2.7/library/itertools.html#itertools.groupby) примерно эквивалентно:261262```python263class groupby(object):264 # [k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B265 # [list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D266 def __init__(self, iterable, key=None):267 if key is None:268 key = lambda x: x269 self.keyfunc = key270 self.it = iter(iterable)271 self.tgtkey = self.currkey = self.currvalue = object()272 def __iter__(self):273 return self274 def next(self):275 while self.currkey == self.tgtkey:276 self.currvalue = next(self.it) # Выход при StopIteration277 self.currkey = self.keyfunc(self.currvalue)278 self.tgtkey = self.currkey279 return (self.currkey, self._grouper(self.tgtkey))280 def _grouper(self, tgtkey):281 while self.currkey == tgtkey:282 yield self.currvalue283 self.currvalue = next(self.it) # Выход при StopIteration284 self.currkey = self.keyfunc(self.currvalue)285```286287Новое в версии 2.4.288289#### `itertools.ifilter(predicate, iterable)`290291Создаёт итератор, который фильтрует элементы из итерируемого объекта, возвращая только те, для которых предикат равен `True`. Если *предикат* равен `None`, возвращает элементы, которые являются истинными. Примерный эквивалент:292293```python294def ifilter(predicate, iterable):295 # ifilter(lambda x: x%2, range(10)) --> 1 3 5 7 9296 if predicate is None:297 predicate = bool298 for x in iterable:299 if predicate(x):300 yield x301```302303#### `itertools.ifilterfalse(predicate, iterable)`304305Создаёт итератор, который фильтрует элементы из итерируемого объекта, возвращая только те, для которых предикат равен `False`. Если *предикат* равен `None`, возвращает элементы, которые являются ложными. Примерно эквивалентно:306307```python308def ifilterfalse(predicate, iterable):309 # ifilterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8310 if predicate is None:311 predicate = bool312 for x in iterable:313 if not predicate(x):314 yield x315```316317#### `itertools.imap(function, *iterables)`318319Создаёт итератор, который вычисляет функцию, используя аргументы из каждого итерируемого объекта. Если *функция* установлена в `None`, то [`imap()`](https://python-all.ru/2.7/library/itertools.html#itertools.imap) возвращает аргументы в виде кортежа. Как [`map()`](https://python-all.ru/2.7/library/functions.html#map), но останавливается, когда самый короткий итерируемый объект исчерпан, вместо заполнения `None` для более коротких итерируемых объектов. Причина различия в том, что аргументы-бесконечные итераторы обычно являются ошибкой для [`map()`](https://python-all.ru/2.7/library/functions.html#map) (поскольку результат полностью вычисляется), но представляют собой распространённый и полезный способ передачи аргументов в [`imap()`](https://python-all.ru/2.7/library/itertools.html#itertools.imap). Примерный эквивалент:320321```python322def imap(function, *iterables):323 # imap(pow, (2,3,10), (5,2,3)) --> 32 9 1000324 iterables = map(iter, iterables)325 while True:326 args = [next(it) for it in iterables]327 if function is None:328 yield tuple(args)329 else:330 yield function(*args)331```332333#### `itertools.islice(iterable, stop)`334335#### `itertools.islice(iterable, start, stop[, step])`336337Создаёт итератор, который возвращает выбранные элементы из итерируемого объекта. Если *start* не равен нулю, то элементы из итерируемого объекта пропускаются до достижения start. Затем элементы возвращаются последовательно, если только *step* не установлен больше единицы, что приводит к пропуску элементов. Если *stop* равен `None`, то итерация продолжается до тех пор, пока итератор не будет исчерпан, если вообще; в противном случае она останавливается на указанной позиции. В отличие от обычной срезки, [`islice()`](https://python-all.ru/2.7/library/itertools.html#itertools.islice) не поддерживает отрицательные значения для *start*, *stop* или *step*. Может использоваться для извлечения связанных полей из данных, где внутренняя структура была уплощена (например, многострочный отчёт может содержать поле имени на каждой третьей строке). Примерно эквивалентно:338339```python340def islice(iterable, *args):341 # islice('ABCDEFG', 2) --> A B342 # islice('ABCDEFG', 2, 4) --> C D343 # islice('ABCDEFG', 2, None) --> C D E F G344 # islice('ABCDEFG', 0, None, 2) --> A C E G345 s = slice(*args)346 start, stop, step = s.start or 0, s.stop or sys.maxint, s.step or 1347 it = iter(xrange(start, stop, step)))348 try:349 nexti = next(it)350 except StopIteration:351 # Потребляет *iterable* до позиции *start*.352 for i, element in izip(xrange(start), iterable):353 pass354 return355 try:356 for i, element in enumerate(iterable):357 if i == nexti:358 yield element359 nexti = next(it)360 except StopIteration:361 # Потребляет до *stop*.362 for i, element in izip(xrange(i + 1, stop), iterable):363 pass364```365366Если *start* равен `None`, то итерация начинается с нуля. Если *step* равен `None`, то шаг по умолчанию равен единице.367368Изменено в версии 2.5: принимаются значения `None` для аргументов по умолчанию *start* и *step*.369370#### `itertools.izip(*iterables)`371372Создаёт итератор, который объединяет элементы из каждого итерируемого объекта. Как [`zip()`](https://python-all.ru/2.7/library/functions.html#zip), за исключением того, что возвращает итератор вместо списка. Используется для синхронного перебора нескольких итерируемых объектов одновременно. Примерный эквивалент:373374```python375def izip(*iterables):376 # izip('ABCD', 'xy') --> Ax By377 iterators = map(iter, iterables)378 while iterators:379 yield tuple(map(next, iterators))380```381382Изменено в версии 2.4: Если итерируемые объекты не указаны, возвращается итератор нулевой длины вместо возбуждения исключения [`TypeError`](https://python-all.ru/2.7/library/exceptions.html#exceptions.TypeError).383384Гарантируется порядок вычисления итерируемых объектов слева направо. Это позволяет использовать идиому для группировки ряда данных в группы длины n с помощью `izip(*[iter(s)]*n)`.385386[`izip()`](https://python-all.ru/2.7/library/itertools.html#itertools.izip) следует использовать только с последовательностями разной длины, если не важны несовпавшие хвостовые значения из более длинных последовательностей. Если эти значения важны, используйте [`izip_longest()`](https://python-all.ru/2.7/library/itertools.html#itertools.izip_longest).387388#### `itertools.izip_longest(*iterables[, fillvalue])`389390Создаёт итератор, который агрегирует элементы из каждого из итерируемых объектов. Если итерируемые объекты имеют разную длину, недостающие значения заполняются с помощью *fillvalue*. Итерация продолжается до тех пор, пока самый длинный итерируемый объект не будет исчерпан. Приблизительно эквивалентно:391392```python393class ZipExhausted(Exception):394 pass395396def izip_longest(*args, **kwds):397 # izip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-398 fillvalue = kwds.get('fillvalue')399 counter = [len(args) - 1]400 def sentinel():401 if not counter[0]:402 raise ZipExhausted403 counter[0] -= 1404 yield fillvalue405 fillers = repeat(fillvalue)406 iterators = [chain(it, sentinel(), fillers) for it in args]407 try:408 while iterators:409 yield tuple(map(next, iterators))410 except ZipExhausted:411 pass412```413414Если один из итерируемых объектов может быть бесконечным, то функцию [`izip_longest()`](https://python-all.ru/2.7/library/itertools.html#itertools.izip_longest) следует обернуть во что-то, ограничивающее количество вызовов (например, [`islice()`](https://python-all.ru/2.7/library/itertools.html#itertools.islice) или [`takewhile()`](https://python-all.ru/2.7/library/itertools.html#itertools.takewhile)). Если не указано, *fillvalue* по умолчанию равен `None`.415416Новое в версии 2.6.417418#### `itertools.permutations(iterable[, r])`419420Возвращает последовательные перестановки длины *r* элементов из *iterable*.421422Если *r* не указан или равен `None`, то *r* по умолчанию равен длине *iterable* и генерируются все возможные перестановки полной длины.423424Перестановки выдаются в лексикографическом порядке. Таким образом, если входной *итерируемый объект* отсортирован, кортежи перестановок будут созданы в отсортированном порядке.425426Элементы считаются уникальными на основе их позиции, а не значения. Поэтому если входные элементы уникальны, то в каждой перестановке не будет повторяющихся значений.427428Примерно эквивалентно:429430```python431def permutations(iterable, r=None):432 # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC433 # permutations(range(3)) --> 012 021 102 120 201 210434 pool = tuple(iterable)435 n = len(pool)436 r = n if r is None else r437 if r > n:438 return439 indices = range(n)440 cycles = range(n, n-r, -1)441 yield tuple(pool[i] for i in indices[:r])442 while n:443 for i in reversed(range(r)):444 cycles[i] -= 1445 if cycles[i] == 0:446 indices[i:] = indices[i+1:] + indices[i:i+1]447 cycles[i] = n - i448 else:449 j = cycles[i]450 indices[i], indices[-j] = indices[-j], indices[i]451 yield tuple(pool[i] for i in indices[:r])452 break453 else:454 return455```456457Код для [`permutations()`](https://python-all.ru/2.7/library/itertools.html#itertools.permutations) также можно выразить как подпоследовательность [`product()`](https://python-all.ru/2.7/library/itertools.html#itertools.product), отфильтрованную для исключения записей с повторяющимися элементами (тех, которые находятся на одной и той же позиции во входном пуле):458459```python460def permutations(iterable, r=None):461 pool = tuple(iterable)462 n = len(pool)463 r = n if r is None else r464 for indices in product(range(n), repeat=r):465 if len(set(indices)) == r:466 yield tuple(pool[i] for i in indices)467```468469Количество возвращаемых элементов равно `n! / (n-r)!`, когда `0 <= r <= n`, или нулю, когда `r > n`.470471Новое в версии 2.6.472473#### `itertools.product(*iterables[, repeat])`474475Декартово произведение входных итерируемых объектов.476477Примерно эквивалентно вложенным циклам for в генераторном выражении. Например, `product(A, B)` возвращает то же, что и `((x,y) for x in A for y in B)`.478479Вложенные циклы работают как одометр: самый правый элемент увеличивается на каждой итерации. Этот шаблон создает лексикографический порядок, так что если входные итерируемые объекты отсортированы, кортежи произведения выдаются в отсортированном порядке.480481Чтобы вычислить произведение итерируемого объекта на самого себя, укажите количество повторений с помощью необязательного именованного аргумента *repeat*. Например, `product(A, repeat=4)` эквивалентно `product(A, A, A, A)`.482483Эта функция примерно эквивалентна следующему коду, за исключением того, что реальная реализация не накапливает промежуточные результаты в памяти:484485```python486def product(*args, **kwds):487 # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy488 # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111489 pools = map(tuple, args) * kwds.get('repeat', 1)490 result = [[]]491 for pool in pools:492 result = [x+[y] for x in result for y in pool]493 for prod in result:494 yield tuple(prod)495```496497Новое в версии 2.6.498499#### `itertools.repeat(object[, times])`500501Создаёт итератор, который снова и снова возвращает *object*. Выполняется бесконечно, если не указан аргумент *times*. Используется как аргумент [`imap()`](https://python-all.ru/2.7/library/itertools.html#itertools.imap) для инвариантных параметров функции. Также используется с [`izip()`](https://python-all.ru/2.7/library/itertools.html#itertools.izip) для создания константных полей в кортеже. Примерный эквивалент:502503```python504def repeat(object, times=None):505 # repeat(10, 3) --> 10 10 10506 if times is None:507 while True:508 yield object509 else:510 for i in xrange(times):511 yield object512```513514Обычное применение *repeat* – подача потока константных значений в *imap* или *zip*:515516```python517>>> list(imap(pow, xrange(10), repeat(2)))518[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]519```520521#### `itertools.starmap(function, iterable)`522523Создаёт итератор, который вычисляет функцию, используя аргументы, полученные из итерируемого объекта. Используется вместо [`imap()`](https://python-all.ru/2.7/library/itertools.html#itertools.imap), когда параметры аргументов уже сгруппированы в кортежи из одного итерируемого объекта (данные были «предварительно сжаты»). Разница между [`imap()`](https://python-all.ru/2.7/library/itertools.html#itertools.imap) и [`starmap()`](https://python-all.ru/2.7/library/itertools.html#itertools.starmap) параллельна различию между `function(a,b)` и `function(*c)`. Примерно эквивалентно:524525```python526def starmap(function, iterable):527 # starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000528 for args in iterable:529 yield function(*args)530```531532Изменено в версии 2.6: Ранее [`starmap()`](https://python-all.ru/2.7/library/itertools.html#itertools.starmap) требовал, чтобы аргументы функции были кортежами. Теперь разрешён любой итерируемый объект.533534#### `itertools.takewhile(predicate, iterable)`535536Создаёт итератор, возвращающий элементы из итерируемого объекта, пока предикат истинен. Приблизительно эквивалентно:537538```python539def takewhile(predicate, iterable):540 # takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4541 for x in iterable:542 if predicate(x):543 yield x544 else:545 break546```547548#### `itertools.tee(iterable[, n=2])`549550Возвращает *n* независимых итераторов из одного итерируемого объекта. Примерно эквивалентно:551552```python553def tee(iterable, n=2):554 it = iter(iterable)555 deques = [collections.deque() for i in range(n)]556 def gen(mydeque):557 while True:558 if not mydeque: # когда локальная deque пуста559 newval = next(it) # извлечь новое значение и560 for d in deques: # загрузить его во все двусторонние очереди561 d.append(newval)562 yield mydeque.popleft()563 return tuple(gen(d) for d in deques)564```565566После того как [`tee()`](https://python-all.ru/2.7/library/itertools.html#itertools.tee) выполнил разделение, исходный *итерируемый объект* не следует использовать где-либо ещё; в противном случае *итерируемый объект* может продвинуться без уведомления объектов tee.567568Итераторы `tee` не являются потокобезопасными. [`RuntimeError`](https://python-all.ru/2.7/library/exceptions.html#exceptions.RuntimeError) может быть возбуждён при одновременном использовании итераторов, возвращённых одним и тем же вызовом [`tee()`](https://python-all.ru/2.7/library/itertools.html#itertools.tee), даже если исходный *iterable* является потокобезопасным.569570Этот инструмент итерации может потребовать значительного вспомогательного хранилища (в зависимости от объёма временных данных, которые необходимо сохранить). В общем случае, если один итератор использует большую часть или все данные до того, как запустится другой итератор, быстрее использовать `list()` вместо [`tee()`](https://python-all.ru/2.7/library/itertools.html#itertools.tee).571572Новое в версии 2.4.573574## 9.7.2. Рецепты575576В этом разделе представлены рецепты для создания расширенного набора инструментов с использованием существующих itertools в качестве строительных блоков.577578Расширенные инструменты обеспечивают такую же высокую производительность, как и базовый набор инструментов. Превосходная производительность по памяти достигается за счёт обработки элементов по одному, а не загрузки всего итерируемого объекта в память сразу. Объём кода остаётся небольшим благодаря связыванию инструментов в функциональном стиле, что помогает избавиться от временных переменных. Высокая скорость сохраняется за счёт предпочтения «векторизованных» строительных блоков вместо использования циклов for и [генераторов](https://python-all.ru/2.7/glossary.html#term-generator), которые создают накладные расходы интерпретатора.579580```python581def take(n, iterable):582 "Return first n items of the iterable as a list"583 return list(islice(iterable, n))584585def tabulate(function, start=0):586 "Return function(0), function(1), ..."587 return imap(function, count(start))588589def consume(iterator, n=None):590 "Advance the iterator n-steps ahead. If n is None, consume entirely."591 # Используйте функции, потребляющие итераторы на скорости C.592 if n is None:593 # передать весь итератор в deque нулевой длины594 collections.deque(iterator, maxlen=0)595 else:596 # перейти к пустому срезу начиная с позиции n597 next(islice(iterator, n, n), None)598599def nth(iterable, n, default=None):600 "Returns the nth item or a default value"601 return next(islice(iterable, n, None), default)602603def all_equal(iterable):604 "Returns True if all the elements are equal to each other"605 g = groupby(iterable)606 return next(g, True) and not next(g, False)607608def quantify(iterable, pred=bool):609 "Count how many times the predicate is true"610 return sum(imap(pred, iterable))611612def padnone(iterable):613 """Возвращает элементы последовательности, а затем бесконечно возвращает None.614615 Полезно для эмуляции поведения встроенной функции map().616 """617 return chain(iterable, repeat(None))618619def ncycles(iterable, n):620 "Returns the sequence elements n times"621 return chain.from_iterable(repeat(tuple(iterable), n))622623def dotproduct(vec1, vec2):624 return sum(imap(operator.mul, vec1, vec2))625626def flatten(listOfLists):627 "Flatten one level of nesting"628 return chain.from_iterable(listOfLists)629630def repeatfunc(func, times=None, *args):631 """Повторяет вызовы func с указанными аргументами.632633 Пример: repeatfunc(random.random)634 """635 if times is None:636 return starmap(func, repeat(args))637 return starmap(func, repeat(args, times))638639def pairwise(iterable):640 "s -> (s0,s1), (s1,s2), (s2, s3), ..."641 a, b = tee(iterable)642 next(b, None)643 return izip(a, b)644645def grouper(iterable, n, fillvalue=None):646 "Collect data into fixed-length chunks or blocks"647 # grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx648 args = [iter(iterable)] * n649 return izip_longest(fillvalue=fillvalue, *args)650651def roundrobin(*iterables):652 "roundrobin('ABC', 'D', 'EF') --> A D E B F C"653 # Автор рецепта – Джордж Саккис654 pending = len(iterables)655 nexts = cycle(iter(it).next for it in iterables)656 while pending:657 try:658 for next in nexts:659 yield next()660 except StopIteration:661 pending -= 1662 nexts = cycle(islice(nexts, pending))663664def powerset(iterable):665 "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"666 s = list(iterable)667 return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))668669def unique_everseen(iterable, key=None):670 "List unique elements, preserving order. Remember all elements ever seen."671 # unique_everseen('AAAABBBCCDAABBB') --> A B C D672 # unique_everseen('ABBCcAD', str.lower) --> A B C D673 seen = set()674 seen_add = seen.add675 if key is None:676 for element in ifilterfalse(seen.__contains__, iterable):677 seen_add(element)678 yield element679 else:680 for element in iterable:681 k = key(element)682 if k not in seen:683 seen_add(k)684 yield element685686def unique_justseen(iterable, key=None):687 "List unique elements, preserving order. Remember only the element just seen."688 # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B689 # unique_justseen('ABBCcAD', str.lower) --> A B C A D690 return imap(next, imap(itemgetter(1), groupby(iterable, key)))691692def iter_except(func, exception, first=None):693 """ Повторно вызывает функцию до возникновения исключения.694695 Преобразует интерфейс вызова до исключения в интерфейс итератора.696 Подобно __builtin__.iter(func, sentinel), но использует исключение вместо этого697 сигнального значения для завершения цикла.698699 Примеры:700 bsddbiter = iter_except(db.next, bsddb.error, db.first)701 heapiter = iter_except(functools.partial(heappop, h), IndexError)702 dictiter = iter_except(d.popitem, KeyError)703 dequeiter = iter_except(d.popleft, IndexError)704 queueiter = iter_except(q.get_nowait, Queue.Empty)705 setiter = iter_except(s.pop, KeyError)706707 """708 try:709 if first is not None:710 yield first()711 while 1:712 yield func()713 except exception:714 pass715716def random_product(*args, **kwds):717 "Random selection from itertools.product(*args, **kwds)"718 pools = map(tuple, args) * kwds.get('repeat', 1)719 return tuple(random.choice(pool) for pool in pools)720721def random_permutation(iterable, r=None):722 "Random selection from itertools.permutations(iterable, r)"723 pool = tuple(iterable)724 r = len(pool) if r is None else r725 return tuple(random.sample(pool, r))726727def random_combination(iterable, r):728 "Random selection from itertools.combinations(iterable, r)"729 pool = tuple(iterable)730 n = len(pool)731 indices = sorted(random.sample(xrange(n), r))732 return tuple(pool[i] for i in indices)733734def random_combination_with_replacement(iterable, r):735 "Random selection from itertools.combinations_with_replacement(iterable, r)"736 pool = tuple(iterable)737 n = len(pool)738 indices = sorted(random.randrange(n) for i in xrange(r))739 return tuple(pool[i] for i in indices)740741def tee_lookahead(t, i):742 """Проверяет i-е следующее значение из объекта tee743 оставляя объект tee на его текущей позиции.744745 Возбуждает IndexError, если базовый итератор не746 имеет достаточного количества значений.747748 """749 for value in islice(t.__copy__(), i, None):750 return value751 raise IndexError(i)752```753754Обратите внимание: многие из приведённых выше рецептов можно оптимизировать, заменив глобальные поиски локальными переменными, определёнными как значения по умолчанию. Например, рецепт *dotproduct* можно записать так:755756```python757def dotproduct(vec1, vec2, sum=sum, imap=imap, mul=operator.mul):758 return sum(imap(mul, vec1, vec2))759```760