itertools.md
1> **Источник:** https://python-all.ru/3.9/library/itertools.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# [`itertools`](https://python-all.ru/3.9/library/itertools.html#module-itertools) – Функции, создающие итераторы для эффективного перебора89---1011Этот модуль реализует ряд строительных блоков [итераторов](https://python-all.ru/3.9/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.9/library/functions.html#map) и [`count()`](https://python-all.ru/3.9/library/itertools.html#itertools.count) для получения `map(f, count())`.1617Эти инструменты и их встроенные аналоги также хорошо работают с высокоскоростными функциями из модуля [`operator`](https://python-all.ru/3.9/library/operator.html#module-operator). Например, оператор умножения можно применить к двум векторам, чтобы получить эффективное скалярное произведение: `sum(map(operator.mul, vector1, vector2))`.1819**Бесконечные итераторы:**2021| Итератор | Аргументы | Результаты | Пример |22| --- | --- | --- | --- |23| [`count()`](https://python-all.ru/3.9/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.9/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.9/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.9/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.9/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.9/library/itertools.html#itertools.chain.from_iterable) | итерируемый объект | p0, p1, … plast, q0, q1, … | `chain.from_iterable(['ABC', 'DEF']) --> A B C D E F` |34| [`compress()`](https://python-all.ru/3.9/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.9/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.9/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.9/library/itertools.html#itertools.groupby) | iterable\[, key\] | подитераторы, сгруппированные по значению key(v) | |38| [`islice()`](https://python-all.ru/3.9/library/itertools.html#itertools.islice) | seq, \[start,\] stop \[, step\] | элементы из seq\[start:stop:step\] | `islice('ABCDEFG', 2, None) --> C D E F G` |39| [`starmap()`](https://python-all.ru/3.9/library/itertools.html#itertools.starmap) | func, seq | func(\*seq\[0\]), func(\*seq\[1\]), … | `starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000` |40| [`takewhile()`](https://python-all.ru/3.9/library/itertools.html#itertools.takewhile) | pred, seq | seq\[0\], seq\[1\], пока pred не вернёт ложь | `takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4` |41| [`tee()`](https://python-all.ru/3.9/library/itertools.html#itertools.tee) | it, n | it1, it2, … itn разделяет один итератор на n | |42| [`zip_longest()`](https://python-all.ru/3.9/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-` |4344**Комбинаторные итераторы:**4546| Итератор | Аргументы | Результаты |47| --- | --- | --- |48| [`product()`](https://python-all.ru/3.9/library/itertools.html#itertools.product) | p, q, … \[repeat=1\] | декартово произведение, эквивалентно вложенному циклу for |49| [`permutations()`](https://python-all.ru/3.9/library/itertools.html#itertools.permutations) | p\[, r\] | кортежи длиной r, все возможные перестановки, без повторяющихся элементов |50| [`combinations()`](https://python-all.ru/3.9/library/itertools.html#itertools.combinations) | p, r | кортежи длиной r, в отсортированном порядке, без повторяющихся элементов |51| [`combinations_with_replacement()`](https://python-all.ru/3.9/library/itertools.html#itertools.combinations_with_replacement) | p, r | кортежи длиной r, в отсортированном порядке, с повторяющимися элементами |5253| Примеры | Результаты |54| --- | --- |55| `product('ABCD', repeat=2)` | `AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD` |56| `permutations('ABCD', 2)` | `AB AC AD BA BC BD CA CB CD DA DB DC` |57| `combinations('ABCD', 2)` | `AB AC AD BC BD CD` |58| `combinations_with_replacement('ABCD', 2)` | `AA AB AC AD BB BC BD CC CD DD` |5960## Функции итераторных инструментов6162Следующие функции модуля создают и возвращают итераторы. Некоторые из них порождают потоки бесконечной длины, поэтому обращаться к ним следует только с помощью функций или циклов, которые обрывают поток.6364#### `itertools.accumulate(iterable[, func, *, initial=None])`6566Создаёт итератор, возвращающий накопленные суммы или накопленные результаты других бинарных функций (задаваемых через необязательный аргумент *func*).6768Если передан аргумент *func*, он должен быть функцией двух аргументов. Элементы входного *iterable* могут быть любого типа, который может быть принят как аргумент *func*. (Например, при операции сложения по умолчанию элементы могут быть любого суммируемого типа, включая [`Decimal`](https://python-all.ru/3.9/library/decimal.html#decimal.Decimal) или [`Fraction`](https://python-all.ru/3.9/library/fractions.html#fractions.Fraction).)6970Обычно количество элементов вывода соответствует входному итерабельному объекту. Однако если указан именованный аргумент *initial*, накопление начинается со значения *initial*, так что в выводе оказывается на один элемент больше, чем во входном итерабельном объекте.7172Примерно эквивалентно:7374```python75def accumulate(iterable, func=operator.add, *, initial=None):76 'Return running totals'77 # accumulate([1,2,3,4,5]) --> 1 3 6 10 1578 # accumulate([1,2,3,4,5], initial=100) --> 100 101 103 106 110 11579 # accumulate([1,2,3,4,5], operator.mul) --> 1 2 6 24 12080 it = iter(iterable)81 total = initial82 if initial is None:83 try:84 total = next(it)85 except StopIteration:86 return87 yield total88 for element in it:89 total = func(total, element)90 yield total91```9293У аргумента *func* есть несколько применений. Его можно установить в [`min()`](https://python-all.ru/3.9/library/functions.html#min) для текущего минимума, [`max()`](https://python-all.ru/3.9/library/functions.html#max) для текущего максимума или [`operator.mul()`](https://python-all.ru/3.9/library/operator.html#operator.mul) для текущего произведения. Таблицы амортизации можно построить, накапливая проценты и применяя платежи. [Рекуррентные соотношения](https://python-all.ru/3.9/library/itertools.html) первого порядка можно смоделировать, передав начальное значение в итерируемом объекте и используя только накопленную сумму в аргументе *func*:9495```python96>>> data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8]97>>> list(accumulate(data, operator.mul)) # текущее произведение98[3, 12, 72, 144, 144, 1296, 0, 0, 0, 0]99>>> list(accumulate(data, max)) # текущий максимум100[3, 4, 6, 6, 6, 9, 9, 9, 9, 9]101102# Amortize a 5% loan of 1000 with 4 annual payments of 90103>>> cashflows = [1000, -90, -90, -90, -90]104>>> list(accumulate(cashflows, lambda bal, pmt: bal*1.05 + pmt))105[1000, 960.0, 918.0, 873.9000000000001, 827.5950000000001]106107# Chaotic recurrence relation https://en.wikipedia.org/wiki/Logistic_map108>>> logistic_map = lambda x, _: r * x * (1 - x)109>>> r = 3.8110>>> x0 = 0.4111>>> inputs = repeat(x0, 36) # используется только начальное значение112>>> [format(x, '.2f') for x in accumulate(inputs, logistic_map)]113['0.40', '0.91', '0.30', '0.81', '0.60', '0.92', '0.29', '0.79', '0.63',114 '0.88', '0.39', '0.90', '0.33', '0.84', '0.52', '0.95', '0.18', '0.57',115 '0.93', '0.25', '0.71', '0.79', '0.63', '0.88', '0.39', '0.91', '0.32',116 '0.83', '0.54', '0.95', '0.20', '0.60', '0.91', '0.30', '0.80', '0.60']117```118119См. [`functools.reduce()`](https://python-all.ru/3.9/library/functools.html#functools.reduce) – похожая функция, возвращающая только итоговое накопленное значение.120121Новое в версии 3.2.122123Изменено в версии 3.3: Добавлен необязательный параметр *func*.124125Изменено в версии 3.8: Добавлен необязательный параметр *initial*.126127#### `itertools.chain(*iterables)`128129Создаёт итератор, который возвращает элементы из первого итерируемого объекта, пока он не будет исчерпан, затем переходит к следующему, пока все итерируемые объекты не будут исчерпаны. Используется для объединения последовательностей в одну. Приблизительный эквивалент:130131```python132def chain(*iterables):133 # chain('ABC', 'DEF') --> A B C D E F134 for it in iterables:135 for element in it:136 yield element137```138139#### `classmethod chain.from_iterable(iterable)`140141Альтернативный конструктор для [`chain()`](https://python-all.ru/3.9/library/itertools.html#itertools.chain). Получает цепочку входных данных из одного аргумента iterable, который вычисляется лениво. Примерная реализация:142143```python144def from_iterable(iterables):145 # chain.from_iterable(['ABC', 'DEF']) --> A B C D E F146 for it in iterables:147 for element in it:148 yield element149```150151#### `itertools.combinations(iterable, r)`152153Возвращает подпоследовательности элементов длины *r* из входного *iterable*.154155Кортежи комбинаций порождаются в лексикографическом порядке в соответствии с порядком входного *итерируемого объекта*. Таким образом, если входной *итерируемый объект* отсортирован, то и кортежи комбинаций будут созданы в отсортированном порядке.156157Элементы считаются уникальными на основе их позиции, а не значения. Поэтому если входные элементы уникальны, то в каждой комбинации не будет повторяющихся значений.158159Примерно эквивалентно:160161```python162def combinations(iterable, r):163 # combinations('ABCD', 2) --> AB AC AD BC BD CD164 # combinations(range(4), 3) --> 012 013 023 123165 pool = tuple(iterable)166 n = len(pool)167 if r > n:168 return169 indices = list(range(r))170 yield tuple(pool[i] for i in indices)171 while True:172 for i in reversed(range(r)):173 if indices[i] != i + n - r:174 break175 else:176 return177 indices[i] += 1178 for j in range(i+1, r):179 indices[j] = indices[j-1] + 1180 yield tuple(pool[i] for i in indices)181```182183Код для [`combinations()`](https://python-all.ru/3.9/library/itertools.html#itertools.combinations) можно также выразить как подпоследовательность [`permutations()`](https://python-all.ru/3.9/library/itertools.html#itertools.permutations) после фильтрации записей, где элементы не находятся в отсортированном порядке (согласно их позиции во входном пуле):184185```python186def combinations(iterable, r):187 pool = tuple(iterable)188 n = len(pool)189 for indices in permutations(range(n), r):190 if sorted(indices) == list(indices):191 yield tuple(pool[i] for i in indices)192```193194Количество возвращаемых элементов равно `n! / r! / (n-r)!`, когда `0 <= r <= n`, или нулю, когда `r > n`.195196#### `itertools.combinations_with_replacement(iterable, r)`197198Возвращает подпоследовательности элементов длины *r* из входного *iterable*, допуская повторение отдельных элементов.199200Кортежи комбинаций порождаются в лексикографическом порядке в соответствии с порядком входного *итерируемого объекта*. Таким образом, если входной *итерируемый объект* отсортирован, то и кортежи комбинаций будут созданы в отсортированном порядке.201202Элементы считаются уникальными по их позиции, а не по значению. Поэтому если входные элементы уникальны, сгенерированные комбинации также будут уникальны.203204Примерно эквивалентно:205206```python207def combinations_with_replacement(iterable, r):208 # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC209 pool = tuple(iterable)210 n = len(pool)211 if not n and r:212 return213 indices = [0] * r214 yield tuple(pool[i] for i in indices)215 while True:216 for i in reversed(range(r)):217 if indices[i] != n - 1:218 break219 else:220 return221 indices[i:] = [indices[i] + 1] * (r - i)222 yield tuple(pool[i] for i in indices)223```224225Код для [`combinations_with_replacement()`](https://python-all.ru/3.9/library/itertools.html#itertools.combinations_with_replacement) можно также выразить как подпоследовательность [`product()`](https://python-all.ru/3.9/library/itertools.html#itertools.product) после фильтрации записей, где элементы не находятся в отсортированном порядке (согласно их позиции во входном пуле):226227```python228def combinations_with_replacement(iterable, r):229 pool = tuple(iterable)230 n = len(pool)231 for indices in product(range(n), repeat=r):232 if sorted(indices) == list(indices):233 yield tuple(pool[i] for i in indices)234```235236Количество возвращаемых элементов равно `(n+r-1)! / r! / (n-1)!`, когда `n > 0`.237238Новое в версии 3.1.239240#### `itertools.compress(data, selectors)`241242Создаёт итератор, который фильтрует элементы из *data*, возвращая только те, для которых в *selectors* есть соответствующий элемент, вычисляемый как `True`. Останавливается, когда исчерпан либо итерабельный объект *data*, либо *selectors*. Примерно эквивалентен:243244```python245def compress(data, selectors):246 # compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F247 return (d for d, s in zip(data, selectors) if s)248```249250Новое в версии 3.1.251252#### `itertools.count(start=0, step=1)`253254Создаёт итератор, возвращающий равномерно распределённые значения, начиная с числа *start*. Часто используется как аргумент для [`map()`](https://python-all.ru/3.9/library/functions.html#map) для генерации последовательных точек данных. Также используется с [`zip()`](https://python-all.ru/3.9/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Создаёт итератор, возвращающий элементы из итерабельного объекта и сохраняющий копию каждого. Когда итерабельный объект исчерпан, возвращает элементы из сохранённой копии. Повторяется бесконечно. Примерно эквивалентен: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Примечание: этот элемент набора инструментов может потребовать значительного дополнительного хранилища (в зависимости от длины итерабельного объекта).287288#### `itertools.dropwhile(predicate, iterable)`289290Создаёт итератор, который отбрасывает элементы из итерабельного объекта, пока предикат истинен; после этого возвращает каждый элемент. Примечание: итератор не выдаёт *никакого* вывода, пока предикат впервые не станет ложным, поэтому время запуска может быть большим. Примерно эквивалентен:291292```python293def dropwhile(predicate, iterable):294 # dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1295 iterable = iter(iterable)296 for x in iterable:297 if not predicate(x):298 yield x299 break300 for x in iterable:301 yield x302```303304#### `itertools.filterfalse(predicate, iterable)`305306Создаёт итератор, который фильтрует элементы из итерируемого объекта, возвращая только те, для которых предикат равен `False`. Если *предикат* равен `None`, возвращает элементы, которые являются ложными. Примерно эквивалентно:307308```python309def filterfalse(predicate, iterable):310 # filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8311 if predicate is None:312 predicate = bool313 for x in iterable:314 if not predicate(x):315 yield x316```317318#### `itertools.groupby(iterable, key=None)`319320Make 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.321322Работа [`groupby()`](https://python-all.ru/3.9/library/itertools.html#itertools.groupby) аналогична фильтру `uniq` в Unix. Она создает разрыв или новую группу каждый раз, когда изменяется значение ключевой функции (поэтому обычно необходимо отсортировать данные с помощью той же ключевой функции). Такое поведение отличается от SQL GROUP BY, которая объединяет общие элементы независимо от порядка их ввода.323324Возвращаемая группа сама является итератором, который использует общий исходный итерируемый объект с [`groupby()`](https://python-all.ru/3.9/library/itertools.html#itertools.groupby). Поскольку источник общий, при продвижении объекта [`groupby()`](https://python-all.ru/3.9/library/itertools.html#itertools.groupby) предыдущая группа перестает быть видимой. Поэтому, если эти данные понадобятся позже, их следует сохранить в виде списка:325326```python327groups = []328uniquekeys = []329data = sorted(data, key=keyfunc)330for k, g in groupby(data, keyfunc):331 groups.append(list(g)) # Сохранить групповой итератор как список332 uniquekeys.append(k)333```334335[`groupby()`](https://python-all.ru/3.9/library/itertools.html#itertools.groupby) примерно эквивалентно:336337```python338class groupby:339 # [k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B340 # [list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D341 def __init__(self, iterable, key=None):342 if key is None:343 key = lambda x: x344 self.keyfunc = key345 self.it = iter(iterable)346 self.tgtkey = self.currkey = self.currvalue = object()347 def __iter__(self):348 return self349 def __next__(self):350 self.id = object()351 while self.currkey == self.tgtkey:352 self.currvalue = next(self.it) # Выход при StopIteration353 self.currkey = self.keyfunc(self.currvalue)354 self.tgtkey = self.currkey355 return (self.currkey, self._grouper(self.tgtkey, self.id))356 def _grouper(self, tgtkey, id):357 while self.id is id and self.currkey == tgtkey:358 yield self.currvalue359 try:360 self.currvalue = next(self.it)361 except StopIteration:362 return363 self.currkey = self.keyfunc(self.currvalue)364```365366#### `itertools.islice(iterable, stop)`367368#### `itertools.islice(iterable, start, stop[, step])`369370Создаёт итератор, который возвращает выбранные элементы из итерируемого объекта. Если *start* не равен нулю, то элементы из итерируемого объекта пропускаются до достижения start. Затем элементы возвращаются последовательно, если только *step* не установлен больше единицы, что приводит к пропуску элементов. Если *stop* равен `None`, то итерация продолжается до тех пор, пока итератор не будет исчерпан, если вообще; в противном случае она останавливается на указанной позиции. В отличие от обычной срезки, [`islice()`](https://python-all.ru/3.9/library/itertools.html#itertools.islice) не поддерживает отрицательные значения для *start*, *stop* или *step*. Может использоваться для извлечения связанных полей из данных, где внутренняя структура была уплощена (например, многострочный отчёт может содержать поле имени на каждой третьей строке). Примерно эквивалентно: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Если *start* равен `None`, то итерация начинается с нуля. Если *step* равен `None`, то шаг по умолчанию равен единице.400401#### `itertools.permutations(iterable, r=None)`402403Возвращает последовательные перестановки длины *r* элементов из *iterable*.404405Если *r* не указан или равен `None`, то *r* по умолчанию равен длине *iterable* и генерируются все возможные перестановки полной длины.406407Кортежи перестановок порождаются в лексикографическом порядке в соответствии с порядком входного *итерируемого объекта*. Таким образом, если входной *итерируемый объект* отсортирован, то и кортежи комбинаций будут созданы в отсортированном порядке.408409Элементы считаются уникальными на основе их позиции, а не значения. Поэтому если входные элементы уникальны, то в каждой перестановке не будет повторяющихся значений.410411Примерно эквивалентно:412413```python414def permutations(iterable, r=None):415 # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC416 # permutations(range(3)) --> 012 021 102 120 201 210417 pool = tuple(iterable)418 n = len(pool)419 r = n if r is None else r420 if r > n:421 return422 indices = list(range(n))423 cycles = list(range(n, n-r, -1))424 yield tuple(pool[i] for i in indices[:r])425 while n:426 for i in reversed(range(r)):427 cycles[i] -= 1428 if cycles[i] == 0:429 indices[i:] = indices[i+1:] + indices[i:i+1]430 cycles[i] = n - i431 else:432 j = cycles[i]433 indices[i], indices[-j] = indices[-j], indices[i]434 yield tuple(pool[i] for i in indices[:r])435 break436 else:437 return438```439440Код для [`permutations()`](https://python-all.ru/3.9/library/itertools.html#itertools.permutations) также можно выразить как подпоследовательность [`product()`](https://python-all.ru/3.9/library/itertools.html#itertools.product), отфильтрованную для исключения записей с повторяющимися элементами (тех, которые находятся на одной и той же позиции во входном пуле):441442```python443def permutations(iterable, r=None):444 pool = tuple(iterable)445 n = len(pool)446 r = n if r is None else r447 for indices in product(range(n), repeat=r):448 if len(set(indices)) == r:449 yield tuple(pool[i] for i in indices)450```451452Количество возвращаемых элементов равно `n! / (n-r)!`, когда `0 <= r <= n`, или нулю, когда `r > n`.453454#### `itertools.product(*iterables, repeat=1)`455456Декартово произведение входных итерируемых объектов.457458Примерно эквивалентно вложенным циклам for в генераторном выражении. Например, `product(A, B)` возвращает то же, что и `((x,y) for x in A for y in B)`.459460Вложенные циклы работают как одометр: самый правый элемент увеличивается на каждой итерации. Этот шаблон создает лексикографический порядок, так что если входные итерируемые объекты отсортированы, кортежи произведения выдаются в отсортированном порядке.461462Чтобы вычислить произведение итерируемого объекта на самого себя, укажите количество повторений с помощью необязательного именованного аргумента *repeat*. Например, `product(A, repeat=4)` эквивалентно `product(A, A, A, A)`.463464Эта функция примерно эквивалентна следующему коду, за исключением того, что реальная реализация не накапливает промежуточные результаты в памяти:465466```python467def product(*args, repeat=1):468 # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy469 # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111470 pools = [tuple(pool) for pool in args] * repeat471 result = [[]]472 for pool in pools:473 result = [x+[y] for x in result for y in pool]474 for prod in result:475 yield tuple(prod)476```477478Перед запуском [`product()`](https://python-all.ru/3.9/library/itertools.html#itertools.product) полностью потребляет входные итерируемые объекты, сохраняя пулы значений в памяти для генерации произведений. Соответственно, она полезна только для конечных входных данных.479480#### `itertools.repeat(object[, times])`481482Создаёт итератор, который снова и снова возвращает *object*. Выполняется бесконечно, если не указан аргумент *times*. Используется как аргумент [`map()`](https://python-all.ru/3.9/library/functions.html#map) для инвариантных параметров вызываемой функции. Также используется с [`zip()`](https://python-all.ru/3.9/library/functions.html#zip) для создания инвариантной части кортежной записи.483484Примерно эквивалентно:485486```python487def repeat(object, times=None):488 # repeat(10, 3) --> 10 10 10489 if times is None:490 while True:491 yield object492 else:493 for i in range(times):494 yield object495```496497Обычное применение *repeat* – передача потока постоянных значений в *map* или *zip*:498499```python500>>> list(map(pow, range(10), repeat(2)))501[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]502```503504#### `itertools.starmap(function, iterable)`505506Создаёт итератор, который вычисляет функцию, используя аргументы, полученные из итерируемого объекта. Используется вместо [`map()`](https://python-all.ru/3.9/library/functions.html#map), когда параметры аргументов уже сгруппированы в кортежи из одного итерируемого объекта (данные были «предварительно сжаты»). Разница между [`map()`](https://python-all.ru/3.9/library/functions.html#map) и [`starmap()`](https://python-all.ru/3.9/library/itertools.html#itertools.starmap) параллельна различию между `function(a,b)` и `function(*c)`. Примерно эквивалентно:507508```python509def starmap(function, iterable):510 # starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000511 for args in iterable:512 yield function(*args)513```514515#### `itertools.takewhile(predicate, iterable)`516517Создаёт итератор, возвращающий элементы из итерируемого объекта, пока предикат истинен. Приблизительно эквивалентно:518519```python520def takewhile(predicate, iterable):521 # takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4522 for x in iterable:523 if predicate(x):524 yield x525 else:526 break527```528529#### `itertools.tee(iterable, n=2)`530531Возвращает *n* независимых итераторов из одного итерируемого объекта.532533Следующий код на Python помогает объяснить, что делает *tee* (хотя реальная реализация более сложна и использует только одну базовую очередь FIFO).534535Примерно эквивалентно:536537```python538def tee(iterable, n=2):539 it = iter(iterable)540 deques = [collections.deque() for i in range(n)]541 def gen(mydeque):542 while True:543 if not mydeque: # когда локальная deque пуста544 try:545 newval = next(it) # извлечь новое значение и546 except StopIteration:547 return548 for d in deques: # загрузить его во все двусторонние очереди549 d.append(newval)550 yield mydeque.popleft()551 return tuple(gen(d) for d in deques)552```553554После того как [`tee()`](https://python-all.ru/3.9/library/itertools.html#itertools.tee) выполнил разделение, исходный *итерируемый объект* не следует использовать где-либо ещё; в противном случае *итерируемый объект* может продвинуться без уведомления объектов tee.555556Итераторы `tee` не являются потокобезопасными. [`RuntimeError`](https://python-all.ru/3.9/library/exceptions.html#RuntimeError) может быть возбуждён при одновременном использовании итераторов, возвращённых одним и тем же вызовом [`tee()`](https://python-all.ru/3.9/library/itertools.html#itertools.tee), даже если исходный *iterable* является потокобезопасным.557558Этот инструмент итерации может потребовать значительного вспомогательного хранилища (в зависимости от объёма временных данных, которые необходимо сохранить). В общем случае, если один итератор использует большую часть или все данные до того, как запустится другой итератор, быстрее использовать [`list()`](https://python-all.ru/3.9/library/stdtypes.html#list) вместо [`tee()`](https://python-all.ru/3.9/library/itertools.html#itertools.tee).559560#### `itertools.zip_longest(*iterables, fillvalue=None)`561562Создаёт итератор, который агрегирует элементы из каждого из итерируемых объектов. Если итерируемые объекты имеют разную длину, недостающие значения заполняются с помощью *fillvalue*. Итерация продолжается до тех пор, пока самый длинный итерируемый объект не будет исчерпан. Приблизительно эквивалентно:563564```python565def zip_longest(*args, fillvalue=None):566 # zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-567 iterators = [iter(it) for it in args]568 num_active = len(iterators)569 if not num_active:570 return571 while True:572 values = []573 for i, it in enumerate(iterators):574 try:575 value = next(it)576 except StopIteration:577 num_active -= 1578 if not num_active:579 return580 iterators[i] = repeat(fillvalue)581 value = fillvalue582 values.append(value)583 yield tuple(values)584```585586Если один из итерируемых объектов потенциально бесконечен, то функцию [`zip_longest()`](https://python-all.ru/3.9/library/itertools.html#itertools.zip_longest) следует обернуть чем-то, что ограничивает количество вызовов (например, [`islice()`](https://python-all.ru/3.9/library/itertools.html#itertools.islice) или [`takewhile()`](https://python-all.ru/3.9/library/itertools.html#itertools.takewhile)). Если не указано, *fillvalue* по умолчанию равен `None`.587588## Рецепты itertools589590В этом разделе представлены рецепты для создания расширенного набора инструментов с использованием существующих itertools в качестве строительных блоков.591592Практически все эти рецепты и многие-многие другие можно установить из проекта [more-itertools](https://python-all.ru/3.9/library/itertools.html), который находится в Python Package Index:593594```python595pip install more-itertools596```597598Расширенные инструменты обеспечивают такую же высокую производительность, как и базовый набор инструментов. Превосходная производительность по памяти достигается за счёт обработки элементов по одному, а не загрузки всего итерируемого объекта в память сразу. Объём кода остаётся небольшим благодаря связыванию инструментов в функциональном стиле, что помогает избавиться от временных переменных. Высокая скорость сохраняется за счёт предпочтения «векторизованных» строительных блоков вместо использования циклов for и [генераторов](https://python-all.ru/3.9/glossary.html#term-generator), которые создают накладные расходы интерпретатора.599600```python601def take(n, iterable):602 "Return first n items of the iterable as a list"603 return list(islice(iterable, n))604605def prepend(value, iterator):606 "Prepend a single value in front of an iterator"607 # prepend(1, [2, 3, 4]) -> 1 2 3 4608 return chain([value], iterator)609610def tabulate(function, start=0):611 "Return function(0), function(1), ..."612 return map(function, count(start))613614def tail(n, iterable):615 "Return an iterator over the last n items"616 # tail(3, 'ABCDEFG') --> E F G617 return iter(collections.deque(iterable, maxlen=n))618619def consume(iterator, n=None):620 "Advance the iterator n-steps ahead. If n is None, consume entirely."621 # Используйте функции, потребляющие итераторы на скорости C.622 if n is None:623 # передать весь итератор в deque нулевой длины624 collections.deque(iterator, maxlen=0)625 else:626 # перейти к пустому срезу начиная с позиции n627 next(islice(iterator, n, n), None)628629def nth(iterable, n, default=None):630 "Returns the nth item or a default value"631 return next(islice(iterable, n, None), default)632633def all_equal(iterable):634 "Returns True if all the elements are equal to each other"635 g = groupby(iterable)636 return next(g, True) and not next(g, False)637638def quantify(iterable, pred=bool):639 "Count how many times the predicate is true"640 return sum(map(pred, iterable))641642def pad_none(iterable):643 """Возвращает элементы последовательности, а затем бесконечно возвращает None.644645 Полезно для эмуляции поведения встроенной функции map().646 """647 return chain(iterable, repeat(None))648649def ncycles(iterable, n):650 "Returns the sequence elements n times"651 return chain.from_iterable(repeat(tuple(iterable), n))652653def dotproduct(vec1, vec2):654 return sum(map(operator.mul, vec1, vec2))655656def convolve(signal, kernel):657 # См.: https://betterexplained.com/articles/intuitive-convolution/658 # convolve(data, [0.25, 0.25, 0.25, 0.25]) --> Скользящее среднее (размытие)659 # convolve(data, [1, -1]) --> Первая конечная разность (первая производная)660 # convolve(data, [1, -2, 1]) --> Вторая конечная разность (вторая производная)661 kernel = tuple(kernel)[::-1]662 n = len(kernel)663 window = collections.deque([0], maxlen=n) * n664 for x in chain(signal, repeat(0, n-1)):665 window.append(x)666 yield sum(map(operator.mul, kernel, window))667668def flatten(list_of_lists):669 "Flatten one level of nesting"670 return chain.from_iterable(list_of_lists)671672def repeatfunc(func, times=None, *args):673 """Повторяет вызовы func с указанными аргументами.674675 Пример: repeatfunc(random.random)676 """677 if times is None:678 return starmap(func, repeat(args))679 return starmap(func, repeat(args, times))680681def pairwise(iterable):682 "s -> (s0,s1), (s1,s2), (s2, s3), ..."683 a, b = tee(iterable)684 next(b, None)685 return zip(a, b)686687def grouper(iterable, n, fillvalue=None):688 "Collect data into fixed-length chunks or blocks"689 # grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx"690 args = [iter(iterable)] * n691 return zip_longest(*args, fillvalue=fillvalue)692693def roundrobin(*iterables):694 "roundrobin('ABC', 'D', 'EF') --> A D E B F C"695 # Автор рецепта – Джордж Саккис696 num_active = len(iterables)697 nexts = cycle(iter(it).__next__ for it in iterables)698 while num_active:699 try:700 for next in nexts:701 yield next()702 except StopIteration:703 # Удалить из цикла только что исчерпанный итератор.704 num_active -= 1705 nexts = cycle(islice(nexts, num_active))706707def partition(pred, iterable):708 "Use a predicate to partition entries into false entries and true entries"709 # partition(is_odd, range(10)) --> 0 2 4 6 8 and 1 3 5 7 9710 t1, t2 = tee(iterable)711 return filterfalse(pred, t1), filter(pred, t2)712713def powerset(iterable):714 "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"715 s = list(iterable)716 return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))717718def unique_everseen(iterable, key=None):719 "List unique elements, preserving order. Remember all elements ever seen."720 # unique_everseen('AAAABBBCCDAABBB') --> A B C D721 # unique_everseen('ABBCcAD', str.lower) --> A B C D722 seen = set()723 seen_add = seen.add724 if key is None:725 for element in filterfalse(seen.__contains__, iterable):726 seen_add(element)727 yield element728 else:729 for element in iterable:730 k = key(element)731 if k not in seen:732 seen_add(k)733 yield element734735def unique_justseen(iterable, key=None):736 "List unique elements, preserving order. Remember only the element just seen."737 # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B738 # unique_justseen('ABBCcAD', str.lower) --> A B C A D739 return map(next, map(operator.itemgetter(1), groupby(iterable, key)))740741def iter_except(func, exception, first=None):742 """ Повторно вызывает функцию до возникновения исключения.743744 Преобразует интерфейс вызова до исключения в интерфейс итератора.745 Как builtins.iter(func, sentinel), но использует исключение вместо746 сигнального значения для завершения цикла.747748 Примеры:749 iter_except(functools.partial(heappop, h), IndexError) # итератор очереди с приоритетом750 iter_except(d.popitem, KeyError) # итератор словаря без блокировки751 iter_except(d.popleft, IndexError) # итератор дека без блокировки752 iter_except(q.get_nowait, Queue.Empty) # цикл по очереди производителя753 iter_except(s.pop, KeyError) # итератор множества без блокировки754755 """756 try:757 if first is not None:758 yield first() # Для API баз данных, требующих первоначального приведения к db.first()759 while True:760 yield func()761 except exception:762 pass763764def first_true(iterable, default=False, pred=None):765 """Возвращает первое истинное значение в итерируемом объекте.766767 Если истинное значение не найдено, возвращает *default*768769 Если *pred* не равен None, возвращает первый элемент770 для которого pred(item) истинно.771772 """773 # first_true([a,b,c], x) --> a or b or c or x774 # first_true([a,b], x, f) --> a if f(a) else b if f(b) else x775 return next(filter(pred, iterable), default)776777def random_product(*args, repeat=1):778 "Random selection from itertools.product(*args, **kwds)"779 pools = [tuple(pool) for pool in args] * repeat780 return tuple(map(random.choice, pools))781782def random_permutation(iterable, r=None):783 "Random selection from itertools.permutations(iterable, r)"784 pool = tuple(iterable)785 r = len(pool) if r is None else r786 return tuple(random.sample(pool, r))787788def random_combination(iterable, r):789 "Random selection from itertools.combinations(iterable, r)"790 pool = tuple(iterable)791 n = len(pool)792 indices = sorted(random.sample(range(n), r))793 return tuple(pool[i] for i in indices)794795def random_combination_with_replacement(iterable, r):796 "Random selection from itertools.combinations_with_replacement(iterable, r)"797 pool = tuple(iterable)798 n = len(pool)799 indices = sorted(random.choices(range(n), k=r))800 return tuple(pool[i] for i in indices)801802def nth_combination(iterable, r, index):803 "Equivalent to list(combinations(iterable, r))[index]"804 pool = tuple(iterable)805 n = len(pool)806 if r < 0 or r > n:807 raise ValueError808 c = 1809 k = min(r, n-r)810 for i in range(1, k+1):811 c = c * (n - k + i) // i812 if index < 0:813 index += c814 if index < 0 or index >= c:815 raise IndexError816 result = []817 while r:818 c, n, r = c*r//n, n-1, r-1819 while index >= c:820 index -= c821 c, n = c*(n-r)//n, n-1822 result.append(pool[-1-n])823 return tuple(result)824```825