itertools.md
1> **Источник:** https://python-all.ru/3.11/library/itertools.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# [`itertools`](https://python-all.ru/3.11/library/itertools.html#module-itertools) – Функции, создающие итераторы для эффективного перебора89---1011Этот модуль реализует ряд строительных блоков [итераторов](https://python-all.ru/3.11/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.11/library/functions.html#map) и [`count()`](https://python-all.ru/3.11/library/itertools.html#itertools.count) для получения `map(f, count())`.1617Эти инструменты и их встроенные аналоги также хорошо работают с высокоскоростными функциями из модуля [`operator`](https://python-all.ru/3.11/library/operator.html#module-operator). Например, оператор умножения можно применить к двум векторам, чтобы получить эффективное скалярное произведение: `sum(starmap(operator.mul, zip(vec1, vec2, strict=True)))`.1819**Бесконечные итераторы:**2021| Итератор | Аргументы | Результаты | Пример |22| --- | --- | --- | --- |23| [`count()`](https://python-all.ru/3.11/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.11/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.11/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.11/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.11/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.11/library/itertools.html#itertools.chain.from_iterable) | iterable | p0, p1, … plast, q0, q1, … | `chain.from_iterable(['ABC', 'DEF']) --> A B C D E F` |34| [`compress()`](https://python-all.ru/3.11/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.11/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.11/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.11/library/itertools.html#itertools.groupby) | iterable\[, key\] | подитераторы, сгруппированные по значению key(v) | |38| [`islice()`](https://python-all.ru/3.11/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.11/library/itertools.html#itertools.pairwise) | iterable | (p\[0\], p\[1\]), (p\[1\], p\[2\]) | `pairwise('ABCDEFG') --> AB BC CD DE EF FG` |40| [`starmap()`](https://python-all.ru/3.11/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.11/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.11/library/itertools.html#itertools.tee) | it, n | it1, it2, … itn разделяет один итератор на n | |43| [`zip_longest()`](https://python-all.ru/3.11/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.11/library/itertools.html#itertools.product) | p, q, … \[repeat=1\] | декартово произведение, эквивалентно вложенному циклу for |50| [`permutations()`](https://python-all.ru/3.11/library/itertools.html#itertools.permutations) | p\[, r\] | кортежи длиной r, все возможные перестановки, без повторяющихся элементов |51| [`combinations()`](https://python-all.ru/3.11/library/itertools.html#itertools.combinations) | p, r | кортежи длиной r, в отсортированном порядке, без повторяющихся элементов |52| [`combinations_with_replacement()`](https://python-all.ru/3.11/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.11/library/decimal.html#decimal.Decimal) или [`Fraction`](https://python-all.ru/3.11/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.11/library/functions.html#min) для текущего минимума, [`max()`](https://python-all.ru/3.11/library/functions.html#max) для текущего максимума или [`operator.mul()`](https://python-all.ru/3.11/library/operator.html#operator.mul) для текущего произведения. Таблицы амортизации можно построить, накапливая проценты и применяя платежи:9596```pycon97>>> 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]107```108109См. [`functools.reduce()`](https://python-all.ru/3.11/library/functools.html#functools.reduce) – похожая функция, возвращающая только итоговое накопленное значение.110111Новое в версии 3.2.112113Изменено в версии 3.3: Добавлен необязательный параметр *func*.114115Изменено в версии 3.8: Добавлен необязательный параметр *initial*.116117#### `itertools.chain(*iterables)`118119Создаёт итератор, который возвращает элементы из первого итерируемого объекта, пока он не будет исчерпан, затем переходит к следующему, пока все итерируемые объекты не будут исчерпаны. Используется для объединения последовательностей в одну. Приблизительный эквивалент:120121```python122def chain(*iterables):123 # chain('ABC', 'DEF') --> A B C D E F124 for it in iterables:125 for element in it:126 yield element127```128129#### `classmethod chain.from_iterable(iterable)`130131Альтернативный конструктор для [`chain()`](https://python-all.ru/3.11/library/itertools.html#itertools.chain). Получает цепочку входных данных из одного аргумента iterable, который вычисляется лениво. Примерная реализация:132133```python134def from_iterable(iterables):135 # chain.from_iterable(['ABC', 'DEF']) --> A B C D E F136 for it in iterables:137 for element in it:138 yield element139```140141#### `itertools.combinations(iterable, r)`142143Возвращает подпоследовательности элементов длины *r* из входного *iterable*.144145Кортежи комбинаций выдаются в лексикографическом порядке в соответствии с порядком входного *iterable*. Таким образом, если входной *iterable* отсортирован, выходные кортежи будут создаваться в отсортированном порядке.146147Элементы считаются уникальными по их позиции, а не по значению. Поэтому если входные элементы уникальны, в каждой комбинации не будет повторяющихся значений.148149Примерно эквивалентно:150151```python152def combinations(iterable, r):153 # combinations('ABCD', 2) --> AB AC AD BC BD CD154 # combinations(range(4), 3) --> 012 013 023 123155 pool = tuple(iterable)156 n = len(pool)157 if r > n:158 return159 indices = list(range(r))160 yield tuple(pool[i] for i in indices)161 while True:162 for i in reversed(range(r)):163 if indices[i] != i + n - r:164 break165 else:166 return167 indices[i] += 1168 for j in range(i+1, r):169 indices[j] = indices[j-1] + 1170 yield tuple(pool[i] for i in indices)171```172173Код для [`combinations()`](https://python-all.ru/3.11/library/itertools.html#itertools.combinations) можно также выразить как подпоследовательность [`permutations()`](https://python-all.ru/3.11/library/itertools.html#itertools.permutations) после фильтрации записей, где элементы не находятся в отсортированном порядке (согласно их позиции во входном пуле):174175```python176def combinations(iterable, r):177 pool = tuple(iterable)178 n = len(pool)179 for indices in permutations(range(n), r):180 if sorted(indices) == list(indices):181 yield tuple(pool[i] for i in indices)182```183184Количество возвращаемых элементов равно `n! / r! / (n-r)!`, когда `0 <= r <= n`, или нулю, когда `r > n`.185186#### `itertools.combinations_with_replacement(iterable, r)`187188Возвращает подпоследовательности элементов длины *r* из входного *iterable*, допуская повторение отдельных элементов.189190Кортежи комбинаций выдаются в лексикографическом порядке в соответствии с порядком входного *iterable*. Таким образом, если входной *iterable* отсортирован, выходные кортежи будут создаваться в отсортированном порядке.191192Элементы считаются уникальными по их позиции, а не по значению. Поэтому если входные элементы уникальны, сгенерированные комбинации также будут уникальны.193194Примерно эквивалентно:195196```python197def combinations_with_replacement(iterable, r):198 # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC199 pool = tuple(iterable)200 n = len(pool)201 if not n and r:202 return203 indices = [0] * r204 yield tuple(pool[i] for i in indices)205 while True:206 for i in reversed(range(r)):207 if indices[i] != n - 1:208 break209 else:210 return211 indices[i:] = [indices[i] + 1] * (r - i)212 yield tuple(pool[i] for i in indices)213```214215Код для [`combinations_with_replacement()`](https://python-all.ru/3.11/library/itertools.html#itertools.combinations_with_replacement) можно также выразить как подпоследовательность [`product()`](https://python-all.ru/3.11/library/itertools.html#itertools.product) после фильтрации записей, где элементы не находятся в отсортированном порядке (согласно их позиции во входном пуле):216217```python218def combinations_with_replacement(iterable, r):219 pool = tuple(iterable)220 n = len(pool)221 for indices in product(range(n), repeat=r):222 if sorted(indices) == list(indices):223 yield tuple(pool[i] for i in indices)224```225226Количество возвращаемых элементов равно `(n+r-1)! / r! / (n-1)!`, когда `n > 0`.227228Новое в версии 3.1.229230#### `itertools.compress(data, selectors)`231232Создаёт итератор, который фильтрует элементы из *data*, возвращая только те, для которых в *selectors* есть соответствующий элемент, вычисляемый как `True`. Останавливается, когда исчерпан либо итерабельный объект *data*, либо *selectors*. Примерно эквивалентен:233234```python235def compress(data, selectors):236 # compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F237 return (d for d, s in zip(data, selectors) if s)238```239240Новое в версии 3.1.241242#### `itertools.count(start=0, step=1)`243244Создаёт итератор, возвращающий равномерно распределённые значения, начиная с числа *start*. Часто используется как аргумент для [`map()`](https://python-all.ru/3.11/library/functions.html#map) для генерации последовательных точек данных. Также используется с [`zip()`](https://python-all.ru/3.11/library/functions.html#zip) для добавления порядковых номеров. Примерно эквивалентен:245246```python247def count(start=0, step=1):248 # count(10) --> 10 11 12 13 14 ...249 # count(2.5, 0.5) --> 2.5 3.0 3.5 ...250 n = start251 while True:252 yield n253 n += step254```255256При подсчёте с числами с плавающей запятой иногда можно добиться лучшей точности, заменив код на мультипликативный, например: `(start + step * i for i in count())`.257258Изменено в версии 3.1: Добавлен аргумент *step* и разрешены нецелые аргументы.259260#### `itertools.cycle(iterable)`261262Создаёт итератор, возвращающий элементы из итерабельного объекта и сохраняющий копию каждого. Когда итерабельный объект исчерпан, возвращает элементы из сохранённой копии. Повторяется бесконечно. Примерно эквивалентен:263264```python265def cycle(iterable):266 # cycle('ABCD') --> A B C D A B C D A B C D ...267 saved = []268 for element in iterable:269 yield element270 saved.append(element)271 while saved:272 for element in saved:273 yield element274```275276Примечание: этот элемент набора инструментов может потребовать значительного дополнительного хранилища (в зависимости от длины итерабельного объекта).277278#### `itertools.dropwhile(predicate, iterable)`279280Создаёт итератор, который отбрасывает элементы из итерабельного объекта, пока предикат истинен; после этого возвращает каждый элемент. Примечание: итератор не выдаёт *никакого* вывода, пока предикат впервые не станет ложным, поэтому время запуска может быть большим. Примерно эквивалентен:281282```python283def dropwhile(predicate, iterable):284 # dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1285 iterable = iter(iterable)286 for x in iterable:287 if not predicate(x):288 yield x289 break290 for x in iterable:291 yield x292```293294#### `itertools.filterfalse(predicate, iterable)`295296Создаёт итератор, который фильтрует элементы из итерабельного объекта, возвращая только те, для которых предикат ложен. Если *predicate* равен `None`, возвращает элементы, которые являются ложными. Примерно эквивалентен:297298```python299def filterfalse(predicate, iterable):300 # filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8301 if predicate is None:302 predicate = bool303 for x in iterable:304 if not predicate(x):305 yield x306```307308#### `itertools.groupby(iterable, key=None)`309310Make 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.311312Работа [`groupby()`](https://python-all.ru/3.11/library/itertools.html#itertools.groupby) аналогична фильтру `uniq` в Unix. Она создает разрыв или новую группу каждый раз, когда изменяется значение ключевой функции (поэтому обычно необходимо отсортировать данные с помощью той же ключевой функции). Такое поведение отличается от SQL GROUP BY, которая объединяет общие элементы независимо от порядка их ввода.313314Возвращаемая группа сама является итератором, который использует общий исходный итерируемый объект с [`groupby()`](https://python-all.ru/3.11/library/itertools.html#itertools.groupby). Поскольку источник общий, при продвижении объекта [`groupby()`](https://python-all.ru/3.11/library/itertools.html#itertools.groupby) предыдущая группа перестает быть видимой. Поэтому, если эти данные понадобятся позже, их следует сохранить в виде списка:315316```python317groups = []318uniquekeys = []319data = sorted(data, key=keyfunc)320for k, g in groupby(data, keyfunc):321 groups.append(list(g)) # Сохранить групповой итератор как список322 uniquekeys.append(k)323```324325[`groupby()`](https://python-all.ru/3.11/library/itertools.html#itertools.groupby) примерно эквивалентно:326327```python328class groupby:329 # [k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B330 # [list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D331332 def __init__(self, iterable, key=None):333 if key is None:334 key = lambda x: x335 self.keyfunc = key336 self.it = iter(iterable)337 self.tgtkey = self.currkey = self.currvalue = object()338339 def __iter__(self):340 return self341342 def __next__(self):343 self.id = object()344 while self.currkey == self.tgtkey:345 self.currvalue = next(self.it) # Выход при StopIteration346 self.currkey = self.keyfunc(self.currvalue)347 self.tgtkey = self.currkey348 return (self.currkey, self._grouper(self.tgtkey, self.id))349350 def _grouper(self, tgtkey, id):351 while self.id is id and self.currkey == tgtkey:352 yield self.currvalue353 try:354 self.currvalue = next(self.it)355 except StopIteration:356 return357 self.currkey = self.keyfunc(self.currvalue)358```359360#### `itertools.islice(iterable, stop)`361362#### `itertools.islice(iterable, start, stop[, step])`363364Создаёт итератор, возвращающий выбранные элементы из итерируемого объекта. Если *start* не равен нулю, то элементы из итерируемого объекта пропускаются до достижения start. Затем элементы возвращаются последовательно, если только *step* не установлен больше единицы, что приводит к пропуску элементов. Если *stop* равен `None`, то итерация продолжается, пока итератор не будет исчерпан (если это вообще произойдёт); в противном случае она останавливается на указанной позиции.365366Если *start* равен `None`, то итерация начинается с нуля. Если *step* равен `None`, то шаг по умолчанию равен единице.367368В отличие от обычной срезки, [`islice()`](https://python-all.ru/3.11/library/itertools.html#itertools.islice) не поддерживает отрицательные значения для *start*, *stop* или *step*. Может использоваться для извлечения связанных полей из данных, у которых внутренняя структура была уплощена (например, многострочный отчёт может выводить поле имени на каждой третьей строке).369370Примерно эквивалентно:371372```python373def islice(iterable, *args):374 # islice('ABCDEFG', 2) --> A B375 # islice('ABCDEFG', 2, 4) --> C D376 # islice('ABCDEFG', 2, None) --> C D E F G377 # islice('ABCDEFG', 0, None, 2) --> A C E G378 s = slice(*args)379 start, stop, step = s.start or 0, s.stop or sys.maxsize, s.step or 1380 it = iter(range(start, stop, step))381 try:382 nexti = next(it)383 except StopIteration:384 # Потребляет *iterable* до позиции *start*.385 for i, element in zip(range(start), iterable):386 pass387 return388 try:389 for i, element in enumerate(iterable):390 if i == nexti:391 yield element392 nexti = next(it)393 except StopIteration:394 # Потребляет до *stop*.395 for i, element in zip(range(i + 1, stop), iterable):396 pass397```398399#### `itertools.pairwise(iterable)`400401Возвращает последовательные перекрывающиеся пары, взятые из входного *iterable*.402403Количество кортежей из двух элементов в выходном итераторе будет на один меньше, чем количество входных элементов. Он будет пустым, если входной итерируемый объект содержит менее двух значений.404405Примерно эквивалентно:406407```python408def pairwise(iterable):409 # pairwise('ABCDEFG') --> AB BC CD DE EF FG410 a, b = tee(iterable)411 next(b, None)412 return zip(a, b)413```414415Новое в версии 3.10.416417#### `itertools.permutations(iterable, r=None)`418419Возвращает последовательные перестановки длины *r* элементов из *iterable*.420421Если *r* не указан или равен `None`, то *r* по умолчанию равен длине *iterable* и генерируются все возможные перестановки полной длины.422423Кортежи перестановок выдаются в лексикографическом порядке в соответствии с порядком входного *iterable*. То есть если входной *iterable* отсортирован, выходные кортежи будут созданы в отсортированном порядке.424425Элементы считаются уникальными на основе их позиции, а не значения. Поэтому если входные элементы уникальны, то в перестановке не будет повторяющихся значений.426427Примерно эквивалентно:428429```python430def permutations(iterable, r=None):431 # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC432 # permutations(range(3)) --> 012 021 102 120 201 210433 pool = tuple(iterable)434 n = len(pool)435 r = n if r is None else r436 if r > n:437 return438 indices = list(range(n))439 cycles = list(range(n, n-r, -1))440 yield tuple(pool[i] for i in indices[:r])441 while n:442 for i in reversed(range(r)):443 cycles[i] -= 1444 if cycles[i] == 0:445 indices[i:] = indices[i+1:] + indices[i:i+1]446 cycles[i] = n - i447 else:448 j = cycles[i]449 indices[i], indices[-j] = indices[-j], indices[i]450 yield tuple(pool[i] for i in indices[:r])451 break452 else:453 return454```455456Код для [`permutations()`](https://python-all.ru/3.11/library/itertools.html#itertools.permutations) также можно выразить как подпоследовательность [`product()`](https://python-all.ru/3.11/library/itertools.html#itertools.product), отфильтрованную для исключения записей с повторяющимися элементами (тех, которые находятся на одной и той же позиции во входном пуле):457458```python459def permutations(iterable, r=None):460 pool = tuple(iterable)461 n = len(pool)462 r = n if r is None else r463 for indices in product(range(n), repeat=r):464 if len(set(indices)) == r:465 yield tuple(pool[i] for i in indices)466```467468Количество возвращаемых элементов равно `n! / (n-r)!`, когда `0 <= r <= n`, или нулю, когда `r > n`.469470#### `itertools.product(*iterables, repeat=1)`471472Декартово произведение входных итерируемых объектов.473474Примерно эквивалентно вложенным циклам for в генераторном выражении. Например, `product(A, B)` возвращает то же, что и `((x,y) for x in A for y in B)`.475476Вложенные циклы работают как одометр: самый правый элемент увеличивается на каждой итерации. Этот шаблон создает лексикографический порядок, так что если входные итерируемые объекты отсортированы, кортежи произведения выдаются в отсортированном порядке.477478Чтобы вычислить произведение итерируемого объекта на самого себя, укажите количество повторений с помощью необязательного именованного аргумента *repeat*. Например, `product(A, repeat=4)` эквивалентно `product(A, A, A, A)`.479480Эта функция примерно эквивалентна следующему коду, за исключением того, что реальная реализация не накапливает промежуточные результаты в памяти:481482```python483def product(*args, repeat=1):484 # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy485 # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111486 pools = [tuple(pool) for pool in args] * repeat487 result = [[]]488 for pool in pools:489 result = [x+[y] for x in result for y in pool]490 for prod in result:491 yield tuple(prod)492```493494Перед запуском [`product()`](https://python-all.ru/3.11/library/itertools.html#itertools.product) полностью потребляет входные итерируемые объекты, сохраняя пулы значений в памяти для генерации произведений. Соответственно, она полезна только для конечных входных данных.495496#### `itertools.repeat(object[, times])`497498Создает итератор, который снова и снова возвращает *object*. Работает бесконечно, если не указан аргумент *times*.499500Примерно эквивалентно:501502```python503def repeat(object, times=None):504 # repeat(10, 3) --> 10 10 10505 if times is None:506 while True:507 yield object508 else:509 for i in range(times):510 yield object511```512513Обычное применение *repeat* – передача потока постоянных значений в *map* или *zip*:514515```pycon516>>> list(map(pow, range(10), repeat(2)))517[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]518```519520#### `itertools.starmap(function, iterable)`521522Создаёт итератор, который вычисляет функцию, используя аргументы, полученные из итерируемого объекта. Используется вместо [`map()`](https://python-all.ru/3.11/library/functions.html#map), когда аргументы уже сгруппированы в кортежи из одного итерируемого объекта (когда данные были «предварительно упакованы»).523524Различие между [`map()`](https://python-all.ru/3.11/library/functions.html#map) и [`starmap()`](https://python-all.ru/3.11/library/itertools.html#itertools.starmap) аналогично различию между `function(a,b)` и `function(*c)`. Примерно эквивалентно:525526```python527def starmap(function, iterable):528 # starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000529 for args in iterable:530 yield function(*args)531```532533#### `itertools.takewhile(predicate, iterable)`534535Создаёт итератор, возвращающий элементы из итерируемого объекта, пока предикат истинен. Приблизительно эквивалентно:536537```python538def takewhile(predicate, iterable):539 # takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4540 for x in iterable:541 if predicate(x):542 yield x543 else:544 break545```546547#### `itertools.tee(iterable, n=2)`548549Возвращает *n* независимых итераторов из одного итерируемого объекта.550551Следующий код на Python помогает объяснить, что делает *tee* (хотя реальная реализация сложнее и использует только одну базовую очередь FIFO):552553```python554def tee(iterable, n=2):555 it = iter(iterable)556 deques = [collections.deque() for i in range(n)]557 def gen(mydeque):558 while True:559 if not mydeque: # когда локальная deque пуста560 try:561 newval = next(it) # извлечь новое значение и562 except StopIteration:563 return564 for d in deques: # загрузить его во все двусторонние очереди565 d.append(newval)566 yield mydeque.popleft()567 return tuple(gen(d) for d in deques)568```569570После того как [`tee()`](https://python-all.ru/3.11/library/itertools.html#itertools.tee) создан, исходный *iterable* не следует использовать где-либо ещё; в противном случае *iterable* может продвинуться без уведомления объектов tee.571572Итераторы `tee` не являются потокобезопасными. [`RuntimeError`](https://python-all.ru/3.11/library/exceptions.html#RuntimeError) может быть возбуждён при одновременном использовании итераторов, возвращённых одним и тем же вызовом [`tee()`](https://python-all.ru/3.11/library/itertools.html#itertools.tee), даже если исходный *iterable* является потокобезопасным.573574Этот инструмент итерации может потребовать значительного вспомогательного хранилища (в зависимости от объёма временных данных, которые необходимо сохранить). В общем случае, если один итератор использует большую часть или все данные до того, как запустится другой итератор, быстрее использовать [`list()`](https://python-all.ru/3.11/library/stdtypes.html#list) вместо [`tee()`](https://python-all.ru/3.11/library/itertools.html#itertools.tee).575576#### `itertools.zip_longest(*iterables, fillvalue=None)`577578Создаёт итератор, который агрегирует элементы из каждого из итерируемых объектов. Если итерируемые объекты имеют разную длину, недостающие значения заполняются с помощью *fillvalue*. Итерация продолжается до тех пор, пока самый длинный итерируемый объект не будет исчерпан. Приблизительно эквивалентно:579580```python581def zip_longest(*args, fillvalue=None):582 # zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-583 iterators = [iter(it) for it in args]584 num_active = len(iterators)585 if not num_active:586 return587 while True:588 values = []589 for i, it in enumerate(iterators):590 try:591 value = next(it)592 except StopIteration:593 num_active -= 1594 if not num_active:595 return596 iterators[i] = repeat(fillvalue)597 value = fillvalue598 values.append(value)599 yield tuple(values)600```601602Если один из итерируемых объектов потенциально бесконечен, то функцию [`zip_longest()`](https://python-all.ru/3.11/library/itertools.html#itertools.zip_longest) следует обернуть чем-то, что ограничивает количество вызовов (например, [`islice()`](https://python-all.ru/3.11/library/itertools.html#itertools.islice) или [`takewhile()`](https://python-all.ru/3.11/library/itertools.html#itertools.takewhile)). Если не указано, *fillvalue* по умолчанию равен `None`.603604## Рецепты itertools605606В этом разделе представлены рецепты для создания расширенного набора инструментов с использованием существующих itertools в качестве строительных блоков.607608Основная цель рецептов itertools – образовательная. Рецепты демонстрируют различные способы мышления об отдельных инструментах – например, что `chain.from_iterable` связано с концепцией уплощения. Рецепты также дают идеи о том, как инструменты можно комбинировать – например, как `compress()` и `range()` могут работать вместе. Рецепты также показывают шаблоны использования itertools с модулями [`operator`](https://python-all.ru/3.11/library/operator.html#module-operator) и [`collections`](https://python-all.ru/3.11/library/collections.html#module-collections), а также со встроенными itertools, такими как `map()`, `filter()`, `reversed()` и `enumerate()`.609610Второстепенная цель рецептов – служить инкубатором. `accumulate()`, `compress()` и `pairwise()` itertools изначально были рецептами. В настоящее время рецепт `iter_index()` тестируется, чтобы проверить, оправдает ли он себя.611612Практически все эти рецепты и многие-многие другие можно установить из проекта [more-itertools](https://python-all.ru/3.11/library/itertools.html), который находится в Python Package Index:613614```python615python -m pip install more-itertools616```617618Многие рецепты обеспечивают такую же высокую производительность, как и базовый набор инструментов. Превосходная производительность по памяти достигается за счёт обработки элементов по одному, а не загрузки всего итерируемого объекта в память сразу. Объём кода остаётся небольшим благодаря связыванию инструментов в функциональном стиле, что помогает исключить временные переменные. Высокая скорость сохраняется за счёт предпочтения «векторизованных» строительных блоков вместо использования циклов for и [генераторов](https://python-all.ru/3.11/glossary.html#term-generator), которые создают накладные расходы интерпретатора.619620```python621import collections622import math623import operator624import random625626def take(n, iterable):627 "Return first n items of the iterable as a list"628 return list(islice(iterable, n))629630def prepend(value, iterable):631 "Prepend a single value in front of an iterable"632 # prepend(1, [2, 3, 4]) --> 1 2 3 4633 return chain([value], iterable)634635def tabulate(function, start=0):636 "Return function(0), function(1), ..."637 return map(function, count(start))638639def tail(n, iterable):640 "Return an iterator over the last n items"641 # tail(3, 'ABCDEFG') --> E F G642 return iter(collections.deque(iterable, maxlen=n))643644def consume(iterator, n=None):645 "Advance the iterator n-steps ahead. If n is None, consume entirely."646 # Используйте функции, потребляющие итераторы на скорости C.647 if n is None:648 # передать весь итератор в deque нулевой длины649 collections.deque(iterator, maxlen=0)650 else:651 # перейти к пустому срезу начиная с позиции n652 next(islice(iterator, n, n), None)653654def nth(iterable, n, default=None):655 "Returns the nth item or a default value"656 return next(islice(iterable, n, None), default)657658def all_equal(iterable):659 "Returns True if all the elements are equal to each other"660 g = groupby(iterable)661 return next(g, True) and not next(g, False)662663def quantify(iterable, pred=bool):664 "Count how many times the predicate is True"665 return sum(map(pred, iterable))666667def ncycles(iterable, n):668 "Returns the sequence elements n times"669 return chain.from_iterable(repeat(tuple(iterable), n))670671def batched(iterable, n):672 "Batch data into tuples of length n. The last batch may be shorter."673 # batched('ABCDEFG', 3) --> ABC DEF G674 if n < 1:675 raise ValueError('n must be at least one')676 it = iter(iterable)677 while batch := tuple(islice(it, n)):678 yield batch679680def grouper(iterable, n, *, incomplete='fill', fillvalue=None):681 "Collect data into non-overlapping fixed-length chunks or blocks"682 # grouper('ABCDEFG', 3, fillvalue='x') --> ABC DEF Gxx683 # grouper('ABCDEFG', 3, incomplete='strict') --> ABC DEF ValueError684 # grouper('ABCDEFG', 3, incomplete='ignore') --> ABC DEF685 args = [iter(iterable)] * n686 if incomplete == 'fill':687 return zip_longest(*args, fillvalue=fillvalue)688 if incomplete == 'strict':689 return zip(*args, strict=True)690 if incomplete == 'ignore':691 return zip(*args)692 else:693 raise ValueError('Expected fill, strict, or ignore')694695def sumprod(vec1, vec2):696 "Compute a sum of products."697 return sum(starmap(operator.mul, zip(vec1, vec2, strict=True)))698699def sum_of_squares(it):700 "Add up the squares of the input values."701 # sum_of_squares([10, 20, 30]) -> 1400702 return sumprod(*tee(it))703704def transpose(it):705 "Swap the rows and columns of the input."706 # transpose([(1, 2, 3), (11, 22, 33)]) --> (1, 11) (2, 22) (3, 33)707 return zip(*it, strict=True)708709def matmul(m1, m2):710 "Multiply two matrices."711 # matmul([(7, 5), (3, 5)], [[2, 5], [7, 9]]) --> (49, 80), (41, 60)712 n = len(m2[0])713 return batched(starmap(sumprod, product(m1, transpose(m2))), n)714715def convolve(signal, kernel):716 # См.: https://betterexplained.com/articles/intuitive-convolution/717 # convolve(data, [0.25, 0.25, 0.25, 0.25]) --> Скользящее среднее (размытие)718 # convolve(data, [1, -1]) --> Первая конечная разность (первая производная)719 # convolve(data, [1, -2, 1]) --> Вторая конечная разность (вторая производная)720 kernel = tuple(kernel)[::-1]721 n = len(kernel)722 window = collections.deque([0], maxlen=n) * n723 for x in chain(signal, repeat(0, n-1)):724 window.append(x)725 yield sumprod(kernel, window)726727def polynomial_from_roots(roots):728 """Вычисляет коэффициенты многочлена по его корням.729730 (x - 5) (x + 4) (x - 3) раскрывается в: x³ -4x² -17x + 60731 """732 # polynomial_from_roots([5, -4, 3]) --> [1, -4, -17, 60]733 expansion = [1]734 for r in roots:735 expansion = convolve(expansion, (1, -r))736 return list(expansion)737738def polynomial_eval(coefficients, x):739 """Вычисляет значение многочлена в заданной точке.740741 Вычисляет с лучшей численной устойчивостью, чем метод Горнера.742 """743 # Вычислить x³ -4x² -17x + 60 при x = 2.5744 # polynomial_eval([1, -4, -17, 60], x=2.5) --> 8.125745 n = len(coefficients)746 if n == 0:747 return x * 0 # Привести ноль к типу x748 powers = map(pow, repeat(x), reversed(range(n)))749 return sumprod(coefficients, powers)750751def iter_index(iterable, value, start=0):752 "Return indices where a value occurs in a sequence or iterable."753 # iter_index('AABCADEAF', 'A') --> 0 1 4 7754 try:755 seq_index = iterable.index756 except AttributeError:757 # Медленный путь для общих итерируемых объектов758 it = islice(iterable, start, None)759 i = start - 1760 try:761 while True:762 yield (i := i + operator.indexOf(it, value) + 1)763 except ValueError:764 pass765 else:766 # Быстрый путь для последовательностей767 i = start - 1768 try:769 while True:770 yield (i := seq_index(value, i+1))771 except ValueError:772 pass773774def sieve(n):775 "Primes less than n"776 # sieve(30) --> 2 3 5 7 11 13 17 19 23 29777 data = bytearray((0, 1)) * (n // 2)778 data[:3] = 0, 0, 0779 limit = math.isqrt(n) + 1780 for p in compress(range(limit), data):781 data[p*p : n : p+p] = bytes(len(range(p*p, n, p+p)))782 data[2] = 1783 return iter_index(data, 1) if n > 2 else iter([])784785def factor(n):786 "Prime factors of n."787 # factor(99) --> 3 3 11788 for prime in sieve(math.isqrt(n) + 1):789 while True:790 quotient, remainder = divmod(n, prime)791 if remainder:792 break793 yield prime794 n = quotient795 if n == 1:796 return797 if n > 1:798 yield n799800def flatten(list_of_lists):801 "Flatten one level of nesting"802 return chain.from_iterable(list_of_lists)803804def repeatfunc(func, times=None, *args):805 """Повторяет вызовы func с указанными аргументами.806807 Пример: repeatfunc(random.random)808 """809 if times is None:810 return starmap(func, repeat(args))811 return starmap(func, repeat(args, times))812813def triplewise(iterable):814 "Return overlapping triplets from an iterable"815 # triplewise('ABCDEFG') --> ABC BCD CDE DEF EFG816 for (a, _), (b, c) in pairwise(pairwise(iterable)):817 yield a, b, c818819def sliding_window(iterable, n):820 # sliding_window('ABCDEFG', 4) --> ABCD BCDE CDEF DEFG821 it = iter(iterable)822 window = collections.deque(islice(it, n), maxlen=n)823 if len(window) == n:824 yield tuple(window)825 for x in it:826 window.append(x)827 yield tuple(window)828829def roundrobin(*iterables):830 "roundrobin('ABC', 'D', 'EF') --> A D E B F C"831 # Автор рецепта – Джордж Саккис832 num_active = len(iterables)833 nexts = cycle(iter(it).__next__ for it in iterables)834 while num_active:835 try:836 for next in nexts:837 yield next()838 except StopIteration:839 # Удалить из цикла только что исчерпанный итератор.840 num_active -= 1841 nexts = cycle(islice(nexts, num_active))842843def partition(pred, iterable):844 "Use a predicate to partition entries into false entries and true entries"845 # partition(is_odd, range(10)) --> 0 2 4 6 8 and 1 3 5 7 9846 t1, t2 = tee(iterable)847 return filterfalse(pred, t1), filter(pred, t2)848849def before_and_after(predicate, it):850 """ Вариант takewhile(), который позволяет полностью851 доступ к остатку итератора.852853 >>> it = iter('ABCdEfGhI')854 >>> all_upper, remainder = before_and_after(str.isupper, it)855 >>> ''.join(all_upper)856 'ABC'857 >>> ''.join(remainder) # takewhile() потерял бы 'd'858 'dEfGhI'859860 Обратите внимание, что первый итератор должен быть полностью861 использован до того, как второй итератор сможет862 сгенерировать корректные результаты.863 """864 it = iter(it)865 transition = []866 def true_iterator():867 for elem in it:868 if predicate(elem):869 yield elem870 else:871 transition.append(elem)872 return873 def remainder_iterator():874 yield from transition875 yield from it876 return true_iterator(), remainder_iterator()877878def subslices(seq):879 "Return all contiguous non-empty subslices of a sequence"880 # subslices('ABCD') --> A AB ABC ABCD B BC BCD C CD D881 slices = starmap(slice, combinations(range(len(seq) + 1), 2))882 return map(operator.getitem, repeat(seq), slices)883884def powerset(iterable):885 "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"886 s = list(iterable)887 return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))888889def unique_everseen(iterable, key=None):890 "List unique elements, preserving order. Remember all elements ever seen."891 # unique_everseen('AAAABBBCCDAABBB') --> A B C D892 # unique_everseen('ABBcCAD', str.lower) --> A B c D893 seen = set()894 if key is None:895 for element in filterfalse(seen.__contains__, iterable):896 seen.add(element)897 yield element898 # Для дедупликации с сохранением порядка,899 # более быстрое, но не ленивое решение:900 # yield from dict.fromkeys(iterable)901 else:902 for element in iterable:903 k = key(element)904 if k not in seen:905 seen.add(k)906 yield element907 # Для случаев, когда можно вернуть последний совпадающий элемент,908 # более быстрое, но не ленивое решение:909 # t1, t2 = tee(iterable)910 # yield from dict(zip(map(key, t1), t2)).values()911912def unique_justseen(iterable, key=None):913 "List unique elements, preserving order. Remember only the element just seen."914 # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B915 # unique_justseen('ABBcCAD', str.lower) --> A B c A D916 return map(next, map(operator.itemgetter(1), groupby(iterable, key)))917918def iter_except(func, exception, first=None):919 """ Повторно вызывает функцию до возникновения исключения.920921 Преобразует интерфейс вызова до исключения в интерфейс итератора.922 Как builtins.iter(func, sentinel), но использует исключение вместо923 сигнального значения для завершения цикла.924925 Примеры:926 iter_except(functools.partial(heappop, h), IndexError) # итератор очереди с приоритетом927 iter_except(d.popitem, KeyError) # итератор словаря без блокировки928 iter_except(d.popleft, IndexError) # итератор дека без блокировки929 iter_except(q.get_nowait, Queue.Empty) # цикл по очереди производителя930 iter_except(s.pop, KeyError) # итератор множества без блокировки931932 """933 try:934 if first is not None:935 yield first() # Для API баз данных, требующих первоначального приведения к db.first()936 while True:937 yield func()938 except exception:939 pass940941def first_true(iterable, default=False, pred=None):942 """Возвращает первое истинное значение в итерируемом объекте.943944 Если истинное значение не найдено, возвращает *default*945946 Если *pred* не равен None, возвращает первый элемент947 для которого pred(item) истинно.948949 """950 # first_true([a,b,c], x) --> a or b or c or x951 # first_true([a,b], x, f) --> a if f(a) else b if f(b) else x952 return next(filter(pred, iterable), default)953954def nth_combination(iterable, r, index):955 "Equivalent to list(combinations(iterable, r))[index]"956 pool = tuple(iterable)957 n = len(pool)958 c = math.comb(n, r)959 if index < 0:960 index += c961 if index < 0 or index >= c:962 raise IndexError963 result = []964 while r:965 c, n, r = c*r//n, n-1, r-1966 while index >= c:967 index -= c968 c, n = c*(n-r)//n, n-1969 result.append(pool[-1-n])970 return tuple(result)971```972