Чем может быть полезна библиотека itertools

Библиотека itertools это набор быстрых и экономичных по объему памяти инструментов, которые полезны сами по себе или в сочетании. Для нас основная цель их применения это комбинаторика - перебор всех возможных перестановок пар, чисел, символов и т.д.

Пример: нас попросили перебрать все возможные перестановки символов 1, 2, 3, 4 без повторений символов.

import itertools

for s in itertools.permutations('1234', 4):
    print(s)

# Результат: 
('1', '2', '3', '4')
('1', '2', '4', '3')
('1', '3', '2', '4')
('1', '3', '4', '2')
('1', '4', '2', '3')
('1', '4', '3', '2')
('2', '1', '3', '4')
('2', '1', '4', '3')
('2', '3', '1', '4')
('2', '3', '4', '1')
('2', '4', '1', '3')
('2', '4', '3', '1')
('3', '1', '2', '4')
('3', '1', '4', '2')
('3', '2', '1', '4')
('3', '2', '4', '1')
('3', '4', '1', '2')
('3', '4', '2', '1')
('4', '1', '2', '3')
('4', '1', '3', '2')
('4', '2', '1', '3')
('4', '2', '3', '1')
('4', '3', '1', '2')
('4', '3', '2', '1')

Мы использовали метод permutation, который принимал в качестве аргументов алфавит и длину ожидаемой строки.

Поменяем условие: нас попросили перебрать все возможные строки длинны 3, состоящие только из символов 1, 2, 3 включая повторения.

import itertools

for s in itertools.product('123', repeat=3):
    print(s)

# Результат: 
('1', '1', '1')
('1', '1', '2')
('1', '1', '3')
('1', '2', '1')
('1', '2', '2')
('1', '2', '3')
('1', '3', '1')
('1', '3', '2')
('1', '3', '3')
('2', '1', '1')
('2', '1', '2')
('2', '1', '3')
('2', '2', '1')
('2', '2', '2')
('2', '2', '3')
('2', '3', '1')
('2', '3', '2')
('2', '3', '3')
('3', '1', '1')
('3', '1', '2')
('3', '1', '3')
('3', '2', '1')
('3', '2', '2')
('3', '2', '3')
('3', '3', '1')
('3', '3', '2')
('3', '3', '3')

Можем догадаться, что метод product перебирает всевозможные комбинации из символов, состоящие из символов алфавита.

Другие методы и примеры из документации:

Предлагаю все дальнейшие примеры рассматривать уже на реальных задачах с экзамена ЕГЭ:

КЕГЭ № 6537 (Уровень: Средний) Сколько существует восьмиразрядных чисел, записанных в тринадцатеричной системе счисления, которые содержат ровно 6 различных цифр и не более 2-х цифр А .

Комментарии к решению задачи:

мы импортировали встроенную в Python библиотеку в наш проект
создали счетчик, так как нас просят найти кол-во существующих чисел
через метод product перебираем всевозможные числа длины 8 составленные из алфавита - в том числе и с повторением символов
так как результат любого из методов библиотеки являются кортежи tuple, необходимо “склеить” их в строки
преобразовав строку str в тип данных set, мы удалим из неё копии, если длина set равна 6, то это будет означать, что строка содержит ровно 6 различных цифр
если в строке кол-во букв ‘A’ не более 2-х
если оба условия истинны, то к общему счетчику добавляем +1
выводим результаты из счетчика

import itertools
count = 0
for s in itertools.product('0123456789ABC', repeat=8):
    s = ''.join(s)
    if len(set(s)) == 6:
        if s.count('A') <= 2:
            count += 1
print(count)

Ответ: 298322640

2. КЕГЭ № 5114 /dev/inf 11.22 (Уровень: Базовый) Определите количество пятизначных чисел, записанных в семеричной системе счисления, в записи которых ровно одна цифра 5, при этом никакая четная цифра не стоит рядом с цифрой 5.

В этой задаче используется аналогичный метод

count = 0
import itertools
for s in itertools.product('0123456', repeat=5):
    s = ''.join(s)
    if s.count('5') == 1 and s[0] != '0':
        # if '50' not in s and '05' not in s ..... ; костыль
        if all(i not in s for i in '50 05 25 52 45 54 65 56'.split()):
            count += 1
print(count)

Ответ: 1176

3. КЕГЭ № 6897 OpenFIPI (Уровень: Средний)

Откройте файл электронной таблицы, содержащей в каждой строке четыре натуральных числа. Определите количество строк таблицы, содержащих числа, для которых выполнены оба условия:

– наибольшее из четырёх чисел меньше суммы трёх других;

– четыре числа нельзя разбить на две пары чисел с равными суммами.

В ответе запишите только число.

Файлы к заданию: 9.csv 9.ods 9.xls 9.xlsx

Комментарии к решению задачи:

импортируем библиотеку в проект
создаем счетчик для подсчета кол-ва подходящих по условиям строк
пробегаем .txt файл по строчкам
каждую s строку через списочное выражение преобразуем в список int-овых значений
первое условие - максимальный элемент меньше суммы оставшихся
самое интересное происходит здесь - функция all() вернет истинну, только если все содержимое внутри будет истинно, для этого мы перебераем все элементы списка M - комбинируем всевозможные перестановки и прогоняем их через условие, что суммы не должны быть равны
если условие тождественно истинно (всегда принимает значение истинны), то добавляем в итоговый счетчик +1
выводим результат на экран

import itertools
count = 0
for s in open('9.txt'):
    M = [int(i) for i in s.split()]  # – наибольшее из четырёх чисел меньше суммы трёх других;
    if max(M) < sum(M) - max(M):
				# if any(sum(A[:2]) == sum(A[2:]) for A in itertools.permutations(M, 4)):
        if all((A[0] + A[1] != A[2] + A[3]) for A in itertools.permutations(M, 4)):
            count += 1
print(count)

Ответ: 2396

КЕГЭ № 7095 OpenFIPI (Уровень: Базовый)

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:– символ «?» означает ровно одну произвольную цифру;

– символ «» означает любую последовательность цифр произвольной длины; в том числе «» может задавать и пустую последовательность.

Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 108, найдите все числа, соответствующие маске 1234*54, делящиеся на 21 без остатка.

В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 21.

Количество строк в таблице для ответа избыточно.

Конечно же в разговоре про библиотеку itertools нельзя обойти стороной 25 номер! Так как в условие к задаче говорится, что маска * может являться пустой и содержать значения вида '000', '001' - то лучший способ перебирать такие значения это библиотека itertools с методом product:

Комментарии к решению задачи:

импортировали библиотеку в проект
создали список, который будет хранить все возможные вариации маски *
установили, что длина маски * может равнять 0, 1 и 2 - перебрали все варианты
для каждого из вариантов сгенерировали кортеж s из алфавит десятичной системы счисления длины l
кортеж преобразовали через .join() в строку str()
и добавили строку в общий список M

Таким образом мы получим все варианты значений для маски *

import itertools
M = []
for l in range(0, 2+1):
    for s in itertools.product('0123456789', repeat=l):
        s = ''.join(s)
        M.append(s)

R = []
for x in M:
    A = int(f'1234{x}54')
    if A % 21 == 0:
        R.append([A, A//21])

for x in sorted(R):
    print(*x)

Ответ: 1234254 58774 12341154 587674 12343254 587774 12345354 587874 12347454 587974 12349554 588074