itertools.md
1> **Источник:** https://python-all.ru/3.12/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.12/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.12/library/functions.html#map) и [`count()`](https://python-all.ru/3.12/library/itertools.html#itertools.count) для получения `map(f, count())`.1617Эти инструменты и их встроенные аналоги также хорошо работают с высокоскоростными функциями из модуля [`operator`](https://python-all.ru/3.12/library/operator.html#module-operator). Например, оператор умножения можно применить к двум векторам, чтобы получить эффективное скалярное произведение: `sum(starmap(operator.mul, zip(vec1, vec2, strict=True)))`.1819**Бесконечные итераторы:**2021| Итератор | Аргументы | Результаты | Пример |22| --- | --- | --- | --- |23| [`count()`](https://python-all.ru/3.12/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.12/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.12/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.12/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| [`batched()`](https://python-all.ru/3.12/library/itertools.html#itertools.batched) | p, n | (p0, p1, …, p\_n-1), … | `batched('ABCDEFG', n=3) → ABC DEF G` |33| [`chain()`](https://python-all.ru/3.12/library/itertools.html#itertools.chain) | p, q, … | p0, p1, … plast, q0, q1, … | `chain('ABC', 'DEF') → A B C D E F` |34| [`chain.from_iterable()`](https://python-all.ru/3.12/library/itertools.html#itertools.chain.from_iterable) | iterable | p0, p1, … plast, q0, q1, … | `chain.from_iterable(['ABC', 'DEF']) → A B C D E F` |35| [`compress()`](https://python-all.ru/3.12/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` |36| [`dropwhile()`](https://python-all.ru/3.12/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` |37| [`filterfalse()`](https://python-all.ru/3.12/library/itertools.html#itertools.filterfalse) | predicate, seq | элементы seq, для которых predicate(elem) не выполняется | `filterfalse(lambda x: x<5, [1,4,6,3,8]) → 6 8` |38| [`groupby()`](https://python-all.ru/3.12/library/itertools.html#itertools.groupby) | iterable\[, key\] | подитераторы, сгруппированные по значению key(v) | |39| [`islice()`](https://python-all.ru/3.12/library/itertools.html#itertools.islice) | seq, \[start,\] stop \[, step\] | элементы из seq\[start:stop:step\] | `islice('ABCDEFG', 2, None) → C D E F G` |40| [`pairwise()`](https://python-all.ru/3.12/library/itertools.html#itertools.pairwise) | iterable | (p\[0\], p\[1\]), (p\[1\], p\[2\]) | `pairwise('ABCDEFG') → AB BC CD DE EF FG` |41| [`starmap()`](https://python-all.ru/3.12/library/itertools.html#itertools.starmap) | func, seq | func(\*seq\[0\]), func(\*seq\[1\]), … | `starmap(pow, [(2,5), (3,2), (10,3)]) → 32 9 1000` |42| [`takewhile()`](https://python-all.ru/3.12/library/itertools.html#itertools.takewhile) | predicate, seq | seq\[0\], seq\[1\], пока predicate не вернёт ложь | `takewhile(lambda x: x<5, [1,4,6,3,8]) → 1 4` |43| [`tee()`](https://python-all.ru/3.12/library/itertools.html#itertools.tee) | it, n | it1, it2, … itn разделяет один итератор на n | |44| [`zip_longest()`](https://python-all.ru/3.12/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-` |4546**Комбинаторные итераторы:**4748| Итератор | Аргументы | Результаты |49| --- | --- | --- |50| [`product()`](https://python-all.ru/3.12/library/itertools.html#itertools.product) | p, q, … \[repeat=1\] | декартово произведение, эквивалентно вложенному циклу for |51| [`permutations()`](https://python-all.ru/3.12/library/itertools.html#itertools.permutations) | p\[, r\] | кортежи длиной r, все возможные перестановки, без повторяющихся элементов |52| [`combinations()`](https://python-all.ru/3.12/library/itertools.html#itertools.combinations) | p, r | кортежи длиной r, в отсортированном порядке, без повторяющихся элементов |53| [`combinations_with_replacement()`](https://python-all.ru/3.12/library/itertools.html#itertools.combinations_with_replacement) | p, r | кортежи длиной r, в отсортированном порядке, с повторяющимися элементами |5455| Примеры | Результаты |56| --- | --- |57| `product('ABCD', repeat=2)` | `AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD` |58| `permutations('ABCD', 2)` | `AB AC AD BA BC BD CA CB CD DA DB DC` |59| `combinations('ABCD', 2)` | `AB AC AD BC BD CD` |60| `combinations_with_replacement('ABCD', 2)` | `AA AB AC AD BB BC BD CC CD DD` |6162## Функции itertools6364Следующие функции модуля создают и возвращают итераторы. Некоторые из них порождают потоки бесконечной длины, поэтому обращаться к ним следует только с помощью функций или циклов, которые обрывают поток.6566#### `itertools.accumulate(iterable[, function, *, initial=None])`6768Создаёт итератор, возвращающий накопленные суммы или накопленные результаты других бинарных функций.6970Если *function* не указана, по умолчанию используется сложение. *Function* должна принимать два аргумента: накопленное значение и очередной элемент из *iterable*.7172Если указано начальное значение *initial*, накопление начнётся с него, и в результате будет на один элемент больше, чем во входном итерируемом объекте.7374Примерно эквивалентно:7576```python77def accumulate(iterable, function=operator.add, *, initial=None):78 'Return running totals'79 # accumulate([1,2,3,4,5]) → 1 3 6 10 1580 # accumulate([1,2,3,4,5], initial=100) → 100 101 103 106 110 11581 # accumulate([1,2,3,4,5], operator.mul) → 1 2 6 24 1208283 iterator = iter(iterable)84 total = initial85 if initial is None:86 try:87 total = next(iterator)88 except StopIteration:89 return9091 yield total92 for element in iterator:93 total = function(total, element)94 yield total95```9697Аргумент *function* можно установить в [`min()`](https://python-all.ru/3.12/library/functions.html#min) для текущего минимума, [`max()`](https://python-all.ru/3.12/library/functions.html#max) для текущего максимума или [`operator.mul()`](https://python-all.ru/3.12/library/operator.html#operator.mul) для текущего произведения. [Таблицы амортизации](https://python-all.ru/3.12/library/itertools.html) можно построить, накапливая проценты и применяя платежи:9899```pycon100>>> data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8]101>>> list(accumulate(data, max)) # текущий максимум102[3, 4, 6, 6, 6, 9, 9, 9, 9, 9]103>>> list(accumulate(data, operator.mul)) # текущее произведение104[3, 12, 72, 144, 144, 1296, 0, 0, 0, 0]105106# Amortize a 5% loan of 1000 with 10 annual payments of 90107>>> update = lambda balance, payment: round(balance * 1.05) - payment108>>> list(accumulate(repeat(90, 10), update, initial=1_000))109[1000, 960, 918, 874, 828, 779, 728, 674, 618, 559, 497]110```111112См. [`functools.reduce()`](https://python-all.ru/3.12/library/functools.html#functools.reduce) – похожая функция, возвращающая только итоговое накопленное значение.113114Добавлено в версии 3.2.115116Изменено в версии 3.3: Добавлен необязательный параметр *function*.117118Изменено в версии 3.8: Добавлен необязательный параметр *initial*.119120#### `itertools.batched(iterable, n)`121122Группирует данные из *iterable* в кортежи длины *n*. Последняя группа может быть короче *n*.123124Перебирает входной iterable и накапливает данные в кортежи размером до *n*. Входные данные обрабатываются лениво – ровно столько, чтобы заполнить одну группу. Результат возвращается сразу, как только группа заполнена или входной iterable исчерпан:125126```pycon127>>> flattened_data = ['roses', 'red', 'violets', 'blue', 'sugar', 'sweet']128>>> unflattened = list(batched(flattened_data, 2))129>>> unflattened130[('roses', 'red'), ('violets', 'blue'), ('sugar', 'sweet')]131```132133Примерно эквивалентно:134135```python136def batched(iterable, n):137 # batched('ABCDEFG', 3) → ABC DEF G138 if n < 1:139 raise ValueError('n must be at least one')140 iterator = iter(iterable)141 while batch := tuple(islice(iterator, n)):142 yield batch143```144145Добавлено в версии 3.12.146147#### `itertools.chain(*iterables)`148149Создаёт итератор, который возвращает элементы из первого итерируемого объекта, пока он не будет исчерпан, затем переходит к следующему, пока все итерируемые объекты не будут исчерпаны. Используется для объединения последовательностей в одну. Приблизительный эквивалент:150151```python152def chain(*iterables):153 # chain('ABC', 'DEF') → A B C D E F154 for iterable in iterables:155 yield from iterable156```157158#### `classmethod chain.from_iterable(iterable)`159160Альтернативный конструктор для [`chain()`](https://python-all.ru/3.12/library/itertools.html#itertools.chain). Получает цепочку входных данных из одного аргумента iterable, который вычисляется лениво. Примерная реализация:161162```python163def from_iterable(iterables):164 # chain.from_iterable(['ABC', 'DEF']) → A B C D E F165 for iterable in iterables:166 yield from iterable167```168169#### `itertools.combinations(iterable, r)`170171Возвращает подпоследовательности элементов длины *r* из входного *iterable*.172173Результат является подмножеством [`product()`](https://python-all.ru/3.12/library/itertools.html#itertools.product), в котором оставлены только те элементы, которые являются подпоследовательностями *iterable*. Длина результата задаётся выражением [`math.comb()`](https://python-all.ru/3.12/library/math.html#math.comb), которое равно `n! / r! / (n - r)!`, если `0 ≤ r ≤ n`, или нулю, если `r > n`.174175Кортежи-комбинации порождаются в лексикографическом порядке по порядку входного *iterable*. Если входной *iterable* отсортирован, выходные кортежи также будут отсортированы.176177Элементы считаются уникальными по позиции, а не по значению. Если входные элементы уникальны, то в каждой комбинации не будет повторяющихся значений.178179Примерно эквивалентно:180181```python182def combinations(iterable, r):183 # combinations('ABCD', 2) → AB AC AD BC BD CD184 # combinations(range(4), 3) → 012 013 023 123185186 pool = tuple(iterable)187 n = len(pool)188 if r > n:189 return190 indices = list(range(r))191192 yield tuple(pool[i] for i in indices)193 while True:194 for i in reversed(range(r)):195 if indices[i] != i + n - r:196 break197 else:198 return199 indices[i] += 1200 for j in range(i+1, r):201 indices[j] = indices[j-1] + 1202 yield tuple(pool[i] for i in indices)203```204205#### `itertools.combinations_with_replacement(iterable, r)`206207Возвращает подпоследовательности элементов длины *r* из входного *iterable*, допуская повторение отдельных элементов.208209Результат является подмножеством [`product()`](https://python-all.ru/3.12/library/itertools.html#itertools.product), в котором оставлены только те элементы, которые являются подпоследовательностями (с возможными повторениями) *iterable*. Количество возвращаемых подпоследовательностей равно `(n + r - 1)! / r! / (n - 1)!`, если `n > 0`.210211Кортежи-комбинации порождаются в лексикографическом порядке по порядку входного *iterable*. Если входной *iterable* отсортирован, выходные кортежи будут отсортированы.212213Элементы считаются уникальными по позиции, а не по значению. Если входные элементы уникальны, то порождённые комбинации тоже будут уникальны.214215Примерно эквивалентно:216217```python218def combinations_with_replacement(iterable, r):219 # combinations_with_replacement('ABC', 2) → AA AB AC BB BC CC220221 pool = tuple(iterable)222 n = len(pool)223 if not n and r:224 return225 indices = [0] * r226227 yield tuple(pool[i] for i in indices)228 while True:229 for i in reversed(range(r)):230 if indices[i] != n - 1:231 break232 else:233 return234 indices[i:] = [indices[i] + 1] * (r - i)235 yield tuple(pool[i] for i in indices)236```237238Добавлено в версии 3.1.239240#### `itertools.compress(data, selectors)`241242Создаёт итератор, который возвращает элементы из *data*, для которых соответствующий элемент из *selectors* истинен. Останавливается, когда исчерпан либо *data*, либо *selectors*. Примерная реализация:243244```python245def compress(data, selectors):246 # compress('ABCDEF', [1,0,1,0,1,1]) → A C E F247 return (datum for datum, selector in zip(data, selectors) if selector)248```249250Добавлено в версии 3.1.251252#### `itertools.count(start=0, step=1)`253254Создаёт итератор, возвращающий равномерно расположенные значения, начиная с *start*. Может использоваться с [`map()`](https://python-all.ru/3.12/library/functions.html#map) для генерации последовательных точек данных или с [`zip()`](https://python-all.ru/3.12/library/functions.html#zip) для добавления номеров по порядку. Примерная реализация:255256```python257def count(start=0, step=1):258 # count(10) → 10 11 12 13 14 ...259 # count(2.5, 0.5) → 2.5 3.0 3.5 ...260 n = start261 while True:262 yield n263 n += step264```265266При подсчёте с числами с плавающей точкой иногда лучшей точности можно добиться, используя мультипликативный код, например: `(start + step * i for i in count())`.267268Изменено в версии 3.1: Добавлен аргумент *step* и разрешены нецелые аргументы.269270#### `itertools.cycle(iterable)`271272Создаёт итератор, который возвращает элементы из *iterable* и сохраняет копию каждого. Когда iterable исчерпан, возвращает элементы из сохранённой копии. Повторяется бесконечно. Примерная реализация:273274```python275def cycle(iterable):276 # cycle('ABCD') → A B C D A B C D A B C D ...277 saved = []278 for element in iterable:279 yield element280 saved.append(element)281 while saved:282 for element in saved:283 yield element284```285286Этот инструмент может потребовать значительного объёма дополнительной памяти (в зависимости от длины iterable).287288#### `itertools.dropwhile(predicate, iterable)`289290Создаёт итератор, который пропускает элементы из *iterable*, пока *predicate* истинен, а затем возвращает все оставшиеся элементы. Примерная реализация:291292```python293def dropwhile(predicate, iterable):294 # dropwhile(lambda x: x<5, [1,4,6,3,8]) → 6 3 8295296 iterator = iter(iterable)297 for x in iterator:298 if not predicate(x):299 yield x300 break301302 for x in iterator:303 yield x304```305306Обратите внимание: этот итератор не выдаёт *ни одного* элемента, пока предикат впервые не станет ложным, поэтому время запуска может быть большим.307308#### `itertools.filterfalse(predicate, iterable)`309310Создаёт итератор, который фильтрует элементы из *iterable*, возвращая только те, для которых *predicate* возвращает ложное значение. Если *predicate* равен `None`, возвращает элементы, которые являются ложными. Примерная реализация:311312```python313def filterfalse(predicate, iterable):314 # filterfalse(lambda x: x<5, [1,4,6,3,8]) → 6 8315 if predicate is None:316 predicate = bool317 for x in iterable:318 if not predicate(x):319 yield x320```321322#### `itertools.groupby(iterable, key=None)`323324Make 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.325326Работа [`groupby()`](https://python-all.ru/3.12/library/itertools.html#itertools.groupby) аналогична фильтру `uniq` в Unix. Она создает разрыв или новую группу каждый раз, когда изменяется значение ключевой функции (поэтому обычно необходимо отсортировать данные с помощью той же ключевой функции). Такое поведение отличается от SQL GROUP BY, которая объединяет общие элементы независимо от порядка их ввода.327328Возвращаемая группа сама является итератором, который использует общий исходный итерируемый объект с [`groupby()`](https://python-all.ru/3.12/library/itertools.html#itertools.groupby). Поскольку источник общий, при продвижении объекта [`groupby()`](https://python-all.ru/3.12/library/itertools.html#itertools.groupby) предыдущая группа перестает быть видимой. Поэтому, если эти данные понадобятся позже, их следует сохранить в виде списка:329330```python331groups = []332uniquekeys = []333data = sorted(data, key=keyfunc)334for k, g in groupby(data, keyfunc):335 groups.append(list(g)) # Сохранить групповой итератор как список336 uniquekeys.append(k)337```338339[`groupby()`](https://python-all.ru/3.12/library/itertools.html#itertools.groupby) примерно эквивалентно:340341```python342def groupby(iterable, key=None):343 # [k for k, g in groupby('AAAABBBCCDAABBB')] → A B C D A B344 # [list(g) for k, g in groupby('AAAABBBCCD')] → AAAA BBB CC D345346 keyfunc = (lambda x: x) if key is None else key347 iterator = iter(iterable)348 exhausted = False349350 def _grouper(target_key):351 nonlocal curr_value, curr_key, exhausted352 yield curr_value353 for curr_value in iterator:354 curr_key = keyfunc(curr_value)355 if curr_key != target_key:356 return357 yield curr_value358 exhausted = True359360 try:361 curr_value = next(iterator)362 except StopIteration:363 return364 curr_key = keyfunc(curr_value)365366 while not exhausted:367 target_key = curr_key368 curr_group = _grouper(target_key)369 yield curr_key, curr_group370 if curr_key == target_key:371 for _ in curr_group:372 pass373```374375#### `itertools.islice(iterable, stop)`376377#### `itertools.islice(iterable, start, stop[, step])`378379Создает итератор, который возвращает выбранные элементы из итерируемого объекта. Работает как срез последовательности, но не поддерживает отрицательные значения для *start*, *stop* или *step*.380381Если *start* равен нулю или `None`, итерация начинается с нуля. В противном случае элементы из итерируемого объекта пропускаются до достижения *start*.382383Если *stop* равен `None`, итерация продолжается до тех пор, пока итератор не будет исчерпан (если это вообще произойдёт). В противном случае он останавливается на указанной позиции.384385Если *step* равен `None`, шаг по умолчанию равен единице. Элементы возвращаются последовательно, если только *step* не больше единицы, что приводит к пропуску элементов.386387Примерно эквивалентно:388389```python390def islice(iterable, *args):391 # islice('ABCDEFG', 2) → A B392 # islice('ABCDEFG', 2, 4) → C D393 # islice('ABCDEFG', 2, None) → C D E F G394 # islice('ABCDEFG', 0, None, 2) → A C E G395396 s = slice(*args)397 start = 0 if s.start is None else s.start398 stop = s.stop399 step = 1 if s.step is None else s.step400 if start < 0 or (stop is not None and stop < 0) or step <= 0:401 raise ValueError402403 indices = count() if stop is None else range(max(start, stop))404 next_i = start405 for i, element in zip(indices, iterable):406 if i == next_i:407 yield element408 next_i += step409```410411#### `itertools.pairwise(iterable)`412413Возвращает последовательные перекрывающиеся пары, взятые из входного *iterable*.414415Количество кортежей из двух элементов в выходном итераторе будет на один меньше, чем количество входных элементов. Он будет пустым, если входной итерируемый объект содержит менее двух значений.416417Примерно эквивалентно:418419```python420def pairwise(iterable):421 # pairwise('ABCDEFG') → AB BC CD DE EF FG422 iterator = iter(iterable)423 a = next(iterator, None)424 for b in iterator:425 yield a, b426 a = b427```428429Добавлено в версии 3.10.430431#### `itertools.permutations(iterable, r=None)`432433Возвращает последовательные *r*-элементные [перестановки элементов](https://python-all.ru/3.12/library/itertools.html) из *iterable*.434435Если *r* не указан или равен `None`, то *r* по умолчанию равен длине *iterable* и генерируются все возможные перестановки полной длины.436437Результат является подпоследовательностью [`product()`](https://python-all.ru/3.12/library/itertools.html#itertools.product), из которой отфильтрованы записи с повторяющимися элементами. Длина результата определяется [`math.perm()`](https://python-all.ru/3.12/library/math.html#math.perm), который вычисляет `n! / (n - r)!`, когда `0 ≤ r ≤ n`, или ноль, когда `r > n`.438439Кортежи перестановок выдаются в лексикографическом порядке в соответствии с порядком входного *iterable*. Если входной *iterable* отсортирован, выходные кортежи будут созданы в отсортированном порядке.440441Элементы считаются уникальными на основе их позиции, а не значения. Если входные элементы уникальны, то в перестановке не будет повторяющихся значений.442443Примерно эквивалентно:444445```python446def permutations(iterable, r=None):447 # permutations('ABCD', 2) → AB AC AD BA BC BD CA CB CD DA DB DC448 # permutations(range(3)) → 012 021 102 120 201 210449450 pool = tuple(iterable)451 n = len(pool)452 r = n if r is None else r453 if r > n:454 return455456 indices = list(range(n))457 cycles = list(range(n, n-r, -1))458 yield tuple(pool[i] for i in indices[:r])459460 while n:461 for i in reversed(range(r)):462 cycles[i] -= 1463 if cycles[i] == 0:464 indices[i:] = indices[i+1:] + indices[i:i+1]465 cycles[i] = n - i466 else:467 j = cycles[i]468 indices[i], indices[-j] = indices[-j], indices[i]469 yield tuple(pool[i] for i in indices[:r])470 break471 else:472 return473```474475#### `itertools.product(*iterables, repeat=1)`476477Декартово произведение входных итерируемых объектов.478479Примерно эквивалентно вложенным циклам for в генераторном выражении. Например, `product(A, B)` возвращает то же, что и `((x,y) for x in A for y in B)`.480481Вложенные циклы работают как одометр: самый правый элемент увеличивается на каждой итерации. Этот шаблон создает лексикографический порядок, так что если входные итерируемые объекты отсортированы, кортежи произведения выдаются в отсортированном порядке.482483Чтобы вычислить произведение итерируемого объекта на самого себя, укажите количество повторений с помощью необязательного именованного аргумента *repeat*. Например, `product(A, repeat=4)` эквивалентно `product(A, A, A, A)`.484485Эта функция примерно эквивалентна следующему коду, за исключением того, что реальная реализация не накапливает промежуточные результаты в памяти:486487```python488def product(*iterables, repeat=1):489 # product('ABCD', 'xy') → Ax Ay Bx By Cx Cy Dx Dy490 # product(range(2), repeat=3) → 000 001 010 011 100 101 110 111491492 pools = [tuple(pool) for pool in iterables] * repeat493494 result = [[]]495 for pool in pools:496 result = [x+[y] for x in result for y in pool]497498 for prod in result:499 yield tuple(prod)500```501502Перед запуском [`product()`](https://python-all.ru/3.12/library/itertools.html#itertools.product) полностью потребляет входные итерируемые объекты, сохраняя пулы значений в памяти для генерации произведений. Соответственно, она полезна только для конечных входных данных.503504#### `itertools.repeat(object[, times])`505506Создает итератор, который снова и снова возвращает *object*. Работает бесконечно, если не указан аргумент *times*.507508Примерно эквивалентно:509510```python511def repeat(object, times=None):512 # repeat(10, 3) → 10 10 10513 if times is None:514 while True:515 yield object516 else:517 for i in range(times):518 yield object519```520521Обычное применение *repeat* – передача потока постоянных значений в *map* или *zip*:522523```pycon524>>> list(map(pow, range(10), repeat(2)))525[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]526```527528#### `itertools.starmap(function, iterable)`529530Создаёт итератор, который вычисляет *функцию*, используя аргументы, полученные из *итерируемого объекта*. Используется вместо [`map()`](https://python-all.ru/3.12/library/functions.html#map), когда параметры аргументов уже «предварительно упакованы» в кортежи.531532Различие между [`map()`](https://python-all.ru/3.12/library/functions.html#map) и [`starmap()`](https://python-all.ru/3.12/library/itertools.html#itertools.starmap) аналогично различию между `function(a,b)` и `function(*c)`. Примерно эквивалентно:533534```python535def starmap(function, iterable):536 # starmap(pow, [(2,5), (3,2), (10,3)]) → 32 9 1000537 for args in iterable:538 yield function(*args)539```540541#### `itertools.takewhile(predicate, iterable)`542543Создаёт итератор, который возвращает элементы из *итерируемого объекта* до тех пор, пока *предикат* истинен. Примерно эквивалентно:544545```python546def takewhile(predicate, iterable):547 # takewhile(lambda x: x<5, [1,4,6,3,8]) → 1 4548 for x in iterable:549 if not predicate(x):550 break551 yield x552```553554Обратите внимание: элемент, который первым не удовлетворяет условию предиката, потребляется из входного итератора, и доступа к нему нет. Это может быть проблемой, если приложение хочет продолжить потребление входного итератора после того, как *takewhile* отработал до полного исчерпания. Чтобы обойти эту проблему, рассмотрите возможность использования [more-itertools.before\_and\_after()](https://python-all.ru/3.12/library/itertools.html) вместо этого.555556#### `itertools.tee(iterable, n=2)`557558Возвращает *n* независимых итераторов из одного итерируемого объекта.559560Примерно эквивалентно:561562```python563def tee(iterable, n=2):564 if n < 0:565 raise ValueError566 if n == 0:567 return ()568 iterator = _tee(iterable)569 result = [iterator]570 for _ in range(n - 1):571 result.append(_tee(iterator))572 return tuple(result)573574class _tee:575576 def __init__(self, iterable):577 it = iter(iterable)578 if isinstance(it, _tee):579 self.iterator = it.iterator580 self.link = it.link581 else:582 self.iterator = it583 self.link = [None, None]584585 def __iter__(self):586 return self587588 def __next__(self):589 link = self.link590 if link[1] is None:591 link[0] = next(self.iterator)592 link[1] = [None, None]593 value, self.link = link594 return value595```596597Итераторы `tee` не являются потокобезопасными. Исключение [`RuntimeError`](https://python-all.ru/3.12/library/exceptions.html#RuntimeError) может быть возбуждено при одновременном использовании итераторов, возвращённых одним вызовом [`tee()`](https://python-all.ru/3.12/library/itertools.html#itertools.tee), даже если исходный *итерируемый объект* потокобезопасен.598599Этот инструмент итерации может потребовать значительного вспомогательного хранилища (в зависимости от объёма временных данных, которые необходимо сохранить). В общем случае, если один итератор использует большую часть или все данные до того, как запустится другой итератор, быстрее использовать [`list()`](https://python-all.ru/3.12/library/stdtypes.html#list) вместо [`tee()`](https://python-all.ru/3.12/library/itertools.html#itertools.tee).600601#### `itertools.zip_longest(*iterables, fillvalue=None)`602603Создаёт итератор, который объединяет элементы из каждого *итерируемого объекта*.604605Если итерируемые объекты имеют разную длину, недостающие значения заполняются с помощью *fillvalue*. Если не указан, *fillvalue* по умолчанию равен `None`.606607Итерация продолжается, пока самый длинный итерируемый объект не будет исчерпан.608609Примерно эквивалентно:610611```python612def zip_longest(*iterables, fillvalue=None):613 # zip_longest('ABCD', 'xy', fillvalue='-') → Ax By C- D-614615 iterators = list(map(iter, iterables))616 num_active = len(iterators)617 if not num_active:618 return619620 while True:621 values = []622 for i, iterator in enumerate(iterators):623 try:624 value = next(iterator)625 except StopIteration:626 num_active -= 1627 if not num_active:628 return629 iterators[i] = repeat(fillvalue)630 value = fillvalue631 values.append(value)632 yield tuple(values)633```634635Если один из итерируемых объектов потенциально бесконечен, то функция [`zip_longest()`](https://python-all.ru/3.12/library/itertools.html#itertools.zip_longest) должна быть обёрнута чем-то, что ограничивает количество вызовов (например, [`islice()`](https://python-all.ru/3.12/library/itertools.html#itertools.islice) или [`takewhile()`](https://python-all.ru/3.12/library/itertools.html#itertools.takewhile)).636637## Рецепты itertools638639В этом разделе представлены рецепты для создания расширенного набора инструментов с использованием существующих itertools в качестве строительных блоков.640641Основная цель рецептов itertools – образовательная. Рецепты демонстрируют различные способы мышления об отдельных инструментах – например, что `chain.from_iterable` связано с концепцией уплощения. Рецепты также дают идеи о том, как инструменты можно комбинировать – например, как `starmap()` и `repeat()` могут работать вместе. Рецепты также показывают шаблоны использования itertools с модулями [`operator`](https://python-all.ru/3.12/library/operator.html#module-operator) и [`collections`](https://python-all.ru/3.12/library/collections.html#module-collections), а также со встроенными itertools, такими как `map()`, `filter()`, `reversed()` и `enumerate()`.642643Второстепенная цель рецептов – служить инкубатором. `accumulate()`, `compress()` и `pairwise()` изначально были рецептами. В настоящее время рецепты `sliding_window()`, `iter_index()` и `sieve()` тестируются, чтобы проверить, оправдают ли они себя.644645Практически все эти и многие другие рецепты можно установить из проекта [more-itertools](https://python-all.ru/3.12/library/itertools.html), доступного на Python Package Index:646647```python648python -m pip install more-itertools649```650651Многие рецепты обеспечивают такую же высокую производительность, как и базовый набор инструментов. Превосходная производительность по памяти достигается за счёт обработки элементов по одному, а не загрузки всего итерируемого объекта в память сразу. Объём кода сохраняется небольшим за счёт связывания инструментов в [функциональном стиле](https://python-all.ru/3.12/library/itertools.html). Высокая скорость сохраняется благодаря предпочтению «векторизованных» строительных блоков перед использованием циклов for и [генераторов](https://python-all.ru/3.12/glossary.html#term-generator), которые влекут накладные расходы интерпретатора.652653```python654import collections655import contextlib656import functools657import math658import operator659import random660661def take(n, iterable):662 "Return first n items of the iterable as a list."663 return list(islice(iterable, n))664665def prepend(value, iterable):666 "Prepend a single value in front of an iterable."667 # prepend(1, [2, 3, 4]) → 1 2 3 4668 return chain([value], iterable)669670def tabulate(function, start=0):671 "Return function(0), function(1), ..."672 return map(function, count(start))673674def repeatfunc(func, times=None, *args):675 "Repeat calls to func with specified arguments."676 if times is None:677 return starmap(func, repeat(args))678 return starmap(func, repeat(args, times))679680def flatten(list_of_lists):681 "Flatten one level of nesting."682 return chain.from_iterable(list_of_lists)683684def ncycles(iterable, n):685 "Returns the sequence elements n times."686 return chain.from_iterable(repeat(tuple(iterable), n))687688def loops(n):689 "Loop n times. Like range(n) but without creating integers."690 # for _ in loops(100): ...691 return repeat(None, n)692693def tail(n, iterable):694 "Return an iterator over the last n items."695 # tail(3, 'ABCDEFG') → E F G696 return iter(collections.deque(iterable, maxlen=n))697698def consume(iterator, n=None):699 "Advance the iterator n-steps ahead. If n is None, consume entirely."700 # Используйте функции, потребляющие итераторы на скорости C.701 if n is None:702 collections.deque(iterator, maxlen=0)703 else:704 next(islice(iterator, n, n), None)705706def nth(iterable, n, default=None):707 "Returns the nth item or a default value."708 return next(islice(iterable, n, None), default)709710def quantify(iterable, predicate=bool):711 "Given a predicate that returns True or False, count the True results."712 return sum(map(predicate, iterable))713714def first_true(iterable, default=False, predicate=None):715 "Returns the first true value or the *default* if there is no true value."716 # first_true([a,b,c], x) → a or b or c or x717 # first_true([a,b], x, f) → a if f(a) else b if f(b) else x718 return next(filter(predicate, iterable), default)719720def all_equal(iterable, key=None):721 "Returns True if all the elements are equal to each other."722 # all_equal('4٤௪౪໔', key=int) → True723 return len(take(2, groupby(iterable, key))) <= 1724725def unique_justseen(iterable, key=None):726 "Yield unique elements, preserving order. Remember only the element just seen."727 # unique_justseen('AAAABBBCCDAABBB') → A B C D A B728 # unique_justseen('ABBcCAD', str.casefold) → A B c A D729 if key is None:730 return map(operator.itemgetter(0), groupby(iterable))731 return map(next, map(operator.itemgetter(1), groupby(iterable, key)))732733def unique_everseen(iterable, key=None):734 "Yield unique elements, preserving order. Remember all elements ever seen."735 # unique_everseen('AAAABBBCCDAABBB') → A B C D736 # unique_everseen('ABBcCAD', str.casefold) → A B c D737 seen = set()738 if key is None:739 for element in filterfalse(seen.__contains__, iterable):740 seen.add(element)741 yield element742 else:743 for element in iterable:744 k = key(element)745 if k not in seen:746 seen.add(k)747 yield element748749def unique(iterable, key=None, reverse=False):750 "Yield unique elements in sorted order. Supports unhashable inputs."751 # unique([[1, 2], [3, 4], [1, 2]]) → [1, 2] [3, 4]752 return unique_justseen(sorted(iterable, key=key, reverse=reverse), key=key)753754def sliding_window(iterable, n):755 "Collect data into overlapping fixed-length chunks or blocks."756 # sliding_window('ABCDEFG', 4) → ABCD BCDE CDEF DEFG757 iterator = iter(iterable)758 window = collections.deque(islice(iterator, n - 1), maxlen=n)759 for x in iterator:760 window.append(x)761 yield tuple(window)762763def grouper(iterable, n, *, incomplete='fill', fillvalue=None):764 "Collect data into non-overlapping fixed-length chunks or blocks."765 # grouper('ABCDEFG', 3, fillvalue='x') → ABC DEF Gxx766 # grouper('ABCDEFG', 3, incomplete='strict') → ABC DEF ValueError767 # grouper('ABCDEFG', 3, incomplete='ignore') → ABC DEF768 iterators = [iter(iterable)] * n769 match incomplete:770 case 'fill':771 return zip_longest(*iterators, fillvalue=fillvalue)772 case 'strict':773 return zip(*iterators, strict=True)774 case 'ignore':775 return zip(*iterators)776 case _:777 raise ValueError('Expected fill, strict, or ignore')778779def roundrobin(*iterables):780 "Visit input iterables in a cycle until each is exhausted."781 # roundrobin('ABC', 'D', 'EF') → A D E B F C782 # Алгоритм Джорджа Саккиса783 iterators = map(iter, iterables)784 for num_active in range(len(iterables), 0, -1):785 iterators = cycle(islice(iterators, num_active))786 yield from map(next, iterators)787788def partition(predicate, iterable):789 """Разделяет элементы на ложные и истинные.790791 Если *предикат* работает медленно, попробуйте обернуть его в functools.lru_cache().792 """793 # partition(is_odd, range(10)) → 0 2 4 6 8 and 1 3 5 7 9794 t1, t2 = tee(iterable)795 return filterfalse(predicate, t1), filter(predicate, t2)796797def subslices(seq):798 "Return all contiguous non-empty subslices of a sequence."799 # subslices('ABCD') → A AB ABC ABCD B BC BCD C CD D800 slices = starmap(slice, combinations(range(len(seq) + 1), 2))801 return map(operator.getitem, repeat(seq), slices)802803def iter_index(iterable, value, start=0, stop=None):804 "Return indices where a value occurs in a sequence or iterable."805 # iter_index('AABCADEAF', 'A') → 0 1 4 7806 seq_index = getattr(iterable, 'index', None)807 if seq_index is None:808 iterator = islice(iterable, start, stop)809 for i, element in enumerate(iterator, start):810 if element is value or element == value:811 yield i812 else:813 stop = len(iterable) if stop is None else stop814 i = start815 with contextlib.suppress(ValueError):816 while True:817 yield (i := seq_index(value, i, stop))818 i += 1819820def iter_except(func, exception, first=None):821 "Convert a call-until-exception interface to an iterator interface."822 # iter_except(d.popitem, KeyError) → неблокирующий итератор словаря823 with contextlib.suppress(exception):824 if first is not None:825 yield first()826 while True:827 yield func()828```829830Следующие рецепты имеют более математическую направленность:831832```python833def powerset(iterable):834 "powerset([1,2,3]) → () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"835 s = list(iterable)836 return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))837838def sum_of_squares(iterable):839 "Add up the squares of the input values."840 # sum_of_squares([10, 20, 30]) → 1400841 return math.sumprod(*tee(iterable))842843def reshape(matrix, cols):844 "Reshape a 2-D matrix to have a given number of columns."845 # reshape([(0, 1), (2, 3), (4, 5)], 3) → (0, 1, 2), (3, 4, 5)846 return batched(chain.from_iterable(matrix), cols)847848def transpose(matrix):849 "Swap the rows and columns of a 2-D matrix."850 # transpose([(1, 2, 3), (11, 22, 33)]) → (1, 11) (2, 22) (3, 33)851 return zip(*matrix, strict=True)852853def matmul(m1, m2):854 "Multiply two matrices."855 # matmul([(7, 5), (3, 5)], [(2, 5), (7, 9)]) → (49, 80), (41, 60)856 n = len(m2[0])857 return batched(starmap(math.sumprod, product(m1, transpose(m2))), n)858859def convolve(signal, kernel):860 """Дискретная линейная свёртка двух итерируемых объектов.861 Эквивалентно умножению многочленов.862863 Свёртки математически коммутативны; однако входные данные864 вычисляются по-разному. Сигнал потребляется лениво и может быть865 бесконечным. Ядро полностью потребляется до начала вычислений.866867 Статья: https://betterexplained.com/articles/intuitive-convolution/868 Видео: https://www.youtube.com/watch?v=KuXjwB4LzSA869 """870 # convolve([1, -1, -20], [1, -3]) → 1 -4 -17 60871 # convolve(data, [0.25, 0.25, 0.25, 0.25]) → Скользящее среднее (размытие)872 # convolve(data, [1/2, 0, -1/2]) → Оценка первой производной873 # convolve(data, [1, -2, 1]) → Оценка второй производной874 kernel = tuple(kernel)[::-1]875 n = len(kernel)876 padded_signal = chain(repeat(0, n-1), signal, repeat(0, n-1))877 windowed_signal = sliding_window(padded_signal, n)878 return map(math.sumprod, repeat(kernel), windowed_signal)879880def polynomial_from_roots(roots):881 """Вычисляет коэффициенты многочлена по его корням.882883 (x - 5) (x + 4) (x - 3) раскрывается в: x³ -4x² -17x + 60884 """885 # polynomial_from_roots([5, -4, 3]) → [1, -4, -17, 60]886 factors = zip(repeat(1), map(operator.neg, roots))887 return list(functools.reduce(convolve, factors, [1]))888889def polynomial_eval(coefficients, x):890 """Вычисляет значение многочлена в заданной точке.891892 Вычисляет с лучшей численной устойчивостью, чем метод Горнера.893 """894 # Вычислить x³ -4x² -17x + 60 при x = 5895 # polynomial_eval([1, -4, -17, 60], x=5) → 0896 n = len(coefficients)897 if not n:898 return type(x)(0)899 powers = map(pow, repeat(x), reversed(range(n)))900 return math.sumprod(coefficients, powers)901902def polynomial_derivative(coefficients):903 """Вычисляет первую производную многочлена.904905 f(x) = x³ -4x² -17x + 60906 f'(x) = 3x² -8x -17907 """908 # polynomial_derivative([1, -4, -17, 60]) → [3, -8, -17]909 n = len(coefficients)910 powers = reversed(range(1, n))911 return list(map(operator.mul, coefficients, powers))912913def sieve(n):914 "Primes less than n."915 # sieve(30) → 2 3 5 7 11 13 17 19 23 29916 if n > 2:917 yield 2918 data = bytearray((0, 1)) * (n // 2)919 for p in iter_index(data, 1, start=3, stop=math.isqrt(n) + 1):920 data[p*p : n : p+p] = bytes(len(range(p*p, n, p+p)))921 yield from iter_index(data, 1, start=3)922923def is_prime(n):924 "Return True if n is prime."925 # is_prime(1_000_000_000_000_403) → True926 return n > 1 and all(n % p for p in sieve(math.isqrt(n) + 1))927928def factor(n):929 "Prime factors of n."930 # factor(99) → 3 3 11931 # factor(1_000_000_000_000_007) → 47 59 360620266859932 # factor(1_000_000_000_000_403) → 1000000000000403933 for prime in sieve(math.isqrt(n) + 1):934 while not n % prime:935 yield prime936 n //= prime937 if n == 1:938 return939 if n > 1:940 yield n941942def totient(n):943 "Count of natural numbers up to n that are coprime to n."944 # https://mathworld.wolfram.com/TotientFunction.html945 # totient(12) → 4 потому что len([1, 5, 7, 11]) == 4946 for prime in set(factor(n)):947 n -= n // prime948 return n949950def multinomial(*counts):951 "Number of distinct arrangements of a multiset."952 # Counter('abracadabra').values() -> 5 2 1 1 2953 # multinomial(5, 2, 1, 1, 2) → 83160954 return math.prod(map(math.comb, accumulate(counts), counts))955```956