TwiddleLab / Код / Рекурсия: функции, которые вызывают себя
Перебери всё: подмножества и порядки
Что ты узнаешь
- Полный перебор: перечисли все варианты и проверь каждый.
- Подмножества: каждый вызов решает про один элемент, взять или пропустить, и доверяет себе остальное. n элементов дают 2^n подмножеств.
- Порядки: каждый вызов выбирает следующий элемент из оставшихся. n элементов дают n! порядков, а это растёт ещё быстрее.
- У 10 песен уже 3 628 800 порядков, поэтому перечислять всё скоро становится слишком долго.
Как идёт урок
Пять начинок для пиццы. Сколько разных пицц можно заказать?
Любое их сочетание, включая простую пиццу без начинок.
По одному решению за раз: взять или пропустить.
Вырасти дерево для 3 начинок, потом добавляй начинки, пока не дойдёшь до 5.
Каждая пицца из меню поменьше встречается в большем дважды: с новой начинкой и без неё. Поэтому каждая начинка удваивает число.
Пропавшая пицца: одной нет в меню. Найди её.
Собери её кнопками начинок и нажми «Заказать». Два раунда на время.
Полный перебор, подмножества и порядки.
Полный перебор значит породить все варианты и проверить каждый. Рекурсия делает такой список простым.
Подмножества: вызов решает про первый элемент, взять или пропустить, и вызывает себя на остальном. Базовый случай: элементов не осталось, напечатай выбранное. 2^n результатов.
Порядки: вызов выбирает, какой элемент идёт следующим, для каждого оставшегося, и вызывает себя на остальном. n x (n - 1) x ... x 1 = n! результатов.
Напиши subsets(items, chosen).
Базовый случай: элементов не осталось, напечатай выбранные. Иначе: один раз с первым элементом, один раз без.
Каждый вызов убирает один элемент, поэтому items сжимается до пустого, и базовый случай достигается. Два вызова, один с добавленным элементом и один без, строят дерево «взять или пропустить».
Твоя пиццерия: выбери 4 начинки и перечисли все пиццы.
Твоя subsets работает на твоих начинках.
Теперь порядок важен: 3 песни в плейлисте.
Каждый уровень выбирает следующую песню из оставшихся. Вырасти дерево.
Подмножества против порядков. Когда порядков станет больше миллиона?
Двигай n и найди первый размер плейлиста, у которого больше 1 000 000 порядков, потом «Проверить».
2^n умножается на 2 каждый шаг; n! умножается на n, а оно всё растёт. 9! = 362 880 и 10! = 3 628 800.
Какую пиццу твой код напечатает первой?
Здесь все пиццы из твоих начинок вперемешку. Нажми на одну, потом «Проверить».
subsets(items[1:], chosen + [items[0]]) выполняется раньше subsets(items[1:], chosen) на каждом уровне. Поэтому первый путь вниз это каждый раз «взять», и первая печать это полная пицца.
Предыдущий урок: Разделяй и властвуй · Следующий урок: Перебор с возвратом: проходим лабиринт · Часть курса: Рекурсия: функции, которые вызывают себя
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
