Стандартная библиотека и перебор комбинаций

Сосчитать буквы слова "BANANA", обслужить заявки по очереди, сложить 1/3 и 1/6 без погрешности, перебрать все слова из букв A, B, C — всё это можно написать циклами и словарями. Но такие задачи встречаются так часто, что для них есть готовые средства. Стандартная библиотека Python — набор модулей, которые есть в любой установке; ими пользуются, когда понятно, что они делают внутри.

Разберём подсчёт, очередь, точные дроби и перебор комбинаций — на тех же примерах.

Каждое средство библиотеки делает то, что ты уже умеешь писать сам. Модуль подключают через import, как math в уроке о модулях. Средства этого и прошлых уроков:

Перед каждым средством стоит один вопрос: что оно делает внутри и при каких условиях ответ верен. cache требует, чтобы аргументы полностью определяли результат, а для itertools надо заранее понимать, сколько вариантов получится.

Counter — готовый словарь частот, defaultdict сам создаёт значение для нового ключа.

from collections import Counter, defaultdict counts = Counter("BANANA")print(counts["A"])print(counts["Z"])print(counts.most_common(2)) groups = defaultdict(list)groups["python"].append("Анна")print(groups["python"])

Counter делает то же, что цикл counts[x] = counts.get(x, 0) + 1 из урока о словарях, а для отсутствующего ключа возвращает 0 без ошибки. most_common(k) даёт k самых частых пар «значение — частота». defaultdict(list) получает функцию list без скобок и вызывает её для каждого нового ключа — так у ключа сразу появляется пустой список.

deque — очередь: добавляют в конец, быстро забирают из начала. Очередь работает по правилу «первым пришёл — первым вышел», так обслуживают заявки по порядку поступления.

from collections import deque queue = deque([1, 2, 3])queue.append(4)first = queue.popleft()print(first, list(queue))

append добавляет справа, popleft удаляет и возвращает элемент слева. У списка то же делает pop(0), но медленно: элементы списка стоят по номерам, и после удаления первого все остальные сдвигаются на место левее.

Fraction и Decimal считают точно там, где float ошибается. В уроке о числах 0.1 + 0.2 дало не ровно 0.3. Точные числа решают это:

from fractions import Fractionfrom decimal import Decimalfrom math import isclose print(Fraction(1, 3) + Fraction(1, 6))print(Decimal("0.1") + Decimal("0.2"))print(isclose(0.1 + 0.2, 0.3))

Fraction хранит числитель и знаменатель, поэтому 1/3 + 1/6 даёт ровно 1/2. Decimal создают из строки: Decimal(0.1) перенёс бы уже неточное float. Если точность не нужна, а нужно сравнить два float, isclose(a, b) проверяет, что они почти равны.

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

itertools.product выдаёт слова по порядку, как счётчик пробега: правая позиция перебирает все буквы, затем левая сдвигается на следующую, а правая начинает сначала. Пройди по шагам слова длины 2 из букв A, B, C:

Посчитаем слова длины 3 из букв A, B, C, в которых ровно одна A:

from itertools import product count = 0for letters in product("ABC", repeat=3):    word = "".join(letters)    if word.count("A") == 1:        count += 1print(count)

product выдаёт кортежи букв, например ('A', 'B', 'C'); "".join склеивает их в слово. Всего слов 3 ** 3 = 27. Подходящих 12: одна из трёх позиций под A, на двух других — по два варианта, 3 · 2 · 2 = 12. Такой ручной подсчёт — независимая проверка программы.

Перестановки, сочетания и слова различаются тем, важен ли порядок и можно ли повторять. product строит слова, permutations — расстановки разных предметов, combinations — выбор группы, combinations_with_replacement — выбор с повторениями без порядка. Разницу видно на парах из букв A, B, C:

from itertools import combinations, permutations, product items = "ABC"print(len(list(product(items, repeat=2))))print(len(list(permutations(items, 2))))print(len(list(combinations(items, 2))))print(["".join(p) for p in combinations(items, 2)])

Числа получаются выбором по позициям: 3 · 3 = 9; 3 · 2 = 6 — вторая буква не может повторить первую; 6 / 2 = 3 — пары AB и BA становятся одной группой.

Функции различают элементы по позиции в источнике. Если в слове есть одинаковые буквы, перестановки дадут одинаковые слова, и их убирают через set(...). Если вариант — запись числа, первая цифра обычно не может быть нулём: это условие добавляют отдельно. И не собирай все варианты в список, если их можно проверять по одному.