Алгоритмы с нуля
Комбинации
В предыдущем уроке ты выбирал перестановки, решая “какой элемент дальше?”, и подмножества, решая “включить или исключить каждый?”. Теперь третья вариация: выбери k элементов из n, но порядок не имеет значения. {A, B} и {B, A} — это одна комбинация, хотя это разные перестановки. Трюк чтобы не генерировать одну комбинацию дважды — проходить элементы в фиксированном порядке и требовать, что выборы идут только вперёд, никогда назад. Одна идея, начальный индекс, превращает тонкую проблему в чистую.
После этого урока ты можешь написать функцию backtracking’а для генерирования всех комбинаций k элементов из n. Ты понимаешь, почему есть C(n, k) = n! / (k!(n-k)!) комбинаций — биномиальный коэффициент. Ты видишь трюк начального индекса: рассматривая только элементы от индекса i и дальше, ты естественно избегаешь дубликатов и обрезаешь ветви рано. Ты контрастируешь комбинации с перестановками и подмножествами, видя как один шаблон адаптируется к разной логике выбора.
Комбинации: выбери k из n
Комбинация — это выбор k элементов из набора из n элементов, где порядок не имеет значения. Набор {A, B, C} имеет три 2-комбинации: {A, B}, {A, C}, {B, C}. Заметь, {A, B} и {B, A} — одна комбинация — мы не считаем её дважды.
Пример: сколько способов выбрать 2 человека из группы 4?
{1, 2},{1, 3},{1, 4},{2, 3},{2, 4},{3, 4}
Всего: 6 комбинаций. В общем, количество C(n, k) = n! / (k!(n-k)!), также пишется как “n choose k” или биномиальный коэффициент.
Почему C(n, k), а не n!?
Перестановки считают все упорядочения: {A, B} и {B, A} разные. Комбинации считают только выборы: {A, B} и {B, A} одинаковые. Чтобы конвертировать перестановки в комбинации, раздели на k! упорядочений внутри выбранного набора. Так C(n, k) = P(n, k) / k! = n! / ((n-k)! × k!).
Комбинации vs. перестановки: трюк начального индекса
С перестановками ты спрашиваешь: “какой неиспользованный элемент идёт дальше?” Ты отслеживаешь массив used чтобы не переиспользовать один элемент.
С комбинациями ты спрашиваешь: “включаю этот элемент или пропускаю?” Но в отличие от подмножеств — где ты ветвишься на каждый элемент — тут ты можешь быть умнее. Ты требуешь порядок: если ты включаешь элемент с индексом i, следующий элемент что ты рассматриваешь должен быть из индекса i+1 или позже. Это предотвращает генерирование одного набора дважды с разными упорядочениями.
Форма backtracking’а для комбинаций
function combinations(arr, k, start, current, result):
if len(current) == k:
result.append(copy(current))
return
for i in range(start, len(arr)):
# Выбор: включи arr[i]
current.push(arr[i])
combinations(arr, k, i + 1, current, result) # Следующий start это i+1
current.pop()Ключевая идея: цикл начинается с start, не с 0. Так если ты выбираешь arr[2], следующий рекурсивный вызов рассматривает только arr[3], arr[4], и т.д. Более ранние элементы (arr[0], arr[1]) никогда не переиспользуются. Это гарантирует нет дубликатов.
Пример: комбинации из {1, 2, 3, 4}, выбрать 2
- Начни с i=0: включи 1, потом смотри на индексы 1+ →
{1,2},{1,3},{1,4}. - Начни с i=1: включи 2, потом смотри на индексы 2+ →
{2,3},{2,4}. - Начни с i=2: включи 3, потом смотри на индексы 3+ →
{3,4}. - Начни с i=3: включи 4, но нет индексов после 3. (Это обрезание происходит естественно.)
Результат: 6 комбинаций. Нет дубликата как {2, 1} потому что мы никогда не исследуем её — раз мы выбираем 1, мы рассматриваем только 2+.
Обрезание: ранняя остановка
В любой точке, если количество оставшихся элементов плюс текущий размер не может дотянуть до k, обрежь ветвь.
remaining = len(arr) - start
if len(current) + remaining < k:
return # Недостаточно элементов осталось чтобы достичь kНапример, если ты выбрал 1 элемент, нужен k=3, и осталось только 2 элемента, останови — ты не можешь достичь k=3. Это обрезает множество ветвей.
Комбинации vs. подмножества vs. перестановки: резюме шаблона
| Задача | Выбор | Начало цикла | Базовый случай | Количество выхода |
|---|---|---|---|---|
| Подмножества | включить/исключить каждый | N/A (глубина) | глубина == n | 2^n |
| Перестановки | какой неиспользованный дальше | 0 (всегда) | размер == n | n! |
| Комбинации | включить/пропустить в порядке | индекс start | размер == k | C(n,k) |
Все три используют один и тот же choose-explore-undo шаблон. Разница в логике цикла и базовом случае.
Из курса математики КомбинацииДавай кодировать комбинации.
Пример: Генерируй все комбинации k элементов из n элементов
function combinations(arr, k) {
const result = [];
function backtrack(start, current) {
// Базовый случай: построил полную комбинацию
if (current.length === k) {
result.push([...current]);
return;
}
// Обрезание: недостаточно элементов осталось
const remaining = arr.length - start;
if (current.length + remaining < k) {
return;
}
// Пробуй каждый элемент от 'start' и дальше
for (let i = start; i < arr.length; i++) {
// Выбор: включи arr[i]
current.push(arr[i]);
backtrack(i + 1, current); // Следующий start это i+1
current.pop(); // Отмени
}
}
backtrack(0, []);
return result;
}
console.log(combinations([1, 2, 3, 4], 2));
// Результат: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]Пробуй:
Пример: Контраст с перестановками
Перестановки из {1, 2, 3} выбрать 2 (порядок имеет значение):
(1, 2),(1, 3),(2, 1),(2, 3),(3, 1),(3, 2)— 6 перестановок.
Комбинации из {1, 2, 3} выбрать 2 (порядок не имеет значения):
{1, 2},{1, 3},{2, 3}— 3 комбинации.
Разница: {1, 2} и {2, 1} считаются один раз как комбинация (потому что одно множество), но дважды как перестановки (потому что порядок отличается).
Давай трассировать генерирование всех комбинаций из {1, 2, 3, 4}, выбирая 2.
1
function backtrack(start, current) {
2
if (current.length === k) {
3
result.push([...current]); return;
4
}
5
for (let i = start; i < arr.length; i++) {
6
current.push(arr[i]);
7
backtrack(i + 1, current);
8
current.pop();
9
}
Ключ: индекс start гарантирует мы движемся только вперёд. Когда мы выбираем 1, мы смотрим только 2, 3, 4 (никогда 0 снова). Когда мы выбираем 2, мы смотрим только 3, 4 (никогда 1 снова). Это естественное упорядочение предотвращает дубликаты как {2, 1}.
Время: O(C(n, k) × k), Пространство: O(k)
- Дерево рекурсии имеет глубину k (выбери k элементов).
- На каждом уровне, ветвление уменьшается: n выборов на уровне 0, потом n-1, n-2, и т.д.
- Всего листьев = C(n, k) (количество различных комбинаций).
- Каждый лист записывает одну комбинацию, что требует O(k) времени (копирование k элементов).
- Время = C(n, k) × O(k) = O(C(n, k) × k).
- Пространство (стек вызовов) = O(k) (глубина рекурсии).
Насколько большой C(n, k)?
C(n, k) = n! / (k!(n-k)!) растёт с n но зависит сильно от k.
- C(n, 1) = n (выбери 1 из n).
- C(n, 2) = n(n-1) / 2 (выбери 2 из n).
- C(n, n) = 1 (выбери все).
- Максимум при k = n/2. Для n=20, k=10, это C(20, 10) ≈ 184,756.
Для малого k относительно n, C(n, k) намного меньше чем n!. Например, C(100, 2) = 4,950, но 100! астрономически большой. Это делает комбинации практичными когда k фиксировано и малое.
Обрезание экономит время
Проверка обрезания if (current.length + remaining < k) return; обрезает ветви рано. В худшем случае (k = n/2), обрезание даёт минимальное преимущество, но для фиксированного малого k, оно устраняет множество ветвей быстро.
Сколько комбинаций есть выбирая 2 элемента из набора 5?
Сколько комбинаций выбирая 3 элемента из {1, 2, 3, 4, 5}?
Какая ключевая разница между генерированием перестановок и генерированием комбинаций?
Почему начальный индекс предотвращает дубликатные комбинации?
Что такое C(6, 3)?
Частая ошибка
Ошибка 1: Не копируешь комбинацию. Ты строишь комбинацию в current, и когда ты достигаешь размер k, ты должен скопировать её перед добавлением в result. Если ты добавляешь ссылку, все комбинации в result указывают на один массив. Когда ты попираешь из current, все из них теряют этот элемент.
// НЕПРАВИЛЬНО
if (current.length === k) {
result.push(current); // БАГ: одна ссылка
return;
}
// ПРАВИЛЬНО
if (current.length === k) {
result.push([...current]); // Скопируй массив
return;
}Ошибка 2: Забываешь начальный индекс. Если ты всегда начинаешь цикл с 0, ты генерируешь одну комбинацию много раз в разных порядках.
// НЕПРАВИЛЬНО: начинает с 0 каждый раз, генерирует дубликаты
for (let i = 0; i < arr.length; i++) {
current.push(arr[i]);
backtrack(0, current); // БАГ: следующий start это 0, не i+1
current.pop();
}
// ПРАВИЛЬНО: следующий start это i+1
for (let i = start; i < arr.length; i++) {
current.push(arr[i]);
backtrack(i + 1, current); // Следующий start это i+1
current.pop();
}Ошибка 3: Пропускаешь обрезание. Без проверки обрезания, ты исследуешь ветви что не могут возможно достичь k элементов. Это неэффективно, хотя всё ещё правильно.
// Работает но медленно
for (let i = start; i < arr.length; i++) {
current.push(arr[i]);
backtrack(i + 1, current);
current.pop();
}
// Лучше: обрежь рано
const remaining = arr.length - start;
if (current.length + remaining < k) {
return;
}Начальный индекс и копия не опциональны — без них твой алгоритм падает или производит дубликаты.
Ты генерируешь все комбинации 4 элементов из массива 6. Сколько комбинаций есть, и какая сложность времени?
Комбинации: Генерируй каждый способ выбрать k элементов из n элементов, где порядок не имеет значения. {A, B} и {B, A} — одна комбинация.
Количество: C(n, k) = n! / (k!(n-k)!) — биномиальный коэффициент, также вызывается “n choose k”.
Трюк начального индекса: Чтобы избежать генерирования одной комбинации в разных порядках, требуй ход только вперёд. Раз ты выбираешь arr[i], только рассматривай arr[i+1] и позже. Никогда не ходи назад. Это предотвращает дубликаты и включает обрезание.
Шаблон: На каждом шаге, выбрать включить текущий элемент (и переместить start вперёд на i+1) или пропустить его (всё ещё переместить start на i+1). Рекурсируй пока ты не выбрал k элементов.
Сложность: O(C(n, k) × k) время и O(k) пространство. C(n, k) намного меньше чем n! когда k малое и фиксировано, делая комбинации практичными для задач как “найди все пары” или “найди все тройки”.
Контрасты: Подмножества ветвятся на каждый элемент (2^n выходов), перестановки отслеживают какие элементы используются (n! выходов), комбинации используют начальный индекс чтобы требовать порядок (C(n, k) выходов). Все три используют choose-explore-undo шаблон с разной логикой выбора.