Комбинаторика: от ЕГЭ до алгоритмических собеседований на Python

Основы комбинаторного анализа: правила суммы и произведения

Добро пожаловать на курс «Комбинаторика: от ЕГЭ до алгоритмических собеседований на Python». Это первая статья нашего цикла, и мы начнем с фундамента, на котором строится вся дискретная математика.

Многие считают комбинаторику сложным разделом математики, полным запутанных формул с факториалами. Однако в её основе лежат всего два интуитивно понятных принципа: правило суммы и правило произведения. Поняв их, вы сможете решать как задачи №8 из ЕГЭ, так и оценивать сложность алгоритмов на собеседованиях в IT-гиганты.

Что такое комбинаторика?

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

Зачем это нужно программисту?

Правило суммы (The Rule of Sum)

Начнем с самого простого. Представьте, что вы решили изучить новый язык программирования. У вас есть выбор: записаться на один из 3 курсов по Python или на один из 2 курсов по Java. Вы не можете учить оба языка одновременно, вам нужно выбрать только один курс.

Сколько всего у вас вариантов выбора?

Логика подсказывает: . Это и есть правило суммы.

Формальное определение

Если объект можно выбрать способами, а объект — способами, причём выбор одного объекта исключает выбор другого (то есть нельзя выбрать и , и одновременно), то выбор «либо , либо » можно сделать способами.

На языке теории множеств это записывается так:

Где:

> Важное условие: Множества не должны пересекаться (). Если есть курс, который обучает и Python, и Java одновременно, простая формула суммы не сработает (потребуется формула включений-исключений, о которой мы поговорим в будущих статьях).

Пример из жизни (ЕГЭ)

На тарелке лежат 5 яблок и 4 груши. Сколькими способами можно выбрать один фрукт?

Решение: Мы выбираем или яблоко, или грушу. Действия взаимоисключающие.

Где — общее количество способов выбрать один фрукт.

Реализация на Python

В программировании правило суммы часто встречается, когда мы объединяем списки или проверяем условия if-elif.

Правило произведения (The Rule of Product)

Теперь усложним задачу. Допустим, вы собираетесь на собеседование. Вам нужно выбрать рубашку и брюки. В шкафу висят 3 разные рубашки и 2 пары брюк. Сколькими способами вы можете одеться?

Здесь мы выбираем И рубашку, И брюки. Это пара предметов.

Давайте рассуждать:

Итого: вариантов. Или проще: .

[VISUALIZATION: Дерево вариантов выбора одежды. Слева корень, от него отходят 3 ветки с подписями

Классические формулы: перестановки, размещения и сочетания без повторений

В предыдущей статье мы разобрали фундамент комбинаторики — правила суммы и произведения. Мы научились складывать варианты, когда выбираем «или то, или это», и перемножать их, когда выбираем «и то, и это».

Сегодня мы сделаем следующий шаг. Мы перейдем от общих принципов к конкретным формулам, которые позволяют мгновенно решать типовые задачи. Эти три кита комбинаторики — перестановки, размещения и сочетания.

Понимание разницы между ними — это 90% успеха при решении задач №8 в ЕГЭ и комбинаторных задач на собеседованиях (например, при генерации всех возможных подмножеств массива).

Факториал: главный инструмент

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

Факториал числа — это произведение всех натуральных чисел от 1 до включительно.

Где:

Примеры: - -

> Важное исключение: Математики договорились, что . Это необходимо для того, чтобы комбинаторные формулы работали корректно.

Реализация на Python

В Python факториал уже реализован в модуле math. Вам не нужно писать цикл for вручную.

1. Перестановки (Permutations)

Представьте, что у вас на полке стоят 3 разные книги: «Гарри Поттер», «Властелин Колец» и «Дюна». Сколькими способами вы можете расставить их в ряд?

Давайте рассуждать, используя правило произведения:

Итого: способов.

Это и есть перестановка. Мы берем все имеющиеся элементы и просто меняем их порядок.

Формула

Количество перестановок из элементов обозначается и равно факториалу :

Где:

Пример задачи (ЕГЭ)

Сколько различных пятибуквенных «слов» (наборов букв) можно составить из букв слова «МЕТРО», если каждая буква используется ровно один раз?

Решение: В слове «МЕТРО» 5 уникальных букв. Мы используем все 5 букв. Порядок важен (МЕТРО и РЕТМО — разные слова). Значит, это перестановка.

Где — искомое количество слов.

Python: itertools.permutations

В библиотеке itertools есть функция для генерации перестановок.

2. Размещения (Arrangements)

Теперь усложним задачу. У нас есть 10 бегунов, участвующих в олимпийском забеге. Но медалей всего 3: золотая, серебряная и бронзовая. Сколькими способами можно распределить медали?

Здесь важны два момента:

Такие комбинации называются размещениями.

Формула

Количество размещений из элементов по обозначается :

Где:

Разбор формулы на примере бегунов:

Формула дает тот же результат:

Где — количество способов распределить 3 медали среди 10 участников.

Python

Функция itertools.permutations умеет работать и как размещения, если передать ей второй аргумент — длину последовательности.

3. Сочетания (Combinations)

Это, пожалуй, самая популярная формула в программировании и теории вероятностей.

Представьте, что вам нужно выбрать 2 дежурных из класса в 30 человек. Важно ли, кто будет первым, а кто вторым? Нет. Главное — попасть в эту пару. Пара «Иванов и Петров» — это то же самое, что «Петров и Иванов».

Когда мы выбираем часть элементов и порядок НЕ важен, это называется сочетаниями.

Формула

Количество сочетаний из по обозначается (читается «це из эн по ка»):

Где:

Пример задачи (Собеседование)

В турнире участвуют 6 команд. Каждая команда должна сыграть с каждой по одному разу. Сколько всего будет матчей?

Решение: Матч — это выбор 2 команд из 6. Порядок не важен (игра «Команда А против Команды Б» — это тот же самый матч, что и «Команда Б против Команды А»).

Где — количество матчей.

Python: itertools.combinations

Как выбрать правильную формулу?

Самая большая сложность — понять, какую из трех формул применить. Для этого задайте себе два вопроса:

!Схема выбора между перестановками, размещениями и сочетаниями

Сводная таблица

| Название | Обозначение | Порядок важен? | Выбираем все элементы? | Пример | | :--- | :--- | :--- | :--- | :--- | | Перестановки | | Да | Да | Очередь в кассу | | Размещения | | Да | Нет | Победители гонки (1, 2, 3 место) | | Сочетания | | Нет | Нет | Выбор ингредиентов для пиццы |

Связь с алгоритмическими собеседованиями

Понимание этих формул критически важно для оценки сложности алгоритмов (Big O).

Если вы решаете задачу методом грубой силы (brute force), перебирая варианты:

Зная формулы, вы можете сразу сказать интервьюеру: «Решение перебором всех пар будет иметь сложность , так как количество пар — это , что пропорционально квадрату ».

В следующей статье мы разберем более сложные случаи: что делать, если элементы повторяются (например, анаграммы слова «МОЛОКО»).

Сложные конфигурации: выборки с повторениями и бином Ньютона

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

Что, если в слове есть одинаковые буквы? Что, если мы генерируем пароль, где цифры могут повторяться? Что, если мы покупаем пирожные, и нам неважно, в каком порядке их кладут в коробку, но мы можем взять 5 одинаковых эклеров?

Сегодня мы расширим наш арсенал формул, добавив в него повторения, и познакомимся с биномом Ньютона — мостом между алгеброй и комбинаторикой.

1. Перестановки с повторениями

Вспомним задачу про анаграммы. Сколько слов можно составить из букв слова «КОТ»? Буквы разные, поэтому .

А теперь попробуйте посчитать количество анаграмм для слова «МАМА».

Если бы мы пометили буквы индексами (), то вариантов было бы . Но для нас и — это одна и та же буква. Поменяв их местами, мы не получим новое слово.

Поскольку у нас две буквы «М», количество вариантов уменьшается в раз. Аналогично для двух букв «А».

Формула

Если у нас есть элементов, среди которых элементов первого типа, элементов второго типа и так далее до , то количество перестановок с повторениями вычисляется так:

Где:

Пример (ЕГЭ / Собеседование)

Сколько различных слов можно составить, переставляя буквы слова «МОЛОКО»?

Решение: Всего букв: . Состав:

Где — искомое количество слов.

Реализация на Python

Для подсчета частоты элементов удобно использовать collections.Counter, а затем применить формулу.

2. Размещения с повторениями

Это самый простой случай, с которым программисты сталкиваются чаще всего. Представьте, что вы подбираете 4-значный пин-код. Цифры могут повторяться (например, «1111» или «1212»).

Логика проста:

Формула

Количество размещений с повторениями из элементов по обозначается :

Где:

> Важно: В этой формуле может быть больше . Например, из 2 цифр (0 и 1) можно составить байт длиной 8 бит ().

Python: itertools.product

Эта функция генерирует декартово произведение, что эквивалентно вложенным циклам.

3. Сочетания с повторениями

Самый сложный для интуитивного понимания тип.

Представьте, что вы пришли в кондитерскую. В продаже есть 3 вида пирожных: Эклер, Корзиночка, Наполеон. Вы хотите купить 2 пирожных.

Какие есть варианты?

Порядок не важен (набор «Эклер и Наполеон» — это то же самое, что «Наполеон и Эклер»). Но элементы могут повторяться.

Метод перегородок (Stars and Bars)

Чтобы вывести формулу, математики придумали красивый трюк. Представим наш выбор как расстановку разделителей.

Пусть у нас есть вида пирожных. Чтобы разделить их, нам нужно 2 перегородки (палочки ).

Мы выбираем пирожных (обозначим их звездами ).

Тогда покупка «2 Эклера» выглядит так: **|| (2 в первой зоне, 0 во второй, 0 в третьей). Покупка «Эклер и Наполеон»: | | (1 в первой, 0 во второй, 1 в третьей). Покупка «2 Корзиночки»: |**|.

Задача сводится к перестановке символов (звезд и палочек). Всего позиций . Из них нам нужно выбрать места для звезд.

!Визуализация метода Stars and Bars для выбора пирожных

Формула

Количество сочетаний с повторениями из по обозначается :

Где:

Пример задачи

В цветочном магазине продаются розы, тюльпаны и хризантемы (3 вида). Сколькими способами можно составить букет из 5 цветов?

Решение: (виды), (количество в букете).

Где 21 — количество вариантов составить букет.

Python: itertools.combinations_with_replacement

4. Бином Ньютона и Треугольник Паскаля

Вы наверняка помните формулы сокращенного умножения из школы:

А что, если нужно раскрыть скобки для или ? Здесь на помощь приходит комбинаторика.

Коэффициенты при слагаемых в разложении — это не что иное, как число сочетаний .

Формула Бинома Ньютона

Где:

Например, для :

Треугольник Паскаля

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

Это свойство () является основой динамического программирования. Многие алгоритмические задачи (например, поиск количества путей в сетке) решаются именно через построение такого треугольника.

Итоги

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

| Тип | Без повторений | С повторениями | | :--- | :--- | :--- | | Перестановки (порядок важен, все элементы) | | | | Размещения (порядок важен, часть элементов) | | | | Сочетания (порядок НЕ важен) | | |

В следующей статье мы перейдем к практике: разберем сложные задачи из ЕГЭ и популярные вопросы с собеседований в Яндекс и Google, где нужно применять эти формулы в коде.

Прикладная комбинаторика в Python: генерация объектов и библиотека itertools

В предыдущих статьях мы погружались в теорию: изучали факториалы, выводили формулы сочетаний и размещений, рисовали схемы с перегородками. Мы научились отвечать на вопрос «Сколько?».

Но в реальной разработке — будь то написание скрипта для автоматизации, создание тестов или решение алгоритмической задачи на собеседовании — нам часто нужно отвечать на вопрос «Какие именно?». Нам нужно не просто знать, что существует 120 перестановок слова, а получить их список, чтобы проверить каждую.

Сегодня мы переходим от математических абстракций к чистому коду. Мы изучим модуль itertools — швейцарский нож питониста для работы с комбинаторикой.

Почему itertools?

Python поставляется с батарейками в комплекте. Модуль itertools входит в стандартную библиотеку, поэтому его не нужно устанавливать через pip. Он написан на C, что делает его невероятно быстрым и эффективным по памяти.

Главная особенность модуля — он возвращает итераторы, а не списки. Это значит, что комбинации генерируются «на лету», по одной, не занимая гигабайты оперативной памяти.

Для начала работы нам нужно импортировать модуль:

1. Декартово произведение: itertools.product

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

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

Синтаксис

Пример: Взлом пин-кода

Допустим, нам нужно сгенерировать все возможные 4-значные пин-коды (от 0000 до 9999). С точки зрения математики это размещения с повторениями: .

Где — общее число вариантов, — количество символов (10 цифр), — длина кода (4).

Это также работает для объединения разных списков (например, масть и достоинство карты).

[VISUALIZATION: Схематичное изображение декартова произведения в виде таблицы. По вертикали список мастей карт, по горизонтали список достоинств. В ячейках пересечения показаны пары (карта, масть).]

2. Перестановки: itertools.permutations

Эта функция реализует математическую операцию перестановки () или размещения без повторений ().

Напомним формулу размещений:

Где — число размещений, — всего элементов, — сколько выбираем, — факториал.

Синтаксис

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

Пример: Задача коммивояжера (Brute Force)

Представьте, что курьеру нужно объехать 3 точки: A, B, C. В каком порядке их лучше посетить, чтобы путь был минимальным? Для этого нужно перебрать все варианты маршрутов.

Важно: Порядок элементов здесь имеет значение. ('A', 'B') и ('B', 'A') — это разные кортежи.

3. Сочетания: itertools.combinations

Это, пожалуй, самая часто используемая функция в алгоритмических задачах. Она реализует сочетания без повторений ().

Формула:

Где — число сочетаний, — всего элементов, — размер группы.

Главное отличие от перестановок: порядок внутри группы не важен. Группа (1, 2) — это то же самое, что (2, 1), поэтому функция вернет только один вариант (обычно отсортированный по порядку появления в исходном списке).

Синтаксис

Аргумент r (размер группы) здесь обязателен.

Пример: Анализ пар данных

Допустим, у нас есть список из 5 серверов, и мы хотим проверить связь между каждым с каждым (топология full-mesh). Нам нужны все уникальные пары.

4. Сочетания с повторениями: itertools.combinations_with_replacement

Эта функция соответствует сложной формуле с перегородками (Stars and Bars), которую мы разбирали в прошлой статье:

Где — число сочетаний с повторениями.

Она позволяет выбирать элементы, где порядок не важен, но один и тот же элемент может быть выбран несколько раз.

Пример: Бросок костей или покупка товаров

Представьте, что вы покупаете 3 шарика мороженого, а в магазине всего 2 вкуса: Шоколад (Ш) и Ваниль (В). Вы можете взять (Ш, Ш, Ш), или (Ш, В, В) и так далее.

Практический кейс: Решение задачи на собеседовании

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

Задача: Дан список чисел. Нужно найти, существуют ли в нем три числа, сумма которых равна ровно 100.

Решение «в лоб» (Brute Force) с использованием itertools:

Анализ сложности: Количество операций здесь пропорционально , что примерно равно . Для списка из 100 элементов это сработает мгновенно (~160 000 операций). Для списка из 10 000 элементов это решение «упадет» по времени. Однако, как первое приближение или для написания тестов — это идеальный инструмент.

Опасности и производительность

Самая частая ошибка новичка — попытка превратить итератор в список на огромных данных.

Правильный подход — итерироваться в цикле:

Сводная таблица методов

| Метод | Порядок важен? | Повторы элементов? | Аналог в математике | | :--- | :--- | :--- | :--- | | product(p, q) | Да | Да | Декартово произведение, Размещения с повторениями | | permutations(p, r) | Да | Нет | Перестановки, Размещения | | combinations(p, r) | Нет | Нет | Сочетания | | combinations_with_replacement | Нет | Да | Сочетания с повторениями |

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

Практикум: решение задач ЕГЭ №8 и алгоритмических задач с собеседований

Мы прошли долгий путь: от базовых правил суммы и произведения до сложных формул с повторениями и генераторов itertools. Теперь пришло время собрать все знания воедино и применить их на практике.

В этой финальной статье курса мы рассмотрим два мира:

Часть 1. Комбинаторика в ЕГЭ (Задание №8)

Задание №8 в ЕГЭ по информатике проверяет умение подсчитывать количество вариантов построения символьных последовательностей. Раньше эти задачи решали только формулами, но с появлением компьютеров на экзамене Python стал «легальным чит-кодом».

Типовая задача: Слова с ограничениями

Условие: Сколько существует 5-буквенных слов, составленных из букв слова «ПИТОН», в которых буква «О» встречается ровно один раз, а буква «Н» не стоит на первом месте? Каждая буква может использоваться несколько раз.

#### Способ 1: Аналитическое решение

Давайте рассуждать математически. У нас есть алфавит из 5 букв: П, И, Т, О, Н. Длина слова — 5 позиций.

Разобьем задачу на два случая в зависимости от того, где стоит буква «О».

Случай А: Буква «О» стоит на первом месте.

Количество вариантов для случая А:

Где — количество слов, начинающихся на «О», а — количество доступных букв для остальных позиций.

Случай Б: Буква «О» стоит НЕ на первом месте.

Количество вариантов для случая Б:

Где — количество слов, где «О» не на первом месте, — выбор места для «О», — выбор первой буквы, — выбор остальных букв.

Итоговый ответ:

Где — общее количество искомых слов.

#### Способ 2: Программное решение (Python)

На экзамене легко ошибиться в арифметике. Python позволяет решить эту задачу методом грубой силы (brute force), перебрав все варианты. Для длины 5 и алфавита 5 это всего вариантов, что для компьютера — мгновение.

Мы будем использовать itertools.product, так как буквы могут повторяться (размещения с повторениями).

> Совет: Всегда используйте программный метод для проверки аналитического решения, если пространство перебора не превышает 10-20 миллионов вариантов.

Часть 2. Алгоритмические собеседования (FAANG)

На собеседованиях в Яндекс, Google или Amazon вам не дадут задачу «посчитать количество слов». Вас попросят написать алгоритм, который генерирует эти комбинации или использует комбинаторные свойства для оптимизации.

Задача 1: Генерация всех подмножеств (Subsets)

Условие (LeetCode 78): Дан массив уникальных чисел nums. Вернуть все возможные подмножества (булеан). Пример: [1, 2] [], [1], [2], [1, 2].

Анализ: Количество подмножеств множества из элементов равно . Это классическая задача на сочетания. Нам нужно выбрать 0 элементов, потом 1 элемент, потом 2... и так до .

Решение через itertools: Здесь идеально подходит функция combinations, запущенная в цикле по длине подмножества.

Сложность этого алгоритма — , так как мы генерируем объектов. Быстрее сделать невозможно, так как таков размер выходных данных.

Задача 2: Уникальные пути (Unique Paths)

Условие (LeetCode 62): Робот находится в левом верхнем углу сетки . Он может двигаться только вниз или вправо. Сколькими способами он может добраться до правого нижнего угла?

!Робот в лабиринте выбирает путь только вправо и вниз

Решение методом динамического программирования: Обычно эту задачу решают, создавая таблицу и суммируя пути. Сложность .

Решение методом комбинаторики: Давайте посмотрим на задачу иначе. Чтобы дойти от старта до финиша в сетке , робот обязан сделать ровно шагов вниз и шагов вправо. Порядок шагов может быть любым, но их количество фиксировано.

Всего шагов:

Где — общая длина пути.

Нам нужно выбрать, на каких именно позициях из этих шагов робот пойдет «Вниз». Остальные шаги автоматически станут «Вправо».

То есть задача сводится к выбору позиций из доступных. Это формула сочетаний!

Где — число сочетаний, — факториал.

Решение на Python: Это решение имеет сложность или даже , если считать арифметические операции за константу. Это намного эффективнее динамического программирования по памяти.

Задача 3: Следующая перестановка (Next Permutation)

Условие (LeetCode 31): Реализовать алгоритм, который перестраивает числа в массиве так, чтобы получить следующую лексикографически (по алфавиту) большую перестановку. Если такой нет, вернуть минимальную (отсортированную).

Пример: [1, 2, 3] [1, 3, 2] [2, 1, 3].

Почему нельзя использовать itertools? Если массив длинный (например, 100 элементов), генерация всех перестановок через itertools.permutations займет вечность ( — астрономическое число). Нам нужно найти только одну следующую.

Алгоритм:

Это пример задачи, где знание того, как устроены перестановки, важнее, чем умение вызывать библиотечную функцию.

Когда использовать формулы, а когда перебор?

| Ситуация | Подход | Почему | Сложность | | :--- | :--- | :--- | :--- | | ЕГЭ №8 (малые числа) | itertools | Быстро пишется, исключает ошибки вычислений | Зависит от , обычно приемлемо | | ЕГЭ №8 (огромные числа) | Формулы | Перебор вариантов не сработает по времени | | | Собеседование (найти количество) | Формулы / DP | Требуется оптимальное решение | или | | Собеседование (вывести все варианты) | Рекурсия / itertools | Нужно вернуть список объектов | или |

Заключение курса

Поздравляем! Вы прошли путь от основ правил суммы и произведения до решения задач уровня Google.

Комбинаторика — это не просто раздел математики про «доставание шаров из урны». Это язык, на котором мы говорим о сложности алгоритмов, о криптографии, о генерации тестов и о структуре данных.

Ваш чек-лист навыков:

Удачи на экзаменах и собеседованиях! Практикуйтесь, и формулы станут вашими верными инструментами.