Рекурсия, перебор

Задача, которая на Python решается практически в одну строчку. Но благодаря ей, познакомимся с ещё одной полезной функцией стандартной библиотеки. Читаем условие: Для начала надо определить, сколько может быть перестановок, чтобы понять, можем ли мы использовать Python или потребуется что-нибудь быстрее. Так как символы не повторяются, количество различных перестановок равно факториалу от N. То есть в самом худшем случае будет 8! = 40,320 перестановок. Вывод очередной перестановки (как и построение следующей из предыдущей) занимает O(N) времени...

Немного упрощённый вариант Задачи 155. Конденсаторы, поэтому и решать будет простой рекурсивной функцией без всяких премудростей. Читаем условие: Чисел всего 4, деления нет, поэтому можно написать функцию, которая будет возвращать список со всеми числами, которые можно получить с помощью заданных арифметических операций. Так как функция будет рекурсивной, то назовём её rec. Тогда основное решение будет очень простым: Функция rec будет разделять входящий список чисел на две части во всех возможных местах и рекурсивно вызываться для каждой из них...

Задача из темы "Рекурсия, перебор", поэтому решим её через рекурсию, но также рассмотрим решение методом динамического программирования. Читаем условие: Рекурсия Разобьём нашу задачу размера N на подзадачи меньшего размера. Однако нельзя вычислить количество лесенок из N кубиков, зная ответы для меньшего числа, потому что они будут включать лесенки с одним кубиком на вершине (а такие лесенки никак не увеличить). Поэтому подзадачи будут с двумя параметрами: сколько существует лесенок из N кубиков, чтобы верхний ряд содержал не меньше M...

Я уже разбирал одну задачу на перебор (Задача 71. Две кучки камней), но там был перебор подмножеств, сейчас хочу показать, как можно легко перебирать расположение. Перестановки - это классический пример расположения элементов друг относительно друга. Если не наложено никаких ограничений, то существует n! = 1 * 2 * ... * n (факториал) различных перестановок длины n. Действительно, первый элемент можно поставить одним способом, второй можно поставить слева или справа от него (два варианта), у третьего элемента уже три окна возможностей, и так далее...

Не так много задач на перебор разобрано на этом канале, давайте исправлять ситуацию. Простая задача на перебор подмножеств: Есть много способов перебрать все подмножества, сейчас я расскажу самый простой с точки зрения реализации, но нам понадобится немного математики. Давайте посмотрим, как можно хранить множества. Так как каждый камень может находиться в одной из двух кучек, можно поставить им в соответствие 0 или 1. И тогда вариант разбиения на две кучки можно записать с помощью n цифр. Например...

Продолжаю находить для вас переоценённые задачи и разбирать их. На этот раз задача из раздела "Рекурсия, перебор". Читаем условие, обращаем внимание на ограничения во входных данных. Выглядит сложно. Сразу не очень понятно, как можно перебрать соединения. Например можно перебрать подмножество, затем перебрать все способы поделить его на две группы и запустить рекурсия для них, а потом все полученные варианты соединить последовательно (сложить) или параллельно (заиспользовать формулу из условия задачи)...