itertools.md
1> **Источник:** https://python-all.ru/3.10/library/itertools.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# [`itertools`](https://python-all.ru/3.10/library/itertools.html#module-itertools) – Функции, создающие итераторы для эффективного перебора89---1011Этот модуль реализует ряд строительных блоков [итераторов](https://python-all.ru/3.10/glossary.html#term-iterator), вдохновлённых конструкциями из APL, Haskell и SML. Каждый из них переработан в форму, подходящую для Python.1213Модуль стандартизирует основной набор быстрых и эффективных по памяти инструментов, которые полезны сами по себе или в комбинации. Вместе они образуют «алгебру итераторов», позволяющую создавать специализированные инструменты кратко и эффективно на чистом Python.1415Например, SML предоставляет инструмент табуляции: `tabulate(f)`, который порождает последовательность `f(0), f(1), ...`. Того же эффекта можно достичь в Python скомбинировав [`map()`](https://python-all.ru/3.10/library/functions.html#map) и [`count()`](https://python-all.ru/3.10/library/itertools.html#itertools.count) для получения `map(f, count())`.1617Эти инструменты и их встроенные аналоги также хорошо работают с высокоскоростными функциями из модуля [`operator`](https://python-all.ru/3.10/library/operator.html#module-operator). Например, оператор умножения можно применить к двум векторам, чтобы получить эффективное скалярное произведение: `sum(map(operator.mul, vector1, vector2))`.1819**Бесконечные итераторы:**2021| Итератор | Аргументы | Результаты | Пример |22| --- | --- | --- | --- |23| [`count()`](https://python-all.ru/3.10/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/3.10/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/3.10/library/itertools.html#itertools.repeat) | elem \[,n\] | elem, elem, elem, … бесконечно или до n раз | `repeat(10, 3) --> 10 10 10` |2627**Итераторы, завершающиеся по кратчайшей входной последовательности:**2829| Итератор | Аргументы | Результаты | Пример |30| --- | --- | --- | --- |31| [`accumulate()`](https://python-all.ru/3.10/library/itertools.html#itertools.accumulate) | p \[,func\] | p0, p0+p1, p0+p1+p2, … | `accumulate([1,2,3,4,5]) --> 1 3 6 10 15` |32| [`chain()`](https://python-all.ru/3.10/library/itertools.html#itertools.chain) | p, q, … | p0, p1, … plast, q0, q1, … | `chain('ABC', 'DEF') --> A B C D E F` |33| [`chain.from_iterable()`](https://python-all.ru/3.10/library/itertools.html#itertools.chain.from_iterable) | итерируемый объект | p0, p1, … plast, q0, q1, … | `chain.from_iterable(['ABC', 'DEF']) --> A B C D E F` |34| [`compress()`](https://python-all.ru/3.10/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` |35| [`dropwhile()`](https://python-all.ru/3.10/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` |36| [`filterfalse()`](https://python-all.ru/3.10/library/itertools.html#itertools.filterfalse) | pred, seq | элементы seq, для которых pred(elem) ложно | `filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8` |37| [`groupby()`](https://python-all.ru/3.10/library/itertools.html#itertools.groupby) | iterable\[, key\] | подитераторы, сгруппированные по значению key(v) | |38| [`islice()`](https://python-all.ru/3.10/library/itertools.html#itertools.islice) | seq, \[start,\] stop \[, step\] | элементы из seq\[start:stop:step\] | `islice('ABCDEFG', 2, None) --> C D E F G` |39| [`pairwise()`](https://python-all.ru/3.10/library/itertools.html#itertools.pairwise) | итерируемый объект | (p\[0\], p\[1\]), (p\[1\], p\[2\]) | `pairwise('ABCDEFG') --> AB BC CD DE EF FG` |40| [`starmap()`](https://python-all.ru/3.10/library/itertools.html#itertools.starmap) | func, seq | func(\*seq\[0\]), func(\*seq\[1\]), … | `starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000` |41| [`takewhile()`](https://python-all.ru/3.10/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| [`tee()`](https://python-all.ru/3.10/library/itertools.html#itertools.tee) | it, n | it1, it2, … itn разделяет один итератор на n | |43| [`zip_longest()`](https://python-all.ru/3.10/library/itertools.html#itertools.zip_longest) | p, q, … | (p\[0\], q\[0\]), (p\[1\], q\[1\]), … | `zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-` |4445**Комбинаторные итераторы:**4647| Итератор | Аргументы | Результаты |48| --- | --- | --- |49| [`product()`](https://python-all.ru/3.10/library/itertools.html#itertools.product) | p, q, … \[repeat=1\] | декартово произведение, эквивалентно вложенному циклу for |50| [`permutations()`](https://python-all.ru/3.10/library/itertools.html#itertools.permutations) | p\[, r\] | кортежи длиной r, все возможные перестановки, без повторяющихся элементов |51| [`combinations()`](https://python-all.ru/3.10/library/itertools.html#itertools.combinations) | p, r | кортежи длиной r, в отсортированном порядке, без повторяющихся элементов |52| [`combinations_with_replacement()`](https://python-all.ru/3.10/library/itertools.html#itertools.combinations_with_replacement) | p, r | кортежи длиной r, в отсортированном порядке, с повторяющимися элементами |5354| Примеры | Результаты |55| --- | --- |56| `product('ABCD', repeat=2)` | `AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD` |57| `permutations('ABCD', 2)` | `AB AC AD BA BC BD CA CB CD DA DB DC` |58| `combinations('ABCD', 2)` | `AB AC AD BC BD CD` |59| `combinations_with_replacement('ABCD', 2)` | `AA AB AC AD BB BC BD CC CD DD` |6061## Функции итераторных инструментов6263Следующие функции модуля создают и возвращают итераторы. Некоторые из них порождают потоки бесконечной длины, поэтому обращаться к ним следует только с помощью функций или циклов, которые обрывают поток.6465#### `itertools.accumulate(iterable[, func, *, initial=None])`6667Создаёт итератор, возвращающий накопленные суммы или накопленные результаты других бинарных функций (задаваемых через необязательный аргумент *func*).6869Если передан аргумент *func*, он должен быть функцией двух аргументов. Элементы входного *iterable* могут быть любого типа, который может быть принят как аргумент *func*. (Например, при операции сложения по умолчанию элементы могут быть любого суммируемого типа, включая [`Decimal`](https://python-all.ru/3.10/library/decimal.html#decimal.Decimal) или [`Fraction`](https://python-all.ru/3.10/library/fractions.html#fractions.Fraction).)7071Обычно количество элементов вывода соответствует входному итерабельному объекту. Однако если указан именованный аргумент *initial*, накопление начинается со значения *initial*, так что в выводе оказывается на один элемент больше, чем во входном итерабельном объекте.7273Примерно эквивалентно:7475```python76def accumulate(iterable, func=operator.add, *, initial=None):77 'Return running totals'78 # accumulate([1,2,3,4,5]) --> 1 3 6 10 1579 # accumulate([1,2,3,4,5], initial=100) --> 100 101 103 106 110 11580 # accumulate([1,2,3,4,5], operator.mul) --> 1 2 6 24 12081 it = iter(iterable)82 total = initial83 if initial is None:84 try:85 total = next(it)86 except StopIteration:87 return88 yield total89 for element in it:90 total = func(total, element)91 yield total92```9394У аргумента *func* есть несколько применений. Его можно установить в [`min()`](https://python-all.ru/3.10/library/functions.html#min) для текущего минимума, [`max()`](https://python-all.ru/3.10/library/functions.html#max) для текущего максимума или [`operator.mul()`](https://python-all.ru/3.10/library/operator.html#operator.mul) для текущего произведения. Таблицы амортизации можно построить, накапливая проценты и применяя платежи. [Рекуррентные соотношения](https://python-all.ru/3.10/library/itertools.html) первого порядка можно смоделировать, передав начальное значение в итерируемом объекте и используя только накопленную сумму в аргументе *func*:9596```python97>>> data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8]98>>> list(accumulate(data, operator.mul)) # текущее произведение99[3, 12, 72, 144, 144, 1296, 0, 0, 0, 0]100>>> list(accumulate(data, max)) # текущий максимум101[3, 4, 6, 6, 6, 9, 9, 9, 9, 9]102103# Amortize a 5% loan of 1000 with 4 annual payments of 90104>>> cashflows = [1000, -90, -90, -90, -90]105>>> list(accumulate(cashflows, lambda bal, pmt: bal*1.05 + pmt))106[1000, 960.0, 918.0, 873.9000000000001, 827.5950000000001]107108# Chaotic recurrence relation https://en.wikipedia.org/wiki/Logistic_map109>>> logistic_map = lambda x, _: r * x * (1 - x)110>>> r = 3.8111>>> x0 = 0.4112>>> inputs = repeat(x0, 36) # используется только начальное значение113>>> [format(x, '.2f') for x in accumulate(inputs, logistic_map)]114['0.40', '0.91', '0.30', '0.81', '0.60', '0.92', '0.29', '0.79', '0.63',115 '0.88', '0.39', '0.90', '0.33', '0.84', '0.52', '0.95', '0.18', '0.57',116 '0.93', '0.25', '0.71', '0.79', '0.63', '0.88', '0.39', '0.91', '0.32',117 '0.83', '0.54', '0.95', '0.20', '0.60', '0.91', '0.30', '0.80', '0.60']118```119120См. [`functools.reduce()`](https://python-all.ru/3.10/library/functools.html#functools.reduce) – похожая функция, возвращающая только итоговое накопленное значение.121122Новое в версии 3.2.123124Изменено в версии 3.3: Добавлен необязательный параметр *func*.125126Изменено в версии 3.8: Добавлен необязательный параметр *initial*.127128#### `itertools.chain(*iterables)`129130Создаёт итератор, который возвращает элементы из первого итерируемого объекта, пока он не будет исчерпан, затем переходит к следующему, пока все итерируемые объекты не будут исчерпаны. Используется для объединения последовательностей в одну. Приблизительный эквивалент:131132```python133def chain(*iterables):134 # chain('ABC', 'DEF') --> A B C D E F135 for it in iterables:136 for element in it:137 yield element138```139140#### `classmethod chain.from_iterable(iterable)`141142Альтернативный конструктор для [`chain()`](https://python-all.ru/3.10/library/itertools.html#itertools.chain). Получает цепочку входных данных из одного аргумента iterable, который вычисляется лениво. Примерная реализация:143144```python145def from_iterable(iterables):146 # chain.from_iterable(['ABC', 'DEF']) --> A B C D E F147 for it in iterables:148 for element in it:149 yield element150```151152#### `itertools.combinations(iterable, r)`153154Возвращает подпоследовательности элементов длины *r* из входного *iterable*.155156Кортежи комбинаций порождаются в лексикографическом порядке в соответствии с порядком входного *итерируемого объекта*. Таким образом, если входной *итерируемый объект* отсортирован, то и кортежи комбинаций будут созданы в отсортированном порядке.157158Элементы считаются уникальными на основе их позиции, а не значения. Поэтому если входные элементы уникальны, то в каждой комбинации не будет повторяющихся значений.159160Примерно эквивалентно:161162```python163def combinations(iterable, r):164 # combinations('ABCD', 2) --> AB AC AD BC BD CD165 # combinations(range(4), 3) --> 012 013 023 123166 pool = tuple(iterable)167 n = len(pool)168 if r > n:169 return170 indices = list(range(r))171 yield tuple(pool[i] for i in indices)172 while True:173 for i in reversed(range(r)):174 if indices[i] != i + n - r:175 break176 else:177 return178 indices[i] += 1179 for j in range(i+1, r):180 indices[j] = indices[j-1] + 1181 yield tuple(pool[i] for i in indices)182```183184Код для [`combinations()`](https://python-all.ru/3.10/library/itertools.html#itertools.combinations) можно также выразить как подпоследовательность [`permutations()`](https://python-all.ru/3.10/library/itertools.html#itertools.permutations) после фильтрации записей, где элементы не находятся в отсортированном порядке (согласно их позиции во входном пуле):185186```python187def combinations(iterable, r):188 pool = tuple(iterable)189 n = len(pool)190 for indices in permutations(range(n), r):191 if sorted(indices) == list(indices):192 yield tuple(pool[i] for i in indices)193```194195Количество возвращаемых элементов равно `n! / r! / (n-r)!`, когда `0 <= r <= n`, или нулю, когда `r > n`.196197#### `itertools.combinations_with_replacement(iterable, r)`198199Возвращает подпоследовательности элементов длины *r* из входного *iterable*, допуская повторение отдельных элементов.200201Кортежи комбинаций порождаются в лексикографическом порядке в соответствии с порядком входного *итерируемого объекта*. Таким образом, если входной *итерируемый объект* отсортирован, то и кортежи комбинаций будут созданы в отсортированном порядке.202203Элементы считаются уникальными по их позиции, а не по значению. Поэтому если входные элементы уникальны, сгенерированные комбинации также будут уникальны.204205Примерно эквивалентно:206207```python208def combinations_with_replacement(iterable, r):209 # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC210 pool = tuple(iterable)211 n = len(pool)212 if not n and r:213 return214 indices = [0] * r215 yield tuple(pool[i] for i in indices)216 while True:217 for i in reversed(range(r)):218 if indices[i] != n - 1:219 break220 else:221 return222 indices[i:] = [indices[i] + 1] * (r - i)223 yield tuple(pool[i] for i in indices)224```225226Код для [`combinations_with_replacement()`](https://python-all.ru/3.10/library/itertools.html#itertools.combinations_with_replacement) можно также выразить как подпоследовательность [`product()`](https://python-all.ru/3.10/library/itertools.html#itertools.product) после фильтрации записей, где элементы не находятся в отсортированном порядке (согласно их позиции во входном пуле):227228```python229def combinations_with_replacement(iterable, r):230 pool = tuple(iterable)231 n = len(pool)232 for indices in product(range(n), repeat=r):233 if sorted(indices) == list(indices):234 yield tuple(pool[i] for i in indices)235```236237Количество возвращаемых элементов равно `(n+r-1)! / r! / (n-1)!`, когда `n > 0`.238239Новое в версии 3.1.240241#### `itertools.compress(data, selectors)`242243Создаёт итератор, который фильтрует элементы из *data*, возвращая только те, для которых в *selectors* есть соответствующий элемент, вычисляемый как `True`. Останавливается, когда исчерпан либо итерабельный объект *data*, либо *selectors*. Примерно эквивалентен:244245```python246def compress(data, selectors):247 # compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F248 return (d for d, s in zip(data, selectors) if s)249```250251Новое в версии 3.1.252253#### `itertools.count(start=0, step=1)`254255Создаёт итератор, возвращающий равномерно распределённые значения, начиная с числа *start*. Часто используется как аргумент для [`map()`](https://python-all.ru/3.10/library/functions.html#map) для генерации последовательных точек данных. Также используется с [`zip()`](https://python-all.ru/3.10/library/functions.html#zip) для добавления порядковых номеров. Примерно эквивалентен:256257```python258def count(start=0, step=1):259 # count(10) --> 10 11 12 13 14 ...260 # count(2.5, 0.5) -> 2.5 3.0 3.5 ...261 n = start262 while True:263 yield n264 n += step265```266267При подсчёте с числами с плавающей запятой иногда можно добиться лучшей точности, заменив код на мультипликативный, например: `(start + step * i for i in count())`.268269Изменено в версии 3.1: Добавлен аргумент *step* и разрешены нецелые аргументы.270271#### `itertools.cycle(iterable)`272273Создаёт итератор, возвращающий элементы из итерабельного объекта и сохраняющий копию каждого. Когда итерабельный объект исчерпан, возвращает элементы из сохранённой копии. Повторяется бесконечно. Примерно эквивалентен:274275```python276def cycle(iterable):277 # cycle('ABCD') --> A B C D A B C D A B C D ...278 saved = []279 for element in iterable:280 yield element281 saved.append(element)282 while saved:283 for element in saved:284 yield element285```286287Примечание: этот элемент набора инструментов может потребовать значительного дополнительного хранилища (в зависимости от длины итерабельного объекта).288289#### `itertools.dropwhile(predicate, iterable)`290291Создаёт итератор, который отбрасывает элементы из итерабельного объекта, пока предикат истинен; после этого возвращает каждый элемент. Примечание: итератор не выдаёт *никакого* вывода, пока предикат впервые не станет ложным, поэтому время запуска может быть большим. Примерно эквивалентен:292293```python294def dropwhile(predicate, iterable):295 # dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1296 iterable = iter(iterable)297 for x in iterable:298 if not predicate(x):299 yield x300 break301 for x in iterable:302 yield x303```304305#### `itertools.filterfalse(predicate, iterable)`306307Создаёт итератор, который фильтрует элементы из итерируемого объекта, возвращая только те, для которых предикат равен `False`. Если *предикат* равен `None`, возвращает элементы, которые являются ложными. Примерно эквивалентно:308309```python310def filterfalse(predicate, iterable):311 # filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8312 if predicate is None:313 predicate = bool314 for x in iterable:315 if not predicate(x):316 yield x317```318319#### `itertools.groupby(iterable, key=None)`320321Make 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.322323Работа [`groupby()`](https://python-all.ru/3.10/library/itertools.html#itertools.groupby) аналогична фильтру `uniq` в Unix. Она создает разрыв или новую группу каждый раз, когда изменяется значение ключевой функции (поэтому обычно необходимо отсортировать данные с помощью той же ключевой функции). Такое поведение отличается от SQL GROUP BY, которая объединяет общие элементы независимо от порядка их ввода.324325Возвращаемая группа сама является итератором, который использует общий исходный итерируемый объект с [`groupby()`](https://python-all.ru/3.10/library/itertools.html#itertools.groupby). Поскольку источник общий, при продвижении объекта [`groupby()`](https://python-all.ru/3.10/library/itertools.html#itertools.groupby) предыдущая группа перестает быть видимой. Поэтому, если эти данные понадобятся позже, их следует сохранить в виде списка:326327```python328groups = []329uniquekeys = []330data = sorted(data, key=keyfunc)331for k, g in groupby(data, keyfunc):332 groups.append(list(g)) # Сохранить групповой итератор как список333 uniquekeys.append(k)334```335336[`groupby()`](https://python-all.ru/3.10/library/itertools.html#itertools.groupby) примерно эквивалентно:337338```python339class groupby:340 # [k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B341 # [list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D342 def __init__(self, iterable, key=None):343 if key is None:344 key = lambda x: x345 self.keyfunc = key346 self.it = iter(iterable)347 self.tgtkey = self.currkey = self.currvalue = object()348 def __iter__(self):349 return self350 def __next__(self):351 self.id = object()352 while self.currkey == self.tgtkey:353 self.currvalue = next(self.it) # Выход при StopIteration354 self.currkey = self.keyfunc(self.currvalue)355 self.tgtkey = self.currkey356 return (self.currkey, self._grouper(self.tgtkey, self.id))357 def _grouper(self, tgtkey, id):358 while self.id is id and self.currkey == tgtkey:359 yield self.currvalue360 try:361 self.currvalue = next(self.it)362 except StopIteration:363 return364 self.currkey = self.keyfunc(self.currvalue)365```366367#### `itertools.islice(iterable, stop)`368369#### `itertools.islice(iterable, start, stop[, step])`370371Создаёт итератор, который возвращает выбранные элементы из итерируемого объекта. Если *start* не равен нулю, то элементы из итерируемого объекта пропускаются до достижения start. Затем элементы возвращаются последовательно, если только *step* не установлен больше единицы, что приводит к пропуску элементов. Если *stop* равен `None`, то итерация продолжается до тех пор, пока итератор не будет исчерпан, если вообще; в противном случае она останавливается на указанной позиции. В отличие от обычной срезки, [`islice()`](https://python-all.ru/3.10/library/itertools.html#itertools.islice) не поддерживает отрицательные значения для *start*, *stop* или *step*. Может использоваться для извлечения связанных полей из данных, где внутренняя структура была уплощена (например, многострочный отчёт может содержать поле имени на каждой третьей строке). Примерно эквивалентно:372373```python374def islice(iterable, *args):375 # islice('ABCDEFG', 2) --> A B376 # islice('ABCDEFG', 2, 4) --> C D377 # islice('ABCDEFG', 2, None) --> C D E F G378 # islice('ABCDEFG', 0, None, 2) --> A C E G379 s = slice(*args)380 start, stop, step = s.start or 0, s.stop or sys.maxsize, s.step or 1381 it = iter(range(start, stop, step))382 try:383 nexti = next(it)384 except StopIteration:385 # Потребляет *iterable* до позиции *start*.386 for i, element in zip(range(start), iterable):387 pass388 return389 try:390 for i, element in enumerate(iterable):391 if i == nexti:392 yield element393 nexti = next(it)394 except StopIteration:395 # Потребляет до *stop*.396 for i, element in zip(range(i + 1, stop), iterable):397 pass398```399400Если *start* равен `None`, то итерация начинается с нуля. Если *step* равен `None`, то шаг по умолчанию равен единице.401402#### `itertools.pairwise(iterable)`403404Возвращает последовательные перекрывающиеся пары, взятые из входного *iterable*.405406Количество кортежей из двух элементов в выходном итераторе будет на один меньше, чем количество входных элементов. Он будет пустым, если входной итерируемый объект содержит менее двух значений.407408Примерно эквивалентно:409410```python411def pairwise(iterable):412 # pairwise('ABCDEFG') --> AB BC CD DE EF FG413 a, b = tee(iterable)414 next(b, None)415 return zip(a, b)416```417418Новое в версии 3.10.419420#### `itertools.permutations(iterable, r=None)`421422Возвращает последовательные перестановки длины *r* элементов из *iterable*.423424Если *r* не указан или равен `None`, то *r* по умолчанию равен длине *iterable* и генерируются все возможные перестановки полной длины.425426Кортежи перестановок порождаются в лексикографическом порядке в соответствии с порядком входного *итерируемого объекта*. Таким образом, если входной *итерируемый объект* отсортирован, то и кортежи комбинаций будут созданы в отсортированном порядке.427428Элементы считаются уникальными на основе их позиции, а не значения. Поэтому если входные элементы уникальны, то в каждой перестановке не будет повторяющихся значений.429430Примерно эквивалентно:431432```python433def permutations(iterable, r=None):434 # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC435 # permutations(range(3)) --> 012 021 102 120 201 210436 pool = tuple(iterable)437 n = len(pool)438 r = n if r is None else r439 if r > n:440 return441 indices = list(range(n))442 cycles = list(range(n, n-r, -1))443 yield tuple(pool[i] for i in indices[:r])444 while n:445 for i in reversed(range(r)):446 cycles[i] -= 1447 if cycles[i] == 0:448 indices[i:] = indices[i+1:] + indices[i:i+1]449 cycles[i] = n - i450 else:451 j = cycles[i]452 indices[i], indices[-j] = indices[-j], indices[i]453 yield tuple(pool[i] for i in indices[:r])454 break455 else:456 return457```458459Код для [`permutations()`](https://python-all.ru/3.10/library/itertools.html#itertools.permutations) также можно выразить как подпоследовательность [`product()`](https://python-all.ru/3.10/library/itertools.html#itertools.product), отфильтрованную для исключения записей с повторяющимися элементами (тех, которые находятся на одной и той же позиции во входном пуле):460461```python462def permutations(iterable, r=None):463 pool = tuple(iterable)464 n = len(pool)465 r = n if r is None else r466 for indices in product(range(n), repeat=r):467 if len(set(indices)) == r:468 yield tuple(pool[i] for i in indices)469```470471Количество возвращаемых элементов равно `n! / (n-r)!`, когда `0 <= r <= n`, или нулю, когда `r > n`.472473#### `itertools.product(*iterables, repeat=1)`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, repeat=1):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 = [tuple(pool) for pool in args] * repeat490 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Перед запуском [`product()`](https://python-all.ru/3.10/library/itertools.html#itertools.product) полностью потребляет входные итерируемые объекты, сохраняя пулы значений в памяти для генерации произведений. Соответственно, она полезна только для конечных входных данных.498499#### `itertools.repeat(object[, times])`500501Создаёт итератор, который снова и снова возвращает *object*. Выполняется бесконечно, если не указан аргумент *times*. Используется как аргумент [`map()`](https://python-all.ru/3.10/library/functions.html#map) для инвариантных параметров вызываемой функции. Также используется с [`zip()`](https://python-all.ru/3.10/library/functions.html#zip) для создания инвариантной части кортежной записи.502503Примерно эквивалентно:504505```python506def repeat(object, times=None):507 # repeat(10, 3) --> 10 10 10508 if times is None:509 while True:510 yield object511 else:512 for i in range(times):513 yield object514```515516Обычное применение *repeat* – передача потока постоянных значений в *map* или *zip*:517518```python519>>> list(map(pow, range(10), repeat(2)))520[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]521```522523#### `itertools.starmap(function, iterable)`524525Создаёт итератор, который вычисляет функцию, используя аргументы, полученные из итерируемого объекта. Используется вместо [`map()`](https://python-all.ru/3.10/library/functions.html#map), когда параметры аргументов уже сгруппированы в кортежи из одного итерируемого объекта (данные были «предварительно сжаты»). Разница между [`map()`](https://python-all.ru/3.10/library/functions.html#map) и [`starmap()`](https://python-all.ru/3.10/library/itertools.html#itertools.starmap) параллельна различию между `function(a,b)` и `function(*c)`. Примерно эквивалентно:526527```python528def starmap(function, iterable):529 # starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000530 for args in iterable:531 yield function(*args)532```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Следующий код на Python помогает объяснить, что делает *tee* (хотя реальная реализация более сложна и использует только одну базовую очередь FIFO).553554Примерно эквивалентно:555556```python557def tee(iterable, n=2):558 it = iter(iterable)559 deques = [collections.deque() for i in range(n)]560 def gen(mydeque):561 while True:562 if not mydeque: # когда локальная deque пуста563 try:564 newval = next(it) # извлечь новое значение и565 except StopIteration:566 return567 for d in deques: # загрузить его во все двусторонние очереди568 d.append(newval)569 yield mydeque.popleft()570 return tuple(gen(d) for d in deques)571```572573После того как [`tee()`](https://python-all.ru/3.10/library/itertools.html#itertools.tee) выполнил разделение, исходный *итерируемый объект* не следует использовать где-либо ещё; в противном случае *итерируемый объект* может продвинуться без уведомления объектов tee.574575Итераторы `tee` не являются потокобезопасными. [`RuntimeError`](https://python-all.ru/3.10/library/exceptions.html#RuntimeError) может быть возбуждён при одновременном использовании итераторов, возвращённых одним и тем же вызовом [`tee()`](https://python-all.ru/3.10/library/itertools.html#itertools.tee), даже если исходный *iterable* является потокобезопасным.576577Этот инструмент итерации может потребовать значительного вспомогательного хранилища (в зависимости от объёма временных данных, которые необходимо сохранить). В общем случае, если один итератор использует большую часть или все данные до того, как запустится другой итератор, быстрее использовать [`list()`](https://python-all.ru/3.10/library/stdtypes.html#list) вместо [`tee()`](https://python-all.ru/3.10/library/itertools.html#itertools.tee).578579#### `itertools.zip_longest(*iterables, fillvalue=None)`580581Создаёт итератор, который агрегирует элементы из каждого из итерируемых объектов. Если итерируемые объекты имеют разную длину, недостающие значения заполняются с помощью *fillvalue*. Итерация продолжается до тех пор, пока самый длинный итерируемый объект не будет исчерпан. Приблизительно эквивалентно:582583```python584def zip_longest(*args, fillvalue=None):585 # zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-586 iterators = [iter(it) for it in args]587 num_active = len(iterators)588 if not num_active:589 return590 while True:591 values = []592 for i, it in enumerate(iterators):593 try:594 value = next(it)595 except StopIteration:596 num_active -= 1597 if not num_active:598 return599 iterators[i] = repeat(fillvalue)600 value = fillvalue601 values.append(value)602 yield tuple(values)603```604605Если один из итерируемых объектов потенциально бесконечен, то функцию [`zip_longest()`](https://python-all.ru/3.10/library/itertools.html#itertools.zip_longest) следует обернуть чем-то, что ограничивает количество вызовов (например, [`islice()`](https://python-all.ru/3.10/library/itertools.html#itertools.islice) или [`takewhile()`](https://python-all.ru/3.10/library/itertools.html#itertools.takewhile)). Если не указано, *fillvalue* по умолчанию равен `None`.606607## Рецепты itertools608609В этом разделе представлены рецепты для создания расширенного набора инструментов с использованием существующих itertools в качестве строительных блоков.610611Практически все эти рецепты и многие-многие другие можно установить из проекта [more-itertools](https://python-all.ru/3.10/library/itertools.html), который находится в Python Package Index:612613```python614pip install more-itertools615```616617Расширенные инструменты обеспечивают такую же высокую производительность, как и базовый набор инструментов. Превосходная производительность по памяти достигается за счёт обработки элементов по одному, а не загрузки всего итерируемого объекта в память сразу. Объём кода остаётся небольшим благодаря связыванию инструментов в функциональном стиле, что помогает избавиться от временных переменных. Высокая скорость сохраняется за счёт предпочтения «векторизованных» строительных блоков вместо использования циклов for и [генераторов](https://python-all.ru/3.10/glossary.html#term-generator), которые создают накладные расходы интерпретатора.618619```python620def take(n, iterable):621 "Return first n items of the iterable as a list"622 return list(islice(iterable, n))623624def prepend(value, iterator):625 "Prepend a single value in front of an iterator"626 # prepend(1, [2, 3, 4]) -> 1 2 3 4627 return chain([value], iterator)628629def tabulate(function, start=0):630 "Return function(0), function(1), ..."631 return map(function, count(start))632633def tail(n, iterable):634 "Return an iterator over the last n items"635 # tail(3, 'ABCDEFG') --> E F G636 return iter(collections.deque(iterable, maxlen=n))637638def consume(iterator, n=None):639 "Advance the iterator n-steps ahead. If n is None, consume entirely."640 # Используйте функции, потребляющие итераторы на скорости C.641 if n is None:642 # передать весь итератор в deque нулевой длины643 collections.deque(iterator, maxlen=0)644 else:645 # перейти к пустому срезу начиная с позиции n646 next(islice(iterator, n, n), None)647648def nth(iterable, n, default=None):649 "Returns the nth item or a default value"650 return next(islice(iterable, n, None), default)651652def all_equal(iterable):653 "Returns True if all the elements are equal to each other"654 g = groupby(iterable)655 return next(g, True) and not next(g, False)656657def quantify(iterable, pred=bool):658 "Count how many times the predicate is true"659 return sum(map(pred, iterable))660661def pad_none(iterable):662 """Возвращает элементы последовательности, а затем бесконечно возвращает None.663664 Полезно для эмуляции поведения встроенной функции map().665 """666 return chain(iterable, repeat(None))667668def ncycles(iterable, n):669 "Returns the sequence elements n times"670 return chain.from_iterable(repeat(tuple(iterable), n))671672def dotproduct(vec1, vec2):673 return sum(map(operator.mul, vec1, vec2))674675def convolve(signal, kernel):676 # См.: https://betterexplained.com/articles/intuitive-convolution/677 # convolve(data, [0.25, 0.25, 0.25, 0.25]) --> Скользящее среднее (размытие)678 # convolve(data, [1, -1]) --> Первая конечная разность (первая производная)679 # convolve(data, [1, -2, 1]) --> Вторая конечная разность (вторая производная)680 kernel = tuple(kernel)[::-1]681 n = len(kernel)682 window = collections.deque([0], maxlen=n) * n683 for x in chain(signal, repeat(0, n-1)):684 window.append(x)685 yield sum(map(operator.mul, kernel, window))686687def flatten(list_of_lists):688 "Flatten one level of nesting"689 return chain.from_iterable(list_of_lists)690691def repeatfunc(func, times=None, *args):692 """Повторяет вызовы func с указанными аргументами.693694 Пример: repeatfunc(random.random)695 """696 if times is None:697 return starmap(func, repeat(args))698 return starmap(func, repeat(args, times))699700def grouper(iterable, n, *, incomplete='fill', fillvalue=None):701 "Collect data into non-overlapping fixed-length chunks or blocks"702 # grouper('ABCDEFG', 3, fillvalue='x') --> ABC DEF Gxx703 # grouper('ABCDEFG', 3, incomplete='strict') --> ABC DEF ValueError704 # grouper('ABCDEFG', 3, incomplete='ignore') --> ABC DEF705 args = [iter(iterable)] * n706 if incomplete == 'fill':707 return zip_longest(*args, fillvalue=fillvalue)708 if incomplete == 'strict':709 return zip(*args, strict=True)710 if incomplete == 'ignore':711 return zip(*args)712 else:713 raise ValueError('Expected fill, strict, or ignore')714715def triplewise(iterable):716 "Return overlapping triplets from an iterable"717 # triplewise('ABCDEFG') -> ABC BCD CDE DEF EFG718 for (a, _), (b, c) in pairwise(pairwise(iterable)):719 yield a, b, c720721def sliding_window(iterable, n):722 # sliding_window('ABCDEFG', 4) -> ABCD BCDE CDEF DEFG723 it = iter(iterable)724 window = collections.deque(islice(it, n), maxlen=n)725 if len(window) == n:726 yield tuple(window)727 for x in it:728 window.append(x)729 yield tuple(window)730731def roundrobin(*iterables):732 "roundrobin('ABC', 'D', 'EF') --> A D E B F C"733 # Автор рецепта – Джордж Саккис734 num_active = len(iterables)735 nexts = cycle(iter(it).__next__ for it in iterables)736 while num_active:737 try:738 for next in nexts:739 yield next()740 except StopIteration:741 # Удалить из цикла только что исчерпанный итератор.742 num_active -= 1743 nexts = cycle(islice(nexts, num_active))744745def partition(pred, iterable):746 "Use a predicate to partition entries into false entries and true entries"747 # partition(is_odd, range(10)) --> 0 2 4 6 8 and 1 3 5 7 9748 t1, t2 = tee(iterable)749 return filterfalse(pred, t1), filter(pred, t2)750751def before_and_after(predicate, it):752 """ Вариант takewhile(), который позволяет полностью753 доступ к остатку итератора.754755 >>> it = iter('ABCdEfGhI')756 >>> all_upper, remainder = before_and_after(str.isupper, it)757 >>> ''.join(all_upper)758 'ABC'759 >>> ''.join(remainder) # takewhile() потерял бы 'd'760 'dEfGhI'761762 Обратите внимание, что первый итератор должен быть полностью763 использован до того, как второй итератор сможет764 сгенерировать корректные результаты.765 """766 it = iter(it)767 transition = []768 def true_iterator():769 for elem in it:770 if predicate(elem):771 yield elem772 else:773 transition.append(elem)774 return775 def remainder_iterator():776 yield from transition777 yield from it778 return true_iterator(), remainder_iterator()779780def subslices(seq):781 "Return all contiguous non-empty subslices of a sequence"782 # subslices('ABCD') --> A AB ABC ABCD B BC BCD C CD D783 slices = starmap(slice, combinations(range(len(seq) + 1), 2))784 return map(operator.getitem, repeat(seq), slices)785786def powerset(iterable):787 "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"788 s = list(iterable)789 return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))790791def unique_everseen(iterable, key=None):792 "List unique elements, preserving order. Remember all elements ever seen."793 # unique_everseen('AAAABBBCCDAABBB') --> A B C D794 # unique_everseen('ABBCcAD', str.lower) --> A B C D795 seen = set()796 seen_add = seen.add797 if key is None:798 for element in filterfalse(seen.__contains__, iterable):799 seen_add(element)800 yield element801 else:802 for element in iterable:803 k = key(element)804 if k not in seen:805 seen_add(k)806 yield element807808def unique_justseen(iterable, key=None):809 "List unique elements, preserving order. Remember only the element just seen."810 # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B811 # unique_justseen('ABBCcAD', str.lower) --> A B C A D812 return map(next, map(operator.itemgetter(1), groupby(iterable, key)))813814def iter_except(func, exception, first=None):815 """ Повторно вызывает функцию до возникновения исключения.816817 Преобразует интерфейс вызова до исключения в интерфейс итератора.818 Как builtins.iter(func, sentinel), но использует исключение вместо819 сигнального значения для завершения цикла.820821 Примеры:822 iter_except(functools.partial(heappop, h), IndexError) # итератор очереди с приоритетом823 iter_except(d.popitem, KeyError) # итератор словаря без блокировки824 iter_except(d.popleft, IndexError) # итератор дека без блокировки825 iter_except(q.get_nowait, Queue.Empty) # цикл по очереди производителя826 iter_except(s.pop, KeyError) # итератор множества без блокировки827828 """829 try:830 if first is not None:831 yield first() # Для API баз данных, требующих первоначального приведения к db.first()832 while True:833 yield func()834 except exception:835 pass836837def first_true(iterable, default=False, pred=None):838 """Возвращает первое истинное значение в итерируемом объекте.839840 Если истинное значение не найдено, возвращает *default*841842 Если *pred* не равен None, возвращает первый элемент843 для которого pred(item) истинно.844845 """846 # first_true([a,b,c], x) --> a or b or c or x847 # first_true([a,b], x, f) --> a if f(a) else b if f(b) else x848 return next(filter(pred, iterable), default)849850def random_product(*args, repeat=1):851 "Random selection from itertools.product(*args, **kwds)"852 pools = [tuple(pool) for pool in args] * repeat853 return tuple(map(random.choice, pools))854855def random_permutation(iterable, r=None):856 "Random selection from itertools.permutations(iterable, r)"857 pool = tuple(iterable)858 r = len(pool) if r is None else r859 return tuple(random.sample(pool, r))860861def random_combination(iterable, r):862 "Random selection from itertools.combinations(iterable, r)"863 pool = tuple(iterable)864 n = len(pool)865 indices = sorted(random.sample(range(n), r))866 return tuple(pool[i] for i in indices)867868def random_combination_with_replacement(iterable, r):869 "Random selection from itertools.combinations_with_replacement(iterable, r)"870 pool = tuple(iterable)871 n = len(pool)872 indices = sorted(random.choices(range(n), k=r))873 return tuple(pool[i] for i in indices)874875def nth_combination(iterable, r, index):876 "Equivalent to list(combinations(iterable, r))[index]"877 pool = tuple(iterable)878 n = len(pool)879 if r < 0 or r > n:880 raise ValueError881 c = 1882 k = min(r, n-r)883 for i in range(1, k+1):884 c = c * (n - k + i) // i885 if index < 0:886 index += c887 if index < 0 or index >= c:888 raise IndexError889 result = []890 while r:891 c, n, r = c*r//n, n-1, r-1892 while index >= c:893 index -= c894 c, n = c*(n-r)//n, n-1895 result.append(pool[-1-n])896 return tuple(result)897```898