itertools.md
1> **Источник:** https://python-all.ru/3.16/library/itertools.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# `itertools` – Функции, создающие итераторы для эффективного перебора89---1011Этот модуль реализует ряд строительных блоков [итераторов](https://python-all.ru/3.16/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.16/library/functions.html#map) и [`count()`](https://python-all.ru/3.16/library/itertools.html#itertools.count) для получения `map(f, count())`.1617**Основные итераторы:**1819| Итератор | Аргументы | Результаты | Пример |20| --- | --- | --- | --- |21| [`accumulate()`](https://python-all.ru/3.16/library/itertools.html#itertools.accumulate) | p \[,func\] | p0, p0+p1, p0+p1+p2, … | `accumulate([1,2,3,4,5]) → 1 3 6 10 15` |22| [`batched()`](https://python-all.ru/3.16/library/itertools.html#itertools.batched) | p, n | (p0, p1, …, p\_n-1), … | `batched('ABCDEFG', n=3) → ABC DEF G` |23| [`chain()`](https://python-all.ru/3.16/library/itertools.html#itertools.chain) | p, q, … | p0, p1, … plast, q0, q1, … | `chain('ABC', 'DEF') → A B C D E F` |24| [`chain.from_iterable()`](https://python-all.ru/3.16/library/itertools.html#itertools.chain.from_iterable) | iterable | p0, p1, … plast, q0, q1, … | `chain.from_iterable(['ABC', 'DEF']) → A B C D E F` |25| [`compress()`](https://python-all.ru/3.16/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` |26| [`count()`](https://python-all.ru/3.16/library/itertools.html#itertools.count) | \[start\[, step\]\] | start, start+step, start+2\*step, … | `count(10) → 10 11 12 13 14 ...` |27| [`cycle()`](https://python-all.ru/3.16/library/itertools.html#itertools.cycle) | p | p0, p1, … plast, p0, p1, … | `cycle('ABCD') → A B C D A B C D ...` |28| [`dropwhile()`](https://python-all.ru/3.16/library/itertools.html#itertools.dropwhile) | predicate, seq | seq\[n\], seq\[n+1\], начиная с момента, когда предикат не выполняется | `dropwhile(lambda x: x<5, [1,4,6,3,8]) → 6 3 8` |29| [`filterfalse()`](https://python-all.ru/3.16/library/itertools.html#itertools.filterfalse) | predicate, seq | элементы seq, для которых predicate(elem) не выполняется | `filterfalse(lambda x: x<5, [1,4,6,3,8]) → 6 8` |30| [`groupby()`](https://python-all.ru/3.16/library/itertools.html#itertools.groupby) | iterable\[, key\] | подитераторы, сгруппированные по значению key(v) | `groupby(['A','B','DEF'], len) → (1, A B) (3, DEF)` |31| [`islice()`](https://python-all.ru/3.16/library/itertools.html#itertools.islice) | seq, \[start,\] stop \[, step\] | элементы из seq\[start:stop:step\] | `islice('ABCDEFG', 2, None) → C D E F G` |32| [`pairwise()`](https://python-all.ru/3.16/library/itertools.html#itertools.pairwise) | iterable | (p\[0\], p\[1\]), (p\[1\], p\[2\]) | `pairwise('ABCDEFG') → AB BC CD DE EF FG` |33| [`repeat()`](https://python-all.ru/3.16/library/itertools.html#itertools.repeat) | elem \[,n\] | elem, elem, elem, … бесконечно или до n раз | `repeat(10, 3) → 10 10 10` |34| [`starmap()`](https://python-all.ru/3.16/library/itertools.html#itertools.starmap) | func, seq | func(\*seq\[0\]), func(\*seq\[1\]), … | `starmap(pow, [(2,5), (3,2), (10,3)]) → 32 9 1000` |35| [`takewhile()`](https://python-all.ru/3.16/library/itertools.html#itertools.takewhile) | predicate, seq | seq\[0\], seq\[1\], пока predicate не вернёт ложь | `takewhile(lambda x: x<5, [1,4,6,3,8]) → 1 4` |36| [`tee()`](https://python-all.ru/3.16/library/itertools.html#itertools.tee) | it, n | it1, it2, … itn разделяет один итератор на n | `tee('ABC', 2) → A B C, A B C` |37| [`zip_longest()`](https://python-all.ru/3.16/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-` |3839**Комбинаторные итераторы:**4041| Итератор | Аргументы | Результаты |42| --- | --- | --- |43| [`product()`](https://python-all.ru/3.16/library/itertools.html#itertools.product) | p, q, … \[repeat=1\] | декартово произведение, эквивалентно вложенному циклу for |44| [`permutations()`](https://python-all.ru/3.16/library/itertools.html#itertools.permutations) | p\[, r\] | кортежи длиной r, все возможные перестановки, без повторяющихся элементов |45| [`combinations()`](https://python-all.ru/3.16/library/itertools.html#itertools.combinations) | p, r | кортежи длиной r, в отсортированном порядке, без повторяющихся элементов |46| [`combinations_with_replacement()`](https://python-all.ru/3.16/library/itertools.html#itertools.combinations_with_replacement) | p, r | кортежи длиной r, в отсортированном порядке, с повторяющимися элементами |4748| Примеры | Результаты |49| --- | --- |50| `product('ABCD', repeat=2)` | `AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD` |51| `permutations('ABCD', 2)` | `AB AC AD BA BC BD CA CB CD DA DB DC` |52| `combinations('ABCD', 2)` | `AB AC AD BC BD CD` |53| `combinations_with_replacement('ABCD', 2)` | `AA AB AC AD BB BC BD CC CD DD` |5455## Функции itertools5657Следующие функции создают и возвращают итераторы. Некоторые из них дают потоки бесконечной длины, поэтому их следует использовать только в функциях или циклах, которые обрезают поток.5859#### `itertools.accumulate(iterable[, function, *, initial=None])`6061Создаёт итератор, возвращающий накопленные суммы или накопленные результаты других бинарных функций.6263Если *function* не указана, по умолчанию используется сложение. *Function* должна принимать два аргумента: накопленное значение и очередной элемент из *iterable*.6465Если указано начальное значение *initial*, накопление начнётся с него, и в результате будет на один элемент больше, чем во входном итерируемом объекте.6667Примерно эквивалентно:6869```python70def accumulate(iterable, function=operator.add, *, initial=None):71 'Return running totals'72 # accumulate([1,2,3,4,5]) → 1 3 6 10 1573 # accumulate([1,2,3,4,5], initial=100) → 100 101 103 106 110 11574 # accumulate([1,2,3,4,5], operator.mul) → 1 2 6 24 1207576 iterator = iter(iterable)77 total = initial78 if initial is None:79 try:80 total = next(iterator)81 except StopIteration:82 return8384 yield total85 for element in iterator:86 total = function(total, element)87 yield total88```8990Чтобы вычислить текущий минимум, задайте *function* равной [`min()`](https://python-all.ru/3.16/library/functions.html#min). Для текущего максимума – *function* [`max()`](https://python-all.ru/3.16/library/functions.html#max). Для текущего произведения – *function* [`operator.mul()`](https://python-all.ru/3.16/library/operator.html#operator.mul). Для построения [таблицы амортизации](https://python-all.ru/3.16/library/itertools.html) накопите проценты и примените платежи:9192```pycon93>>> data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8]94>>> list(accumulate(data, max)) # текущий максимум95[3, 4, 6, 6, 6, 9, 9, 9, 9, 9]96>>> list(accumulate(data, operator.mul)) # текущее произведение97[3, 12, 72, 144, 144, 1296, 0, 0, 0, 0]9899# Amortize a 5% loan of 1000 with 10 annual payments of 90100>>> update = lambda balance, payment: round(balance * 1.05) - payment101>>> list(accumulate(repeat(90, 10), update, initial=1_000))102[1000, 960, 918, 874, 828, 779, 728, 674, 618, 559, 497]103```104105См. [`functools.reduce()`](https://python-all.ru/3.16/library/functools.html#functools.reduce) – похожая функция, возвращающая только итоговое накопленное значение.106107Добавлено в версии 3.2.108109Изменено в версии 3.3: Добавлен необязательный параметр *function*.110111Изменено в версии 3.8: Добавлен необязательный параметр *initial*.112113#### `itertools.batched(iterable, n, *, strict=False)`114115Группирует данные из *iterable* в кортежи длины *n*. Последняя группа может быть короче *n*.116117Если *strict* равен True, будет вызвано исключение [`ValueError`](https://python-all.ru/3.16/library/exceptions.html#ValueError), если последняя группа короче *n*.118119Перебирает входной iterable и накапливает данные в кортежи размером до *n*. Входные данные обрабатываются лениво – ровно столько, чтобы заполнить одну группу. Результат возвращается сразу, как только группа заполнена или входной iterable исчерпан:120121```pycon122>>> flattened_data = ['roses', 'red', 'violets', 'blue', 'sugar', 'sweet']123>>> unflattened = list(batched(flattened_data, 2))124>>> unflattened125[('roses', 'red'), ('violets', 'blue'), ('sugar', 'sweet')]126```127128Примерно эквивалентно:129130```python131def batched(iterable, n, *, strict=False):132 # batched('ABCDEFG', 3) → ABC DEF G133 if n < 1:134 raise ValueError('n must be at least one')135 iterator = iter(iterable)136 while batch := tuple(islice(iterator, n)):137 if strict and len(batch) != n:138 raise ValueError('batched(): incomplete batch')139 yield batch140```141142Добавлено в версии 3.12.143144Изменено в версии 3.13: Добавлен параметр *strict*.145146#### `itertools.chain(*iterables)`147148Создаёт итератор, который возвращает элементы из первого iterable, пока он не исчерпан, затем переходит к следующему, и так до исчерпания всех. Это объединяет несколько источников данных в один итератор. Примерная реализация:149150```python151def chain(*iterables):152 # chain('ABC', 'DEF') → A B C D E F153 for iterable in iterables:154 yield from iterable155```156157Обратите внимание, что [unpacking in comprehensions](https://python-all.ru/3.16/reference/expressions.html#unpacking-comprehensions) предоставляет аналогичную функциональность, поэтому `list(chain(p, q))` можно записать как `[*s for s in (p, q)]`.158159#### `classmethod chain.from_iterable(iterable)`160161Альтернативный конструктор для [`chain()`](https://python-all.ru/3.16/library/itertools.html#itertools.chain). Получает цепочку входных данных из одного аргумента iterable, который вычисляется лениво. Примерная реализация:162163```python164def from_iterable(iterables):165 # chain.from_iterable(['ABC', 'DEF']) → A B C D E F166 for iterable in iterables:167 yield from iterable168```169170Обратите внимание, что [unpacking in comprehensions](https://python-all.ru/3.16/reference/expressions.html#unpacking-comprehensions) предоставляет аналогичную функциональность, поэтому `list(chain.from_iterable(iterables))` можно записать как `[*s for s in iterables]`.171172#### `itertools.combinations(iterable, r)`173174Возвращает подпоследовательности элементов длины *r* из входного *iterable*.175176Результат является подмножеством [`product()`](https://python-all.ru/3.16/library/itertools.html#itertools.product), в котором оставлены только те элементы, которые являются подпоследовательностями *iterable*. Длина результата задаётся выражением [`math.comb()`](https://python-all.ru/3.16/library/math.html#math.comb), которое равно `n! / r! / (n - r)!`, если `0 ≤ r ≤ n`, или нулю, если `r > n`.177178Кортежи-комбинации порождаются в лексикографическом порядке по порядку входного *iterable*. Если входной *iterable* отсортирован, выходные кортежи также будут отсортированы.179180Элементы считаются уникальными по позиции, а не по значению. Если входные элементы уникальны, то в каждой комбинации не будет повторяющихся значений.181182Примерно эквивалентно:183184```python185def combinations(iterable, r):186 # combinations('ABCD', 2) → AB AC AD BC BD CD187 # combinations(range(4), 3) → 012 013 023 123188189 pool = tuple(iterable)190 n = len(pool)191 if r > n:192 return193 indices = list(range(r))194195 yield tuple(pool[i] for i in indices)196 while True:197 for i in reversed(range(r)):198 if indices[i] != i + n - r:199 break200 else:201 return202 indices[i] += 1203 for j in range(i+1, r):204 indices[j] = indices[j-1] + 1205 yield tuple(pool[i] for i in indices)206```207208#### `itertools.combinations_with_replacement(iterable, r)`209210Возвращает подпоследовательности элементов длины *r* из входного *iterable*, допуская повторение отдельных элементов.211212Результат является подмножеством [`product()`](https://python-all.ru/3.16/library/itertools.html#itertools.product), в котором оставлены только те элементы, которые являются подпоследовательностями (с возможными повторениями) *iterable*. Количество возвращаемых подпоследовательностей равно `(n + r - 1)! / r! / (n - 1)!`, если `n > 0`.213214Кортежи-комбинации порождаются в лексикографическом порядке по порядку входного *iterable*. Если входной *iterable* отсортирован, выходные кортежи будут отсортированы.215216Элементы считаются уникальными по позиции, а не по значению. Если входные элементы уникальны, то порождённые комбинации тоже будут уникальны.217218Примерно эквивалентно:219220```python221def combinations_with_replacement(iterable, r):222 # combinations_with_replacement('ABC', 2) → AA AB AC BB BC CC223224 pool = tuple(iterable)225 n = len(pool)226 if not n and r:227 return228 indices = [0] * r229230 yield tuple(pool[i] for i in indices)231 while True:232 for i in reversed(range(r)):233 if indices[i] != n - 1:234 break235 else:236 return237 indices[i:] = [indices[i] + 1] * (r - i)238 yield tuple(pool[i] for i in indices)239```240241Добавлено в версии 3.1.242243#### `itertools.compress(data, selectors)`244245Создаёт итератор, который возвращает элементы из *data*, для которых соответствующий элемент из *selectors* истинен. Останавливается, когда исчерпан либо *data*, либо *selectors*. Примерная реализация:246247```python248def compress(data, selectors):249 # compress('ABCDEF', [1,0,1,0,1,1]) → A C E F250 return (datum for datum, selector in zip(data, selectors) if selector)251```252253Добавлено в версии 3.1.254255#### `itertools.count(start=0, step=1)`256257Создаёт итератор, возвращающий равномерно расположенные значения, начиная с *start*. Может использоваться с [`map()`](https://python-all.ru/3.16/library/functions.html#map) для генерации последовательных точек данных или с [`zip()`](https://python-all.ru/3.16/library/functions.html#zip) для добавления номеров по порядку. Примерная реализация:258259```python260def count(start=0, step=1):261 # count(10) → 10 11 12 13 14 ...262 # count(2.5, 0.5) → 2.5 3.0 3.5 ...263 n = start264 while True:265 yield n266 n += step267```268269При подсчёте с числами с плавающей точкой иногда лучшей точности можно добиться, используя мультипликативный код, например: `(start + step * i for i in count())`.270271Изменено в версии 3.1: Добавлен аргумент *step* и разрешены нецелые аргументы.272273#### `itertools.cycle(iterable)`274275Создаёт итератор, который возвращает элементы из *iterable* и сохраняет копию каждого. Когда iterable исчерпан, возвращает элементы из сохранённой копии. Повторяется бесконечно. Примерная реализация:276277```python278def cycle(iterable):279 # cycle('ABCD') → A B C D A B C D A B C D ...280281 saved = []282 for element in iterable:283 yield element284 saved.append(element)285286 while saved:287 for element in saved:288 yield element289```290291Этот инструмент может потребовать значительного объёма дополнительной памяти (в зависимости от длины iterable).292293#### `itertools.dropwhile(predicate, iterable)`294295Создаёт итератор, который пропускает элементы из *iterable*, пока *predicate* истинен, а затем возвращает все оставшиеся элементы. Примерная реализация:296297```python298def dropwhile(predicate, iterable):299 # dropwhile(lambda x: x<5, [1,4,6,3,8]) → 6 3 8300301 iterator = iter(iterable)302 for x in iterator:303 if not predicate(x):304 yield x305 break306307 for x in iterator:308 yield x309```310311Обратите внимание: этот итератор не выдаёт *ни одного* элемента, пока предикат впервые не станет ложным, поэтому время запуска может быть большим.312313#### `itertools.filterfalse(predicate, iterable)`314315Создаёт итератор, который фильтрует элементы из *iterable*, возвращая только те, для которых *predicate* возвращает ложное значение. Если *predicate* равен `None`, возвращает элементы, которые являются ложными. Примерная реализация:316317```python318def filterfalse(predicate, iterable):319 # filterfalse(lambda x: x<5, [1,4,6,3,8]) → 6 8320321 if predicate is None:322 predicate = bool323324 for x in iterable:325 if not predicate(x):326 yield x327```328329#### `itertools.groupby(iterable, key=None)`330331Make 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.332333Работа `groupby()` аналогична фильтру `uniq` в Unix. Она создает разрыв или новую группу каждый раз, когда изменяется значение ключевой функции (поэтому обычно необходимо отсортировать данные с помощью той же ключевой функции). Такое поведение отличается от SQL GROUP BY, которая объединяет общие элементы независимо от порядка их ввода.334335Возвращаемая группа сама является итератором, который использует общий исходный итерируемый объект с `groupby()`. Поскольку источник общий, при продвижении объекта `groupby()` предыдущая группа перестает быть видимой. Поэтому, если эти данные понадобятся позже, их следует сохранить в виде списка:336337```python338groups = []339uniquekeys = []340data = sorted(data, key=keyfunc)341for k, g in groupby(data, keyfunc):342 groups.append(list(g)) # Сохранить групповой итератор как список343 uniquekeys.append(k)344```345346`groupby()` примерно эквивалентно:347348```python349def groupby(iterable, key=None):350 # [k for k, g in groupby('AAAABBBCCDAABBB')] → A B C D A B351 # [list(g) for k, g in groupby('AAAABBBCCD')] → AAAA BBB CC D352353 keyfunc = (lambda x: x) if key is None else key354 iterator = iter(iterable)355 exhausted = False356357 def _grouper(target_key):358 nonlocal curr_value, curr_key, exhausted359 yield curr_value360 for curr_value in iterator:361 curr_key = keyfunc(curr_value)362 if curr_key != target_key:363 return364 yield curr_value365 exhausted = True366367 try:368 curr_value = next(iterator)369 except StopIteration:370 return371 curr_key = keyfunc(curr_value)372373 while not exhausted:374 target_key = curr_key375 curr_group = _grouper(target_key)376 yield curr_key, curr_group377 if curr_key == target_key:378 for _ in curr_group:379 pass380```381382#### `itertools.islice(iterable, stop)`383384#### `itertools.islice(iterable, start, stop[, step])`385386Создает итератор, который возвращает выбранные элементы из итерируемого объекта. Работает как срез последовательности, но не поддерживает отрицательные значения для *start*, *stop* или *step*.387388Если *start* равен нулю или `None`, итерация начинается с нуля. В противном случае элементы из итерируемого объекта пропускаются до достижения *start*.389390Если *stop* равен `None`, итерация продолжается до тех пор, пока входной объект не будет исчерпан. В противном случае она останавливается на указанной позиции.391392Если *step* равен `None`, шаг по умолчанию равен единице. Элементы возвращаются последовательно, если только *step* не больше единицы, что приводит к пропуску элементов.393394Примерно эквивалентно:395396```python397def islice(iterable, *args):398 # islice('ABCDEFG', 2) → A B399 # islice('ABCDEFG', 2, 4) → C D400 # islice('ABCDEFG', 2, None) → C D E F G401 # islice('ABCDEFG', 0, None, 2) → A C E G402403 s = slice(*args)404 start = 0 if s.start is None else s.start405 stop = s.stop406 step = 1 if s.step is None else s.step407 if start < 0 or (stop is not None and stop < 0) or step <= 0:408 raise ValueError409410 indices = count() if stop is None else range(max(start, stop))411 next_i = start412 for i, element in zip(indices, iterable):413 if i == next_i:414 yield element415 next_i += step416```417418Если входной объект является итератором, то полное потребление *islice* продвигает входной итератор на `max(start, stop)` шагов независимо от значения *step*.419420#### `itertools.pairwise(iterable)`421422Возвращает последовательные перекрывающиеся пары, взятые из входного *iterable*.423424Количество кортежей из двух элементов в выходном итераторе будет на один меньше, чем количество входных элементов. Он будет пустым, если входной итерируемый объект содержит менее двух значений.425426Примерно эквивалентно:427428```python429def pairwise(iterable):430 # pairwise('ABCDEFG') → AB BC CD DE EF FG431432 iterator = iter(iterable)433 a = next(iterator, None)434435 for b in iterator:436 yield a, b437 a = b438```439440Добавлено в версии 3.10.441442#### `itertools.permutations(iterable, r=None)`443444Возвращает последовательные *r*-элементные [перестановки элементов](https://python-all.ru/3.16/library/itertools.html) из *iterable*.445446Если *r* не указан или равен `None`, то *r* по умолчанию равен длине *iterable* и генерируются все возможные перестановки полной длины.447448Результат является подпоследовательностью [`product()`](https://python-all.ru/3.16/library/itertools.html#itertools.product), из которой отфильтрованы записи с повторяющимися элементами. Длина результата определяется [`math.perm()`](https://python-all.ru/3.16/library/math.html#math.perm), который вычисляет `n! / (n - r)!`, когда `0 ≤ r ≤ n`, или ноль, когда `r > n`.449450Кортежи перестановок выдаются в лексикографическом порядке в соответствии с порядком входного *iterable*. Если входной *iterable* отсортирован, выходные кортежи будут созданы в отсортированном порядке.451452Элементы считаются уникальными на основе их позиции, а не значения. Если входные элементы уникальны, то в перестановке не будет повторяющихся значений.453454Примерно эквивалентно:455456```python457def permutations(iterable, r=None):458 # permutations('ABCD', 2) → AB AC AD BA BC BD CA CB CD DA DB DC459 # permutations(range(3)) → 012 021 102 120 201 210460461 pool = tuple(iterable)462 n = len(pool)463 r = n if r is None else r464 if r > n:465 return466467 indices = list(range(n))468 cycles = list(range(n, n-r, -1))469 yield tuple(pool[i] for i in indices[:r])470471 while n:472 for i in reversed(range(r)):473 cycles[i] -= 1474 if cycles[i] == 0:475 indices[i:] = indices[i+1:] + indices[i:i+1]476 cycles[i] = n - i477 else:478 j = cycles[i]479 indices[i], indices[-j] = indices[-j], indices[i]480 yield tuple(pool[i] for i in indices[:r])481 break482 else:483 return484```485486#### `itertools.product(*iterables, repeat=1)`487488[Декартово произведение](https://python-all.ru/3.16/library/itertools.html) входных итерируемых объектов.489490Примерно эквивалентно вложенным циклам for в генераторном выражении. Например, `product(A, B)` возвращает то же, что и `((x,y) for x in A for y in B)`.491492Вложенные циклы работают как одометр: самый правый элемент увеличивается на каждой итерации. Этот шаблон создает лексикографический порядок, так что если входные итерируемые объекты отсортированы, кортежи произведения выдаются в отсортированном порядке.493494Чтобы вычислить произведение итерируемого объекта на самого себя, укажите количество повторений с помощью необязательного именованного аргумента *repeat*. Например, `product(A, repeat=4)` эквивалентно `product(A, A, A, A)`.495496Эта функция примерно эквивалентна следующему коду, за исключением того, что реальная реализация не накапливает промежуточные результаты в памяти:497498```python499def product(*iterables, repeat=1):500 # product('ABCD', 'xy') → Ax Ay Bx By Cx Cy Dx Dy501 # product(range(2), repeat=3) → 000 001 010 011 100 101 110 111502503 if repeat < 0:504 raise ValueError('repeat argument cannot be negative')505 pools = [tuple(pool) for pool in iterables] * repeat506507 result = [[]]508 for pool in pools:509 result = [x+[y] for x in result for y in pool]510511 for prod in result:512 yield tuple(prod)513```514515Перед запуском `product()` полностью потребляет входные итерируемые объекты, сохраняя пулы значений в памяти для генерации произведений. Соответственно, она полезна только для конечных входных данных.516517#### `itertools.repeat(object[, times])`518519Создает итератор, который снова и снова возвращает *object*. Работает бесконечно, если не указан аргумент *times*.520521Примерно эквивалентно:522523```python524def repeat(object, times=None):525 # repeat(10, 3) → 10 10 10526 if times is None:527 while True:528 yield object529 else:530 for i in range(times):531 yield object532```533534Обычное применение *repeat* – передача потока постоянных значений в *map* или *zip*:535536```pycon537>>> list(map(pow, range(10), repeat(2)))538[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]539```540541#### `itertools.starmap(function, iterable)`542543Создаёт итератор, который вычисляет *функцию*, используя аргументы, полученные из *итерируемого объекта*. Используется вместо [`map()`](https://python-all.ru/3.16/library/functions.html#map), когда параметры аргументов уже «предварительно упакованы» в кортежи.544545Различие между [`map()`](https://python-all.ru/3.16/library/functions.html#map) и `starmap()` аналогично различию между `function(a,b)` и `function(*c)`. Примерно эквивалентно:546547```python548def starmap(function, iterable):549 # starmap(pow, [(2,5), (3,2), (10,3)]) → 32 9 1000550 for args in iterable:551 yield function(*args)552```553554#### `itertools.takewhile(predicate, iterable)`555556Создаёт итератор, который возвращает элементы из *итерируемого объекта* до тех пор, пока *предикат* истинен. Примерно эквивалентно:557558```python559def takewhile(predicate, iterable):560 # takewhile(lambda x: x<5, [1,4,6,3,8]) → 1 4561 for x in iterable:562 if not predicate(x):563 break564 yield x565```566567Обратите внимание: элемент, который первым не удовлетворяет условию предиката, потребляется из входного итератора, и доступа к нему нет. Это может быть проблемой, если приложение хочет продолжить потребление входного итератора после того, как *takewhile* отработал до полного исчерпания. Чтобы обойти эту проблему, рассмотрите возможность использования [more-itertools.before\_and\_after()](https://python-all.ru/3.16/library/itertools.html) вместо этого.568569#### `itertools.tee(iterable, n=2)`570571Возвращает *n* независимых итераторов из одного итерируемого объекта.572573Примерно эквивалентно:574575```python576def tee(iterable, n=2):577 if n < 0:578 raise ValueError579 if n == 0:580 return ()581 iterator = _tee(iterable)582 result = [iterator]583 for _ in range(n - 1):584 result.append(_tee(iterator))585 return tuple(result)586587class _tee:588589 def __init__(self, iterable):590 it = iter(iterable)591 if isinstance(it, _tee):592 self.iterator = it.iterator593 self.link = it.link594 else:595 self.iterator = it596 self.link = [None, None]597598 def __iter__(self):599 return self600601 def __next__(self):602 link = self.link603 if link[1] is None:604 link[0] = next(self.iterator)605 link[1] = [None, None]606 value, self.link = link607 return value608```609610Если входной *итерируемый объект* уже является объектом-итератором tee, все элементы возвращаемого кортежа создаются так, как если бы они были произведены upstream-вызовом `tee()`. Этот «шаг уплощения» позволяет вложенным вызовам `tee()` использовать одну и ту же базовую цепочку данных и выполнять один шаг обновления вместо цепочки вызовов.611612Свойство уплощения делает итераторы tee эффективно просматриваемыми:613614```python615def lookahead(tee_iterator):616 "Return the next value without moving the input forward"617 [forked_iterator] = tee(tee_iterator, 1)618 return next(forked_iterator)619```620621```pycon622>>> iterator = iter('abcdef')623>>> [iterator] = tee(iterator, 1) # Сделать входные данные просматриваемыми (peekable)624>>> next(iterator) # Продвинуть итератор вперед625'a'626>>> lookahead(iterator) # Проверить следующее значение627'b'628>>> next(iterator) # Продолжить движение вперед629'b'630```631632Итераторы `tee` не являются потокобезопасными. Исключение [`RuntimeError`](https://python-all.ru/3.16/library/exceptions.html#RuntimeError) может быть возбуждено при одновременном использовании итераторов, возвращённых одним вызовом `tee()`, даже если исходный *итерируемый объект* потокобезопасен.633634Этот инструмент итерации может потребовать значительного вспомогательного хранилища (в зависимости от объёма временных данных, которые необходимо сохранить). В общем случае, если один итератор использует большую часть или все данные до того, как запустится другой итератор, быстрее использовать [`list()`](https://python-all.ru/3.16/library/stdtypes.html#list) вместо `tee()`.635636#### `itertools.zip_longest(*iterables, fillvalue=None)`637638Создаёт итератор, который объединяет элементы из каждого *итерируемого объекта*.639640Если итерируемые объекты имеют разную длину, недостающие значения заполняются с помощью *fillvalue*. Если не указан, *fillvalue* по умолчанию равен `None`.641642Итерация продолжается, пока самый длинный итерируемый объект не будет исчерпан.643644Примерно эквивалентно:645646```python647def zip_longest(*iterables, fillvalue=None):648 # zip_longest('ABCD', 'xy', fillvalue='-') → Ax By C- D-649650 iterators = list(map(iter, iterables))651 num_active = len(iterators)652 if not num_active:653 return654655 while True:656 values = []657 for i, iterator in enumerate(iterators):658 try:659 value = next(iterator)660 except StopIteration:661 num_active -= 1662 if not num_active:663 return664 iterators[i] = repeat(fillvalue)665 value = fillvalue666 values.append(value)667 yield tuple(values)668```669670Если один из итерируемых объектов потенциально бесконечен, то функция `zip_longest()` должна быть обёрнута чем-то, что ограничивает количество вызовов (например, [`islice()`](https://python-all.ru/3.16/library/itertools.html#itertools.islice) или [`takewhile()`](https://python-all.ru/3.16/library/itertools.html#itertools.takewhile)).671672## Рецепты itertools673674В этом разделе представлены рецепты для создания расширенного набора инструментов с использованием существующих itertools в качестве строительных блоков.675676Основная цель рецептов itertools – образовательная. Рецепты демонстрируют различные способы мышления об отдельных инструментах – например, что `chain.from_iterable` связано с концепцией уплощения. Рецепты также дают идеи о том, как инструменты можно комбинировать – например, как `starmap()` и `repeat()` могут работать вместе. Рецепты также показывают шаблоны использования itertools с модулями [`operator`](https://python-all.ru/3.16/library/operator.html#module-operator) и [`collections`](https://python-all.ru/3.16/library/collections.html#module-collections), а также со встроенными itertools, такими как `map()`, `filter()`, `reversed()` и `enumerate()`.677678Второстепенная цель рецептов – служить инкубатором. `accumulate()`, `compress()` и `pairwise()` изначально были рецептами. В настоящее время рецепты `sliding_window()`, `derangements()` и `sieve()` тестируются, чтобы проверить, оправдают ли они себя.679680Практически все эти и многие другие рецепты можно установить из проекта [more-itertools](https://python-all.ru/3.16/library/itertools.html), доступного на Python Package Index:681682```python683python -m pip install more-itertools684```685686Многие рецепты обеспечивают такую же высокую производительность, как и базовый набор инструментов. Превосходная производительность по памяти достигается за счёт обработки элементов по одному, а не загрузки всего итерируемого объекта в память сразу. Объём кода сохраняется небольшим за счёт связывания инструментов в [функциональном стиле](https://python-all.ru/3.16/library/itertools.html). Высокая скорость сохраняется благодаря предпочтению «векторизованных» строительных блоков перед использованием циклов for и [генераторов](https://python-all.ru/3.16/glossary.html#term-generator), которые влекут накладные расходы интерпретатора.687688```python689from itertools import (accumulate, batched, chain, combinations, compress,690 count, cycle, filterfalse, groupby, islice, permutations, product,691 repeat, starmap, tee, zip_longest)692from collections import Counter, deque693from contextlib import suppress694from functools import reduce695from heapq import heappush, heappushpop, heappush_max, heappushpop_max696from math import comb, isqrt, prod, sumprod697from operator import getitem, is_not, itemgetter, mul, neg, truediv698699# ==== Базовые однострочники ====700701def take(n, iterable):702 "Return first n items of the iterable as a list."703 return list(islice(iterable, n))704705def prepend(value, iterable):706 "Prepend a single value in front of an iterable."707 # prepend(1, [2, 3, 4]) → 1 2 3 4708 return chain([value], iterable)709710def repeatfunc(function, times=None, *args):711 "Repeat calls to a function with specified arguments."712 if times is None:713 return starmap(function, repeat(args))714 return starmap(function, repeat(args, times))715716def flatten(list_of_lists):717 "Flatten one level of nesting."718 return chain.from_iterable(list_of_lists)719720def ncycles(iterable, n):721 "Returns the sequence elements n times."722 return chain.from_iterable(repeat(tuple(iterable), n))723724def loops(n):725 "Loop n times. Like range(n) but without creating integers."726 # for _ in loops(100): ...727 return repeat(None, n)728729def tail(n, iterable):730 "Return an iterator over the last n items."731 # tail(3, 'ABCDEFG') → E F G732 return iter(deque(iterable, maxlen=n))733734def consume(iterator, n=None):735 "Advance the iterator n-steps ahead. If n is None, consume entirely."736 # Используйте функции, потребляющие итераторы на скорости C.737 if n is None:738 deque(iterator, maxlen=0)739 else:740 next(islice(iterator, n, n), None)741742def nth(iterable, n, default=None):743 "Returns the nth item or a default value."744 return next(islice(iterable, n, None), default)745746def quantify(iterable, predicate=bool):747 "Given a predicate that returns True or False, count the True results."748 return sum(map(predicate, iterable))749750def first_true(iterable, default=False, predicate=None):751 "Returns the first true value or the *default* if there is no true value."752 # first_true([a, b, c], x) → a or b or c or x753 # first_true([a, b], x, f) → a if f(a) else b if f(b) else x754 return next(filter(predicate, iterable), default)755756def all_equal(iterable, key=None):757 "Returns True if all the elements are equal to each other."758 # all_equal('4٤௪౪໔', key=int) → True759 return len(take(2, groupby(iterable, key))) <= 1760761# ==== Конвейеры данных ====762763def unique_justseen(iterable, key=None):764 "Yield unique elements, preserving order. Remember only the element just seen."765 # unique_justseen('AAAABBBCCDAABBB') → A B C D A B766 # unique_justseen('ABBcCAD', str.casefold) → A B c A D767 if key is None:768 return map(itemgetter(0), groupby(iterable))769 return map(next, map(itemgetter(1), groupby(iterable, key)))770771def unique_everseen(iterable, key=None):772 "Yield unique elements, preserving order. Remember all elements ever seen."773 # unique_everseen('AAAABBBCCDAABBB') → A B C D774 # unique_everseen('ABBcCAD', str.casefold) → A B c D775 seen = set()776 if key is None:777 for element in filterfalse(seen.__contains__, iterable):778 seen.add(element)779 yield element780 else:781 for element in iterable:782 k = key(element)783 if k not in seen:784 seen.add(k)785 yield element786787def unique(iterable, key=None, reverse=False):788 "Yield unique elements in sorted order. Supports unhashable inputs."789 # unique([[1, 2], [3, 4], [1, 2]]) → [1, 2] [3, 4]790 sequenced = sorted(iterable, key=key, reverse=reverse)791 return unique_justseen(sequenced, key=key)792793def sliding_window(iterable, n):794 "Collect data into overlapping fixed-length chunks or blocks."795 # sliding_window('ABCDEFG', 3) → ABC BCD CDE DEF EFG796 iterator = iter(iterable)797 window = deque(islice(iterator, n - 1), maxlen=n)798 for x in iterator:799 window.append(x)800 yield tuple(window)801802def grouper(iterable, n, *, incomplete='fill', fillvalue=None):803 "Collect data into non-overlapping fixed-length chunks or blocks."804 # grouper('ABCDEFG', 3, fillvalue='x') → ABC DEF Gxx805 # grouper('ABCDEFG', 3, incomplete='strict') → ABC DEF ValueError806 # grouper('ABCDEFG', 3, incomplete='ignore') → ABC DEF807 iterators = [iter(iterable)] * n808 match incomplete:809 case 'fill':810 return zip_longest(*iterators, fillvalue=fillvalue)811 case 'strict':812 return zip(*iterators, strict=True)813 case 'ignore':814 return zip(*iterators)815 case _:816 raise ValueError('Expected fill, strict, or ignore')817818def roundrobin(*iterables):819 "Visit input iterables in a cycle until each is exhausted."820 # roundrobin('ABC', 'D', 'EF') → A D E B F C821 # Алгоритм Джорджа Саккиса822 iterators = map(iter, iterables)823 for num_active in range(len(iterables), 0, -1):824 iterators = cycle(islice(iterators, num_active))825 yield from map(next, iterators)826827def subslices(seq):828 "Return all contiguous non-empty subslices of a sequence."829 # subslices('ABCD') → A AB ABC ABCD B BC BCD C CD D830 slices = starmap(slice, combinations(range(len(seq) + 1), 2))831 return map(getitem, repeat(seq), slices)832833def derangements(iterable, r=None):834 "Produce r length permutations without fixed points."835 # derangements('ABCD') → BADC BCDA BDAC CADB CDAB CDBA DABC DCAB DCBA836 # Алгоритм Стефана Похманна837 seq = tuple(iterable)838 pos = tuple(range(len(seq)))839 have_moved = map(map, repeat(is_not), repeat(pos), permutations(pos, r=r))840 valid_derangements = map(all, have_moved)841 return compress(permutations(seq, r=r), valid_derangements)842843def iter_index(iterable, value, start=0, stop=None):844 "Return indices where a value occurs in a sequence or iterable."845 # iter_index('AABCADEAF', 'A') → 0 1 4 7846 seq_index = getattr(iterable, 'index', None)847 if seq_index is None:848 iterator = islice(iterable, start, stop)849 for i, element in enumerate(iterator, start):850 if element is value or element == value:851 yield i852 else:853 stop = len(iterable) if stop is None else stop854 i = start855 with suppress(ValueError):856 while True:857 yield (i := seq_index(value, i, stop))858 i += 1859860def iter_except(function, exception, first=None):861 "Convert a call-until-exception interface to an iterator interface."862 # iter_except(d.popitem, KeyError) → неблокирующий итератор словаря863 with suppress(exception):864 if first is not None:865 yield first()866 while True:867 yield function()868869# ==== Математические операции ====870871def multinomial(*counts):872 "Number of distinct arrangements of a multiset."873 # Counter('abracadabra').values() → 5 2 2 1 1874 # multinomial(5, 2, 2, 1, 1) → 83160875 return prod(map(comb, accumulate(counts), counts))876877def powerset(iterable):878 "Subsequences of the iterable from shortest to longest."879 # powerset([1,2,3]) → () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)880 s = list(iterable)881 return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))882883def sum_of_squares(iterable):884 "Add up the squares of the input values."885 # sum_of_squares([10, 20, 30]) → 1400886 return sumprod(*tee(iterable))887888# ==== Операции с матрицами ====889890def reshape(matrix, columns):891 "Reshape a 2-D matrix to have a given number of columns."892 # reshape([(0, 1), (2, 3), (4, 5)], 3) → (0, 1, 2) (3, 4, 5)893 return batched(chain.from_iterable(matrix), columns, strict=True)894895def transpose(matrix):896 "Swap the rows and columns of a 2-D matrix."897 # transpose([(1, 2, 3), (11, 22, 33)]) → (1, 11) (2, 22) (3, 33)898 return zip(*matrix, strict=True)899900def matmul(m1, m2):901 "Multiply two matrices."902 # matmul([(7, 5), (3, 5)], [(2, 5), (7, 9)]) → (49, 80) (41, 60)903 n = len(m2[0])904 return batched(starmap(sumprod, product(m1, transpose(m2))), n)905906# ==== Арифметика многочленов ====907908def convolve(signal, kernel):909 """Дискретная линейная свёртка двух итерируемых объектов.910 Эквивалентно умножению многочленов.911912 Свёртки математически коммутативны; однако входные данные913 вычисляются по-разному. Сигнал потребляется лениво и может быть914 бесконечным. Ядро полностью потребляется до начала вычислений.915916 Статья: https://betterexplained.com/articles/intuitive-convolution/917 Видео: https://www.youtube.com/watch?v=KuXjwB4LzSA918 """919 # convolve([1, -1, -20], [1, -3]) → 1 -4 -17 60920 # convolve(data, [0.25, 0.25, 0.25, 0.25]) → Скользящее среднее (размытие)921 # convolve(data, [1/2, 0, -1/2]) → Оценка первой производной922 # convolve(data, [1, -2, 1]) → Оценка второй производной923 kernel = tuple(kernel)[::-1]924 n = len(kernel)925 padded_signal = chain(repeat(0, n-1), signal, repeat(0, n-1))926 windowed_signal = sliding_window(padded_signal, n)927 return map(sumprod, repeat(kernel), windowed_signal)928929def polynomial_from_roots(roots):930 """Вычисляет коэффициенты многочлена по его корням.931932 (x - 5) (x + 4) (x - 3) раскрывается в: x³ -4x² -17x + 60933 """934 # polynomial_from_roots([5, -4, 3]) → [1, -4, -17, 60]935 factors = zip(repeat(1), map(neg, roots))936 return list(reduce(convolve, factors, [1]))937938def polynomial_eval(coefficients, x):939 """Вычисляет значение многочлена в заданной точке.940941 Вычисляет с лучшей численной устойчивостью, чем метод Горнера.942 """943 # Вычислить x³ -4x² -17x + 60 при x = 5944 # polynomial_eval([1, -4, -17, 60], x=5) → 0945 n = len(coefficients)946 if not n:947 return type(x)(0)948 powers = map(pow, repeat(x), reversed(range(n)))949 return sumprod(coefficients, powers)950951def polynomial_derivative(coefficients):952 """Вычисляет первую производную многочлена.953954 f(x) = x³ -4x² -17x + 60955 f'(x) = 3x² -8x -17956 """957 # polynomial_derivative([1, -4, -17, 60]) → [3, -8, -17]958 n = len(coefficients)959 powers = reversed(range(1, n))960 return list(map(mul, coefficients, powers))961962# ==== Теория чисел ====963964def sieve(n):965 "Primes less than n."966 # sieve(30) → 2 3 5 7 11 13 17 19 23 29967 if n > 2:968 yield 2969 data = bytearray((0, 1)) * (n // 2)970 for p in iter_index(data, 1, start=3, stop=isqrt(n) + 1):971 data[p*p : n : p+p] = bytes(len(range(p*p, n, p+p)))972 yield from iter_index(data, 1, start=3)973974def factor(n):975 "Prime factors of n."976 # factor(99) → 3 3 11977 # factor(1_000_000_000_000_007) → 47 59 360620266859978 # factor(1_000_000_000_000_403) → 1000000000000403979 for prime in sieve(isqrt(n) + 1):980 while not n % prime:981 yield prime982 n //= prime983 if n == 1:984 return985 if n > 1:986 yield n987988def is_prime(n):989 "Return True if n is prime."990 # is_prime(1_000_000_000_000_403) → True991 return n > 1 and next(factor(n)) == n992993def totient(n):994 "Count of natural numbers up to n that are coprime to n."995 # https://mathworld.wolfram.com/TotientFunction.html996 # totient(12) → 4 потому что len([1, 5, 7, 11]) == 4997 for prime in set(factor(n)):998 n -= n // prime999 return n10001001# ==== Скользящие статистики ====10021003def running_mean(iterable):1004 "Average of values seen so far."1005 # running_mean([37, 33, 38, 28]) → 37 35 36 341006 return map(truediv, accumulate(iterable), count(1))10071008def running_min(iterable):1009 "Smallest of values seen so far."1010 # running_min([37, 33, 38, 28]) → 37 33 33 281011 return accumulate(iterable, func=min)10121013def running_max(iterable):1014 "Largest of values seen so far."1015 # running_max([37, 33, 38, 28]) → 37 37 38 381016 return accumulate(iterable, func=max)10171018def running_median(iterable):1019 "Median of values seen so far."1020 # running_median([37, 33, 38, 28]) → 37 35 37 351021 read = iter(iterable).__next__1022 lo = [] # максимальная куча1023 hi = [] # мин-куча того же размера, что и lo, или на единицу меньше1024 with suppress(StopIteration):1025 while True:1026 heappush_max(lo, heappushpop(hi, read()))1027 yield lo[0]1028 heappush(hi, heappushpop_max(lo, read()))1029 yield (lo[0] + hi[0]) / 210301031def running_statistics(iterable):1032 "Aggregate statistics for values seen so far."1033 # Создать кортежи: (size, minimum, median, maximum, mean)1034 t0, t1, t2, t3 = tee(iterable, 4)1035 return zip(1036 count(1),1037 running_min(t0),1038 running_median(t1),1039 running_max(t2),1040 running_mean(t3),1041 )1042```1043