Библиотека Itertools

Библиотека itertools

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

Рассмотрим три основные функции: product, permutations и combinations.

1. product — последовательности с повторениями

Функция product составляет последовательности заданной длины. Каждый исходный символ можно использовать несколько раз.

from itertools import product
for i in product('АБ', repeat=3):
        a = ''.join(i)
        print(a)

Первый аргумент — доступные символы, а repeat=3 — длина последовательности. На каждую из трёх позиций независимо выбирается буква А или Б.

Результат:

ААА
ААБ
АБА
АББ
БАА
БАБ
ББА
БББ

Функция возвращает кортежи, например ('А', 'Б', 'А'). Чтобы работать с результатом как с обычной строкой, используем:

a = ''.join(i)

Метод join соединяет элементы. Пустые кавычки означают, что между ними не будет разделителя. Получаем строку 'АБА', в которой удобно считать буквы, обращаться к отдельным символам и искать сочетания.

Пример задачи. Сколько существует четырёхбуквенных слов из букв А, Б, В, Г, содержащих ровно одну букву А и не начинающихся с буквы Б?

from itertools import product
cnt = 0
for i in product('АБВГ', repeat=4):
    a = ''.join(i)    
    if a.count('А') == 1 and a[0] != 'Б':        
        cnt += 1
print(cnt)

Перебираем все слова длины 4. Проверка a.count('А') == 1 оставляет слова с одной буквой А, а a[0] != 'Б' исключает слова, начинающиеся с Б. Если оба условия выполнены, увеличиваем счётчик cnt. Программа выводит 81.

Алфавитный порядок и нумерация

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

Если в задаче требуется номер слова, добавляем счётчик, который увеличивается на каждой итерации, а не только при выполнении условия:

n = 0
for i in product('АБВГ', repeat=4):    
    a = ''.join(i)    
    n += 1

Теперь n — номер текущего слова, начиная с 1. Чтобы найти первое подходящее слово, после его обнаружения можно завершить цикл командой break. Чтобы найти последнее, нужно продолжать перебор и обновлять сохранённый номер при каждом совпадении.

2. permutations — перестановки

Функция permutations составляет последовательности, используя каждую исходную позицию не более одного раза. Если все исходные символы различны, повторяющихся символов в результате не будет.

from itertools import permutations
for i in permutations('АБВ', 2):    
    a = ''.join(i)    
    print(a)

Результат:

АБ
АВ
БА
БВ
ВА
ВБ

Второй аргумент задаёт длину последовательности. Если его не указать, используются все исходные элементы: permutations('АБВ') создаст перестановки длины 3.

Порядок здесь важен: АБ и БА — разные результаты. При этом АА не появляется, поскольку в исходной строке только одна буква А.

Повторяющиеся буквы и set

Если исходная строка содержит одинаковые буквы, permutations может выдавать одинаковые результаты. Для функции две буквы А на разных позициях — два отдельных элемента, хотя их перестановка между собой не меняет слово.

Чтобы оставить только различные перестановки, используем set:

set(permutations('ЛАРИСА'))

Пример задачи. Сколько различных слов можно составить перестановкой всех букв имени ЛАРИСА, если первая буква не должна быть гласной?

from itertools import permutations
cnt = 0for i in set(permutations('ЛАРИСА')):    
    a = ''.join(i)    
    if a[0] not in 'АИ':        
        cnt += 1
print(cnt)

В имени две одинаковые буквы А, поэтому set удаляет дубликаты перестановок. Затем проверяем, что первая буква не входит в строку 'АИ', то есть не является одной из гласных этого имени.

Программа выводит 180. Если исходные символы различны, set не нужен. Также нужно учитывать, что множество не сохраняет алфавитный порядок: использовать порядок его перебора для нумерации слов нельзя.

3. combinations — сочетания

Функция combinations выбирает заданное количество элементов без учёта порядка. Она подходит для задач, в которых важен состав выбранной группы, а не расположение элементов.

from itertools import combinations
for i in combinations('АБВГ', 2):
    a = ''.join(i)
    print(a)

Результат:

АБ
АВ
АГ
БВ
БГ
ВГ

Второй аргумент задаёт количество выбираемых элементов. Сочетание БА отдельно не появляется: это тот же выбор букв, что и АБ.

Каждая исходная позиция используется не более одного раза. При этом элементы внутри результата сохраняют порядок исходной последовательности. Если исходные цифры записаны по возрастанию и не повторяются, в каждом сочетании они тоже будут строго возрастать.

Пример задачи. Сколько существует трёхзначных десятичных чисел, цифры которых строго возрастают слева направо?

from itertools import combinations
cnt = 0
for i in combinations('0123456789', 3):
    a = ''.join(i)
    if a[0] != '0':
        cnt += 1
print(cnt)

Функция сразу создаёт последовательности с возрастающими цифрами: например, '123', '147', '589'. Проверять порядок отдельно не требуется.

Сочетания с нулём начинаются с него, поэтому исключаем их условием a[0] != '0': такая запись не является трёхзначным числом. Программа выводит 84.

4. Как записывать условия задачи

После строки a = ''.join(i) результат перебора становится обычной строкой. Для проверки ограничений используются индексы, метод count и операции in, not in.

Если число записано в другой системе счисления, основание указывается вторым аргументом: например, int(a, 8) преобразует восьмеричную запись в число.

Проверка соседних чётных и нечётных цифр

Если условие касается чётности соседних цифр, удобно привести их к двум символам с помощью replace:

for x in '02468':    
    a = a.replace(x, 'ч')
for x in '13579':    
    a = a.replace(x, 'н')

После такой замены сочетание чч означает две соседние чётные цифры, а нн — две соседние нечётные. Для проверки чередования записываем:

if 'чч' not in a and 'нн' not in a:    
    cnt += 1

Проверять начальный ноль, делимость и количество конкретных цифр нужно до замены, пока строка содержит исходную запись.

5. Как выбрать функцию

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