1. Правила комбинаторики. Комбинаторная математика.

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

• Задачи делятся на две части: подсчет комбинаций и генерация комбинаторных объектов.  

• В курсе будут рассматриваться задачи генерации комбинаторных объектов для решения других задач.  

• Комбинаторика основана на трех правилах: правило суммы, правило произведения и принцип Дирихле.  

• Правило суммы: количество элементов объединения непересекающихся множеств равно сумме их количеств.  

• Правило произведения: количество всевозможных пар элементов равно произведению их количеств.  

• Размещение: упорядоченные наборы элементов, количество которых обозначается как a из n по k.  

• Пример: распределение медалей среди команд.  

• Перестановки: упорядоченные наборы, где порядок элементов важен, количество обозначается с индексом n.  

• Задача: сгенерировать все возможные перестановки.  

• Оценка времени генерации объектов: запуск программы в режиме релиза и измерение времени генерации.  

• Пример: генерация перестановок для n=12 занимает одну секунду.  

• Важно оценивать время выполнения задач, чтобы избежать зависаний.  

• Запускайте задачи на домашнем компьютере, чтобы избежать проблем с производительностью.  

• Используйте дебаг для точного измерения времени выполнения.  

• Оцените время выполнения заданий, чтобы понять, сколько времени потребуется.  

• Удалите вывод в консоль для точного измерения времени.  

• Начните с простых задач, чтобы получить оценку времени выполнения.  

• Перестановки требуют много времени для выполнения.  

• Чем больше конфигураций, тем дольше будет выполняться задача.  

• Некоторые задачи невозможно решить на домашнем компьютере.  

• Некоторые задачи невозможно решить на домашнем компьютере.  

• Используйте приближенные методы или измените подход для таких задач.  

• Важно знать, какие задачи не стоит решать.  

• Примеры задач, которые сложно решить: поиск максимального пути, перестановки.  

• Используйте приближенные методы для таких задач.  

• Важно понимать, как задачи решаются и какие методы подходят.  

• Генерация комбинаторных объектов требует начального приближения и правила трансформации.  

• Условия остановки генерации должны быть интуитивно понятными.  

• Лексико-графический порядок используется для генерации комбинаторных конфигураций.  

• Лексико-графический порядок сравнивает слова по символам слева направо.  

• Если символы совпадают, слова сравниваются по числам.  

• Пример: "abc" меньше, чем "abcdf", так как "abc" меньше "abcdf" по алфавиту.  

• Алгоритм Нараямы генерирует перестановки в лексико-графическом порядке.  

• Работает с числами, а не с символами.  

• Пример: перестановки чисел 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.  

• Пример с числами: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.  

• Алгоритм ищет элемент, который больше или меньше предыдущего.  

• Пример: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.  

• Пример с числами: 2, 6, 5, 8, 7, 4, 3, 2, 1.  

• Алгоритм сравнивает элементы справа налево и меняет местами те, которые нарушают правило.  

• Пример: 2, 6, 5, 8, 7, 4, 3, 2, 1, 3, 1, 4, 3, 7, 4, 8, 5, 7, 5, 8.