Комбинаторные алгоритмы: генерация и эффективный перебор

Генерация подмножеств и битовые маски

Представьте задачу: у вас есть 20 посылок разного веса, и нужно загрузить курьерский фургон так, чтобы суммарный вес составил ровно 500 килограммов. На бумаге комбинаторный ответ очевиден — число возможных комбинаций равно $2^{20} = 1\,048\,576$. Человек без компьютера потратил бы на выписывание этих вариантов годы, но для процессора миллион операций — дело нескольких миллисекунд. Вопрос лишь в том, как заставить программу перебрать все варианты без избыточных затрат памяти и без путаницы с рекурсией.

Решение кроется в фундаментальном мостике между комбинаторикой и низкоуровневой архитектурой процессоров — битовых масках.

Мостик от множества к числу

Пусть дано базовое множество $S$ из $n$ упорядоченных элементов с индексами от $0$ до $n - 1$:

$$S = \{s_0, s_1, s_2, \dots, s_{n-1}\}$$

Каждое подмножество $A \subseteq S$ однозначно определяется правилом: для каждого элемента $s_i$ мы либо включаем его в $A$, либо нет. Это бинарный выбор:

• $1$, если $s_i \in A$;
• $0$, если $s_i \notin A$.

Последовательность таких нулей и единиц длины $n$ называется характеристическим вектором (или вектором принадлежности). Но последовательность из нулей и единиц — это не что иное, как двоичная запись целого неотрицательного числа.

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

Индекс $i$	$3$	$2$	$1$	$0$
Элемент $s_i$	$\text{D}$	$\text{C}$	$\text{B}$	$\text{A}$
Включение в $A$	$1$	$0$	$1$	$1$

Бинарная цепочка $1011_2$ в десятичной системе счисления равна:

$$1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 8 + 0 + 2 + 1 = 11$$

Ключевой инсайт: Между всеми $2^n$ подмножествами $n$-элементного множества и целыми числами от $0$ до $2^n - 1$ существует взаимно однозначное соответствие (биекция). Пустому множеству $\varnothing$ соответствует число $0$, а всему множеству $S$ — число $2^n - 1$.

Целое число, представляющее подмножество через свои биты, в программировании называют битовой маской (bitmask).

Арсенал побитовых операций

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

1. Сдвиг влево и единичная маска элемента

Выражение 1 << i сдвигает единицу на $i$ разрядов влево, порождая двоичное число, в котором установлен только $i$-й бит (число $2^i$). Это маска для одного элемента $s_i$.

2. Проверка принадлежности элемента ($s_i \in A$)

Чтобы проверить, установлен ли $i$-й бит в маске mask, применяют побитовое «И» (&):

is_present = (mask & (1 << i)) != 0
# Либо проверка выдвижением бита в нулевой разряд:
is_present = ((mask >> i) & 1) == 1

Если $i$-й бит равен нулю, результат побитового умножения на 1 << i даст $0$. Если равен единице — число $2^i$.

3. Добавление элемента ($A \cup \{s_i\}$)

Включение элемента выполняется через побитовое «ИЛИ» (|):

mask = mask | (1 << i)

Операция устанавливает $i$-й бит в $1$, оставляя остальные разряды неизменными.

4. Удаление элемента ($A \setminus \{s_i\}$)

Для сброса бита в $0$ используется побитовое «НЕ» (~), инвертирующее все разряды, и побитовое «И»:

mask = mask & ~(1 << i)

В выражении ~(1 << i) все биты равны единице, кроме $i$-го. Умножение на такую маску гарантированно зануляет $i$-й бит.

5. Симметрическая разность / переключение состояния

Побитовое исключающее «ИЛИ» (^) меняет значение бита на противоположное:

mask = mask ^ (1 << i)

6. Операции над двумя множествами

Теоретико-множественная операция	Побитовый эквивалент	Название
Пересечение: $A \cap B$	mask_A & mask_B	Побитовое И (AND)
Объединение: $A \cup B$	mask_A | mask_B	Побитовое ИЛИ (OR)
Разность: $A \setminus B$	mask_A & ~mask_B	И с инверсией
Симметрическая разность: $A \bigtriangleup B$	mask_A ^ mask_B	Побитовое XOR

Итеративная генерация всех подмножеств

Осознание биекции даёт простейший алгоритм полного перебора: достаточно запустить цикл от $0$ до $2^n - 1$ и для каждого числа восстановить входящие в него элементы.

def generate_all_subsets(elements: list[str]) -> list[list[str]]:
    n = len(elements)
    total_subsets = 1 << n  # 2^n
    all_subsets = []

    for mask in range(total_subsets):
        current_subset = []
        for i in range(n):
            if (mask >> i) & 1:
                current_subset.append(elements[i])
        all_subsets.append(current_subset)

    return all_subsets

Разберём вычислительную сложность алгоритма:

1. Внешний цикл выполняется ровно $2^n$ раз.
2. Внутренний цикл для каждой маски выполняет $n$ итераций, проверяя каждый бит.

Итоговая временная сложность: $O(n \cdot 2^n)$. Пространственная сложность для генерации одного подмножества: $O(1)$ вспомогательной памяти (если элементы сразу обрабатываются, а не сохраняются в список).

Практическое ограничение: размер $n$

В современных 64-битных системах стандартный целочисленный тип вмещает до 64 бит. Это означает, что маска может описывать множество мощностью до $n = 64$.

Однако сложность $O(n \cdot 2^n)$ накладывает жесткие рамки на время:

• При $n = 20$: $2^{20} \approx 10^6$ операций — выполняется за 0.05 секунды.
• При $n = 30$: $2^{30} \approx 10^9$ операций — займет несколько секунд на C++ и десятки секунд на Python.
• При $n = 40$: $2^{40} \approx 1.1 \times 10^{12}$ операций — потребует часов работы суперкомпьютера.

Поэтому метод битовых масок на практике применим при $n \leq 20 \dots 25$ для задач полного перебора.

Решение прикладной задачи: Subset Sum

Вернемся к задаче о загрузке фургона. Пусть дан список весов и целевая масса $W$:

def find_exact_subset(weights: list[int], target_sum: int) -> list[int] | None:
    n = len(weights)
    for mask in range(1 << n):
        current_sum = 0
        for i in range(n):
            if (mask >> i) & 1:
                current_sum += weights[i]

        if current_sum == target_sum:
            return [weights[i] for i in range(n) if (mask >> i) & 1]
    return None

weights = [45, 120, 80, 210, 75, 90]
target = 375
print(find_exact_subset(weights, target))  # [45, 120, 210] -> 45 + 120 + 210 = 375

Код не требует стека рекурсии, легко прерывается при первом найденном совпадении и не расходует лишнюю память.

Продвинутый трюк: перебор всех подмасок заданной маски

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

Наивный путь — перебрать все числа от $0$ до mask и для каждого проверить условие (sub & mask) == sub. Но если mask содержит $k$ единичных бит, число ее подмасок равно $2^k$, в то время как само число mask может достигать $2^n - 1$. Наивный перебор проверит множество заведомо посторонних чисел.

Существует классический битовый трюк, перебирающий строго подмаски в порядке убывания:

submask = mask
while True:
    # Обработка текущей подмаски
    process(submask)
    if submask == 0:
        break
    submask = (submask - 1) & mask

Как работает шаг (submask - 1) & mask?

1. Операция submask - 1 находит самый младший единичный бит в submask, обнуляет его, а все биты младше него превращает в единицы.
2. Последующее побитовое & mask отсекает те младшие единицы, которых изначально не было в родительской маске mask.

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

Сложность перебора подмасок для всех масок

Если мы запустим перебор подмасок для каждой маски от $0$ до $2^n - 1$:

for mask in range(1 << n):
    submask = mask
    while True:
        # шаг обработки
        if submask == 0:
            break
        submask = (submask - 1) & mask

Сколько всего итераций выполнит внутренний цикл суммарно?

Для маски с $k$ установленными битами существует ровно $2^k$ подмасок. Число масок длины $n$ с ровно $k$ единичными битами равно числу сочетаний $\binom{n}{k}$. Следовательно, суммарное число итераций:

$$\sum_{k=0}^{n} \binom{n}{k} 2^k \cdot 1^{n-k} = (2 + 1)^n = 3^n$$

Формула бинома Ньютона доказывает: суммарное время работы составляет $O(3^n)$, а вовсе не $O(4^n)$, как при наивном вложенном переборе всех пар. Для $n = 15$: $3^{15} \approx 1.4 \times 10^7$ действий — вполне под силу уложить в секунду процессорного времени.

Рекурсивный перебор vs Битовые маски

В алгоритмической практике подмножества генерируют двумя путями: через битовые маски или рекурсивным деревом решений (backtracking).

Критерий	Битовые маски	Рекурсивный обход дерева
Реализация	Компактный итеративный цикл	Функция с рекурсивными вызовами
Память	$O(1)$ вспомогательной памяти	$O(n)$ памяти под стек вызовов
Накладные расходы	Минимальные (машинные инструкции)	Вызовы функций, передача параметров
Раннее отсечение ветвей (pruning)	Затруднено (проверяет все маски подряд)	Естественное (не спускаемся в поддерево при переполнении суммы)
Ограничение по размеру	$n \leq 30$ (обычно до 64)	Ограничено глубиной стека (но время растет экспоненциально)

Если пространство поиска необходимо просеивать полностью (проверить абсолютно все $2^n$ состояний или найти оптимальное подмножество при небольшом $n$) — битовые маски вне конкуренции по скорости и чистоте кода. Если же задача позволяет отсекать заведомо тупиковые ветви на ранних шагах (например, сумма уже превысила целевую), эффективнее оказывается поиск с возвратом.

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

Перестановки и алгоритм Нараяны

Перебор $2^n$ подмножеств решался естественным сопоставлением битов числа элементам множества: достаточно было прибавить единицу к счетчику, чтобы получить следующую конфигурацию. Однако если зафиксировать размер выборки и потребовать упорядочить все элементы множества без пропусков и повторений, битовая арифметика бессильна. Для $n = 10$ число перестановок $10! = 3\,628\,800$ уже превосходит $2^{10} = 1024$ более чем в 3500 раз. Как перебрать все $n!$ состояний упорядоченно, не тратя память на стек рекурсии и затрачивая в среднем $O(1)$ операций на переход к следующему состоянию?

Ответом на этот вызов служит алгоритм генерации следующей перестановки в лексикографическом порядке, известный в современной литературе как алгоритм Нараяны.

Лексикографический порядок

Чтобы перебор был детерминированным и исчерпывающим, на множестве перестановок задают линейный порядок. Естественным выбором является порядок словаря — лексикографический порядок.

Пусть даны две различные перестановки $P = (p_1, p_2, \dots, p_n)$ и $Q = (q_1, q_2, \dots, q_n)$ одного и того же мультимножества. Перестановка $P$ предшествует $Q$ ($P < Q$), если в первой позиции $i$, где их элементы различаются, выполняется $p_i < q_i$:

$$i = \min \{ k \mid p_k \neq q_k \}, \quad p_i < q_i$$

Здесь $i$ — первый несовпадающий индекс слева направо; элементы $p_1, \dots, p_{i-1}$ строго совпадают с $q_1, \dots, q_{i-1}$, а знак неравенства на позиции $i$ однозначно задает, какая из двух перестановок идет раньше.

Например, для $n = 3$ на числах $\{1, 2, 3\}$ полный лексикографический порядок формирует строгую цепочку:

$$(1, 2, 3) < (1, 3, 2) < (2, 1, 3) < (2, 3, 1) < (3, 1, 2) < (3, 2, 1)$$

Первая перестановка отсортирована по возрастанию: любой её префикс минимален. Последняя перестановка отсортирована по убыванию: ни один элемент нельзя увеличить, не нарушив допустимый состав чисел.

Задача генератора — по текущей перестановке $P$ найти непосредственного преемника: наименьшую перестановку $Q$, для которой $P < Q$.

Интуиция алгоритма Нараяны

Индийский математик XIV века Нараяна Пандит описал алгоритм, решающий эту задачу за минимальное число сравнений и обменов.

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

Рассмотрим перестановку $P = (1, 3, 5, 4, 2)$.

Хвост $(5, 4, 2)$ уже упорядочен по строгому убыванию. Это означает, что для чисел $\{5, 4, 2\}$ перестановка $(5, 4, 2)$ является локально максимальной: никакая перестановка этих трех элементов не даст значения больше текущего. Значит, изменить только последние три элемента недостаточно — перенести разряд в более старшую позицию неизбежно.

Ближайший элемент слева, который можно увеличить, — это тройка на позиции с индексом $1$ (при 0-индексации), стоящая перед убывающим суффиксом, так как $3 < 5$.

Четыре шага алгоритма Нараяны

Алгоритм состоит из четырех строгих механических действий над массивом $A[0 \dots n-1]$:

Шаг 1. Поиск опорного индекса $i$

Двигаясь справа налево, находим первый индекс $i$, для которого текущий элемент строго меньше следующего:

$$A[i] < A[i + 1]$$

Суффикс $A[i+1 \dots n-1]$ гарантированно не возрастает: $A[i+1] \geq A[i+2] \geq \dots \geq A[n-1]$. Если такого индекса $i$ нет (весь массив отсортирован по невозрастанию), то текущая перестановка — последняя в лексикографическом порядке. Обход завершен.

Шаг 2. Поиск кандидата на замену $j$

В убывающем суффиксе $A[i+1 \dots n-1]$ ищем самый правый элемент, который строго больше $A[i]$:

$$j = \max \{ k \mid A[k] > A[i] \}$$

Поскольку $A[i] < A[i+1]$, такой элемент гарантированно существует (как минимум $k = i+1$). Выбор самого правого элемента обеспечивает минимальный возможный шаг прироста: среди всех чисел хвоста, превышающих $A[i]$, выбирается наименьшее.

Шаг 3. Обмен элементов (swap)

Меняем местами $A[i]$ и $A[j]$:

$$\mathrm{swap}(A[i], A[j])$$

После обмена суффикс $A[i+1 \dots n-1]$ сохраняет свойство невозрастания.

Шаг 4. Разворот суффикса (reverse)

Разворачиваем суффикс $A[i+1 \dots n-1]$ слева направо.

Поскольку суффикс был отсортирован по убыванию, после обращения он становится отсортирован по возрастанию. Это обеспечивает минимальное лексикографическое значение хвоста при новом значении на позиции $i$.

Проследим трансформацию на векторе $(1, 3, 5, 4, 2)$:

1. Справа налево находим пару: $3 < 5$. Опорный индекс $i = 1$ ($A[i] = 3$).
2. В суффиксе $(5, 4, 2)$ ищем справа налево элемент, больший $3$. Это $4$ с индексом $j = 3$ ($A[j] = 4$).
3. Меняем местами $A[1]$ и $A[3]$: получаем $(1, 4, 5, 3, 2)$. Суффикс $(5, 3, 2)$ по-прежнему отсортирован по убыванию.
4. Разворачиваем суффикс с индекса $2$ до конца: $(1, 4, 2, 3, 5)$.

Результат $(1, 4, 2, 3, 5)$ — строго следующий элемент в лексикографическом порядке.

Реализация генератора на Python

В стандартной библиотеке C++ данный алгоритм реализован в функции std::next_permutation. Напишем генератор на Python, преобразующий массив на месте (in-place):

def next_permutation(a: list) -> bool:
    """
    Преобразует список a в следующую лексикографическую перестановку.
    Возвращает True, если следующая перестановка найдена,
    или False, если массив уже был максимальным (в этом случае он разворачивается в исходный).
    """
    n = len(a)
    if n <= 1:
        return False

    # Шаг 1: Ищем первый элемент a[i] < a[i + 1] с конца
    i = n - 2
    while i >= 0 and a[i] >= a[i + 1]:
        i -= 1

    # Если массив уже упорядочен по убыванию — это последняя перестановка
    if i < 0:
        a.reverse()
        return False

    # Шаг 2: Ищем наименьший a[j] > a[i] в суффиксе (самый правый)
    j = n - 1
    while a[j] <= a[i]:
        j -= 1

    # Шаг 3: Меняем a[i] и a[j]
    a[i], a[j] = a[j], a[i]

    # Шаг 4: Разворачиваем суффикс a[i + 1:]
    left = i + 1
    right = n - 1
    while left < right:
        a[left], a[right] = a[right], a[left]
        left += 1
        right -= 1

    return True

Используя эту функцию, полный перебор массива размера $n$ выполняется циклом с минимальным расходом памяти:

elements = [1, 2, 3]
print(elements)
while next_permutation(elements):
    print(elements)

Вывод:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Временная сложность и амортизированный анализ

В худшем случае один вызов next_permutation требует $O(n)$ операций — например, при переходе от $(1, n, n-1, \dots, 2)$ к $(2, 1, 3, \dots, n)$ просматривается и разворачивается почти весь массив.

Однако какова средняя стоимость шага при генерации всех $n!$ перестановок?

Оценим длину разворачиваемого суффикса:

• Ровно в половине всех перестановок последний элемент больше предпоследнего ($a[n-2] < a[n-1]$). В этих случаях $i = n - 2$, суффикс состоит из одного элемента, и шаг 4 требует $O(1)$ действий.
• В $1/3$ всех случаев ($2/3$ оставшихся) длина суффикса равна $2$.
• В общем виде суффикс длины $k$ разворачивается с вероятностью $k / (k + 1)!$.

Формально суммарное число элементарных операций на прохождение всех $n!$ перестановок выражается через подсчет числа перестановок с убывающим суффиксом фиксированной длины:

Среднее число операций на одну итерацию алгоритма Нараяны ограничено константой:

$$T_{\text{avg}} = O(1)$$

Полный перебор всех $n!$ перестановок занимает $O(n \cdot n!)$ времени при выводе каждой перестановки или $O(n!)$ времени, если только производить инкремент без поэлементного копирования.

Это делает алгоритм Нараяны оптимальным: дополнительная память строго $O(1)$ (нет стека вызовов, перестановка модифицируется in-place), а время генерации очередного объекта амортизированно константно.

Работа с повторяющимися элементами

Критическое преимущество алгоритма Нараяны над рекурсивным наивным перебором — естественная обработка мультимножеств (массивов с одинаковыми числами).

Если во входном массиве есть дубликаты, например $[1, 2, 2]$, то общее число уникальных перестановок задается формулой полиномиального коэффициента:

$$P(n_1, n_2, \dots, n_k) = \frac{n!}{n_1! \, n_2! \dots n_k!}$$

Для массива $[1, 2, 2]$ число перестановок равно $3! / (1! \cdot 2!) = 3$.

Если в шаге 1 искать $A[i] < A[i+1]$, а в шаге 2 строго $A[j] > A[i]$, то:

1. Алгоритм никогда не генерирует дублирующиеся перестановки.
2. Каждая уникальная перестановка создается ровно один раз.
3. Промежуточные холостые шаги отсутствуют.

Массив	Перестановки без повторений	Итоговое число шагов
[1, 2, 3]	(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)	6
[1, 1, 2]	(1,1,2), (1,2,1), (2,1,1)	3
[1, 2, 2]	(1,2,2), (2,1,2), (2,2,1)	3
[2, 2, 2]	(2,2,2)	1

Применение: Решение задачи коммивояжёра (TSP)

Перебор перестановок применяется в задачах оптимизации на графах, где важен точный порядок обхода вершин.

Классический пример — симметричная задача коммивояжёра (Traveling Salesperson Problem): найти маршрут минимальной длины, проходящий через все города из списка $\{0, 1, \dots, n-1\}$ ровно по одному разу и возвращающийся в исходную точку.

Пусть число городов $n = 5$, а матрица расстояний $D$ задана таблицей:

dist = [
    [0, 10, 8, 9, 7],
    [10, 0, 10, 5, 6],
    [8, 10, 0, 8, 9],
    [9, 5, 8, 0, 6],
    [7, 6, 9, 6, 0]
]

Поскольку маршрут циклический, начальный город можно зафиксировать (например, город $0$). Это сокращает пространство перебора с $n!$ до $(n - 1)!$. Перебирать следует только перестановки оставшихся вершин $\{1, 2, \dots, n-1\}$.

def solve_tsp(dist_matrix: list[list[int]]) -> tuple[int, list[int]]:
    num_cities = len(dist_matrix)
    # Фиксируем начальный город 0, перебираем перестановки остальных
    route_tail = list(range(1, num_cities))

    best_cost = float('inf')
    best_route = []

    while True:
        # Полный маршрут: 0 -> route_tail -> 0
        current_route = [0] + route_tail + [0]
        current_cost = 0

        for k in range(num_cities):
            u = current_route[k]
            v = current_route[k + 1]
            current_cost += dist_matrix[u][v]

        if current_cost < best_cost:
            best_cost = current_cost
            best_route = current_route[:]

        if not next_permutation(route_tail):
            break

    return best_cost, best_route

cost, route = solve_tsp(dist)
print(f"Минимальная стоимость: {cost}, маршрут: {route}")
# Вывод: Минимальная стоимость: 34, маршрут: [0, 2, 3, 1, 4, 0]

Для $n \leq 11$ такой подход гарантированно находит точный оптимум за доли секунды ($10! \approx 3.6 \times 10^6$ итераций), не требуя дополнительной памяти и исключая риск переполнения стека рекурсии.

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

Генерация сочетаний и размещений

Перебор всех подмножеств давал нам $2^n$ вариантов, а полный перебор перестановок требовал факториального времени $n!$. Однако в прикладных задачах чаще возникает более узкое требование: выбрать ровно $k$ элементов из $n$ доступных ресурсов. Если порядок выбора не имеет значения (например, выбор $k$ серверов из кластера для репликации данных), мы работаем с сочетаниями. Если же порядок критичен (например, назначение $k$ задач на $k$ уникальных исполнителей из пула размера $n$), речь идёт о размещениях.

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

Каноническое представление сочетаний

Сочетанием из $n$ по $k$ называется неупорядоченный набор из $k$ различных элементов, выбранных из $n$-элементного множества. Количество таких наборов задаётся биномиальным коэффициентом:

$$\binom{n}{k} = \frac{n!}{k!(n - k)!}$$

Поясним смысл каждого множителя. Числитель $n!$ задаёт число всех способов упорядочить $n$ объектов. Факториал $(n - k)!$ в знаменателе устраняет порядок среди тех $(n - k)$ элементов, которые мы решили не брать, превращая факториал в число упорядоченных выборок длины $k$. Наконец, факториал $k!$ «склеивает» все перестановки внутри уже выбранной группы, так как порядок элементов внутри сочетания роли не играет. Например, при выборе $k = 3$ узлов из $n = 5$ доступных (пронумерованных от $1$ до $5$) формула даёт:

$$\binom{5}{3} = \frac{5 \cdot 4 \cdot 3}{3 \cdot 2 \cdot 1} = 10$$

Чтобы комбинаторные объекты можно было перебирать последовательно и без дубликатов, их необходимо канонизировать. Стандартный подход — зафиксировать базовое множество как строго возрастающую последовательность индексов $\{1, 2, \dots, n\}$ (или с нуля $\{0, 1, \dots, n - 1\}$) и представлять каждое сочетание в виде строго возрастающего кортежа:

$$c = (c_1, c_2, \dots, c_k), \quad 1 \leq c_1 < c_2 < \dots < c_k \leq n$$

Строгий порядок внутри кортежа устраняет неоднозначность: наборы $(1, 3, 2)$ и $(3, 1, 2)$ сводятся к единственному каноническому виду $(1, 2, 3)$.

Лексикографический порядок сочетаний

Каноническое представление позволяет упорядочить сочетания лексикографически. Первым (минимальным) сочетанием всегда будет набор из первых $k$ натуральных чисел:

$$c_{\min} = (1, 2, \dots, k)$$

Последним (максимальным) сочетанием станет «хвост» из наибольших $k$ чисел:

$$c_{\max} = (n - k + 1, n - k + 2, \dots, n)$$

Обратите внимание на верхнюю границу для каждого разряда. Элемент $c_k$ на последней позиции может достигать значения $n$. Предшествующий ему элемент $c_{k-1}$ обязан быть строго меньше $c_k$, а значит, его максимальное значение — $n - 1$. В общем виде для позиции $i$ (где $i \in \{1, \dots, k\}$):

$$c_i \leq n - k + i$$

Если для некоторого индекса $i$ текущее значение достигло предельной планки $n - k + i$, увеличить его в рамках текущего префикса уже невозможно: для последующих элементов просто не хватит оставшихся чисел из отрезка $[1, n]$.

Алгоритм перехода к следующему сочетанию

Чтобы перейти от текущего сочетания $c$ к непосредственно следующему в лексикографическом порядке, выполняется детерминированная процедура:

1. Поиск опорного индекса: сканируем кортеж справа налево (от $i = k$ до $1$) и ищем первый элемент, который ещё не достиг своего максимума, то есть $c_i < n - k + i$. Если такого индекса нет, текущее сочетание уже максимально — генерация завершена.
2. Инкремент опоры: увеличиваем найденный элемент на единицу: $c_i \leftarrow c_i + 1$.
3. Минимизация суффикса: все элементы правее позиции $i$ (индексы $j$ от $i + 1$ до $k$) устанавливаем в минимально возможные допустимые значения, сохраняя строгое возрастание: $c_j \leftarrow c_{j-1} + 1$.

Разберём переход на конкретном примере: пусть $n = 6$, $k = 4$, а текущее сочетание равно $(1, 3, 5, 6)$.

• Проверяем позицию 4: $c_4 = 6$, а максимальный предел $6 - 4 + 4 = 6$. Позиция насыщена.
• Проверяем позицию 3: $c_3 = 5$, предел $6 - 4 + 3 = 5$. Позиция насыщена.
• Проверяем позицию 2: $c_2 = 3$, предел $6 - 4 + 2 = 4$. Найдена опора $i = 2$, так как $3 < 4$.
• Увеличиваем опору: $c_2 \leftarrow 4$.
• Выравниваем суффикс: $c_3 \leftarrow c_2 + 1 = 5$, затем $c_4 \leftarrow c_3 + 1 = 6$.
• Результат: следующее сочетание — $(1, 4, 5, 6)$.

Реализуем итератор на Python, работающий с $0$-индексацией:

def next_combination(c: list[int], n: int) -> bool:
    """Трансформирует c in-place в следующее сочетание из n элементов.

    Элементы c находятся в диапазоне 0..n-1 и строго возрастают.
    Возвращает False, если текущее сочетание было последним.
    """
    k = len(c)
    i = k - 1
    # Ищем самый правый элемент, который можно увеличить.
    # Для 0-индексации верхняя граница: n - k + i
    while i >= 0 and c[i] == n - k + i:
        i -= 1

    if i < 0:
        return False

    c[i] += 1
    for j in range(i + 1, k):
        c[j] = c[j - 1] + 1

    return True

def combinations(n: int, k: int):
    """Генератор всех сочетаний из n по k в лексикографическом порядке."""
    if k < 0 or k > n:
        return

    c = list(range(k))
    yield tuple(c)

    while next_combination(c, n):
        yield tuple(c)

Сложность шага в худшем случае составляет $O(k)$, когда приходится переписывать весь суффикс длины $k$. Однако в среднем суффикс изменяется всего на несколько элементов, поэтому амортизированная сложность перехода близка к $O(1)$. Память алгоритма составляет $O(k)$ для хранения одного рабочего вектора.

Побитовая генерация: алгоритм Госпера (Gosper's Hack)

Когда общее число элементов $n$ не превышает разрядности машинного слова (обычно $n \leq 64$), сочетания можно представить характеристическими векторами — битовыми масками. Поскольку размер сочетания строго фиксирован и равен $k$, задача сводится к генерации всех двоичных чисел длины $n$, содержащих ровно $k$ установленных единиц (чисел с постоянным весом Хэмминга).

Перебирать все числа от $0$ до $2^n - 1$ и отфильтровывать те, у которых число единиц равно $k$, крайне неэффективно: при $n = 30$ и $k = 4$ мы бы проверили свыше миллиарда чисел, хотя искомых сочетаний всего $\binom{30}{4} = 27\,405$.

Билл Госпер в 1972 году предложил способ вычисления следующего лексикографического числа с тем же количеством бит ровно за несколько элементарных битовых операций:

def gospers_hack(n: int, k: int):
    """Генерирует все битовые маски длины n с k установленными битами."""
    if k == 0:
        yield 0
        return
    if k > n:
        return

    # Начальная маска: k единиц в младших битах, то есть (1 << k) - 1
    mask = (1 << k) - 1
    limit = 1 << n

    while mask < limit:
        yield mask
        # 1. Извлекаем младший единичный бит
        c = mask & -mask
        # 2. Прибавляем его к маске: блок младших единиц "схлопывается",
        # бит слева от него становится 1
        r = mask + c
        # 3. Восстанавливаем оставшиеся единицы в крайних правых разрядах
        mask = (((r ^ mask) >> 2) // c) | r

Разберём математику этого трюка по шагам:

• Выражение c = mask & -mask изолирует младший установленный бит (lowest set bit). Это работает благодаря представлению отрицательных чисел в дополнительном коде: -mask == (~mask) + 1.
• Операция r = mask + c выполняет перенос: младшая непрерывная группа единиц обнуляется, а бит непосредственно слева от этой группы устанавливается в 1. Мы только что продвинули старшую единицу группы на один разряд влево.
• Однако суммирование уничтожило информацию о том, сколько именно единиц было в младшей группе. Разность r ^ mask выделяет изменённые биты: это перенесённый бит плюс все исчезнувшие биты группы.
• Сдвиг (r ^ mask) >> 2 и целочисленное деление на c нормализуют оставшиеся единицы: они смещаются в самые младшие разряды числа.
• Побитовое ИЛИ (| r) объединяет новую старшую позицию с аккуратно сдвинутыми вправо оставшимися единицами.

Сложность одного перехода в алгоритме Госпера составляет $O(1)$ без скрытых констант и ветвлений на уровне процессора. Это идеальный инструмент для задач низкоуровневой оптимизации.

Размещения: добавление порядка

Перейдём ко второму классу объектов. Размещением из $n$ по $k$ называется упорядоченный кортеж из $k$ различных элементов, выбранных из базового множества мощности $n$.

Количество размещений обозначается $A_n^k$ (или $P(n, k)$) и выражается формулой:

$$A_n^k = \frac{n!}{(n - k)!} = n(n - 1)\dots(n - k + 1)$$

Сравним эту формулу с выражением для сочетаний:

$$A_n^k = \binom{n}{k} \cdot k!$$

Это фундаментальное тождество задаёт архитектуру алгоритмов перебора:

Любое размещение длины $k$ может быть однозначно факторизовано на два независимых шага: выбор неупорядоченного подмножества размера $k$ (сочетание) и выбор конкретного порядка следования этих $k$ элементов (перестановка).

Параметр	Подмножества	Сочетания	Размещения	Перестановки
Длина выборки	Произвольная ($0 \dots n$)	Фиксированная ($k$)	Фиксированная ($k$)	Полная ($n$)
Учёт порядка	Нет	Нет	Да	Да
Число вариантов	$2^n$	$\binom{n}{k}$	$A_n^k = \binom{n}{k} \cdot k!$	$n!$

Алгоритм генерации через композицию

Опираясь на эту связь, мы можем скомпоновать генератор размещений без написания сложной новой логики. Для каждого сгенерированного сочетания индексов мы просто запускаем алгоритм Нараяны для получения всех $k!$ перестановок этих индексов.

Однако если требуется сгенерировать размещения строго в общем лексикографическом порядке (например, для $n = 4, k = 2$: сначала $(0, 1), (0, 2), (0, 3)$, затем $(1, 0), (1, 2), \dots$), наивная композиция «сочетания, а затем их перестановки» нарушит глобальную сортировку: после $(0, 1)$ сразу пойдёт $(1, 0)$, а не $(0, 2)$.

Для соблюдения глобального лексикографического порядка размещения генерируют как $k$-префиксы перестановок $n$-элементного множества либо с помощью рекурсивного поиска с возвратом:

def generate_arrangements(n: int, k: int):
    """Генерирует все размещения из n по k в строгом лексикографическом порядке."""
    current = []
    used = [False] * n

    def backtrack():
        if len(current) == k:
            yield tuple(current)
            return

        for val in range(n):
            if not used[val]:
                used[val] = True
                current.append(val)
                yield from backtrack()
                current.pop()
                used[val] = False

    yield from backtrack()

Вектор used размера $n$ за $O(1)$ отслеживает занятость элементов. Глубина рекурсии строго ограничена величиной $k$, поэтому накладные расходы по памяти составляют всего $O(n + k) = O(n)$.

Каждый лист дерева рекурсии соответствует ровно одному валидному размещению, а внутренние узлы дерева не содержат тупиковых путей: на каждом шаге мы выбираем любой из ещё свободных элементов, которых гарантированно не менее $n - k + 1 > 0$. Следовательно, на генерацию одного размещения уходит $O(k)$ операций в худшем случае и $O(1)$ в амортизированном анализе на каждый шаг спуска/подъёма.

Разбиения чисел и слагаемые

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

Но что происходит, когда объекты физически неотличимы друг от друга? Представьте распределение 10 абсолютно одинаковых вычислительных потоков между несколькими серверами, размен 100 рублей монетами или выделение одинаковых блоков оперативной памяти под задачи. Здесь нас больше не интересует, какой именно поток куда попал — имеет значение лишь количество ресурсов в каждой группе.

Задача перестаёт быть выбором подмножеств и превращается в разбиение целого положительного числа $n$ на сумму положительных целых слагаемых.

Составы и разбиения: когда порядок имеет значение

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

Состав числа (композиция, ordered partition) — представление целого положительного числа $n$ в виде упорядоченной суммы положительных целых чисел.

Разбиение числа (integer partition) — представление целого положительного числа $n$ в виде неупорядоченной суммы положительных целых чисел.

Пусть $n = 4$. Если мы распределяем 4 задачи по трём разным серверам (сервер $A$, сервер $B$, сервер $C$), то распределение $3 + 1 + 0$ и распределение $1 + 3 + 0$ — это совершенно разные исходы. Это составы числа. Если же сервера безымянные и важна лишь группировка задач, то $3 + 1$ и $1 + 3$ — это одно и то же разбиение числа 4.

Разница между ними наглядна при сопоставлении свойств:

Критерий	Составы числа (Compositions)	Разбиения числа (Partitions)
Учёт порядка	Порядок слагаемых важен: $3 + 1 \neq 1 + 3$	Порядок слагаемых безразличен: $3 + 1 \equiv 1 + 3$
Каноническая форма	Любая последовательность $(a_1, a_2, \dots, a_k)$	Невозрастающая цепочка $\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_k \geq 1$
Количество для числа $n$	Ровно $2^{n-1}$ (экспоненциальный рост)	Функция разбиений $p(n)$ (субэкспоненциальный рост)
Связь с базовыми структурами	Сводится к битовым маскам и сочетаниям	Требует специализированных правил перехода

Для составов числа работает классический комбинаторный метод «перегородок» (stars and bars). Представим число $n$ как ряд из $n$ единиц:

$$1 \quad 1 \quad 1 \quad \dots \quad 1$$

Между этими единицами есть ровно $n - 1$ позиция для разделителей. Если мы хотим разбить число $n$ на $k$ слагаемых, нам достаточно выбрать любые $k - 1$ позиций из доступных $n - 1$. Количество способов сделать это равно числу сочетаний $\binom{n-1}{k-1}$. Если же число слагаемых не фиксировано, на каждой из $n - 1$ позиций мы можем либо поставить разделитель, либо нет. Это даёт ровно $2^{n-1}$ всевозможных составов, генерация которых тривиально сводится к уже изученному перебору битовых масок длины $n - 1$.

С разбиениями чисел всё иначе: поскольку порядок не важен, перестановки одних и тех же слагаемых склеиваются. Чтобы каждое разбиение генерировалось ровно один раз, вводят каноническое правило: слагаемые обязаны идти в порядке невозрастания.

Геометрия разбиений: диаграммы Феррерса и сопряжение

Чтобы оперировать разбиениями структурно, математик Норман Феррерс предложил визуализировать их в виде точечных сеток, а Альфред Юнг развил эту идею до клеток (диаграмм Юнга).

Пусть разбиение числа $n = 14$ задано кортежем $\lambda = (5, 4, 3, 2)$. Изобразим его строками из точек или квадратов, выровненными по левому краю:

Диаграмма не просто иллюстрирует разбиение — она задаёт геометрическую операцию транспонирования (отражения относительно главной диагонали). Если прочитать столбцы диаграммы вместо строк, мы получим новое разбиение того же самого числа $n$:

Сопряжённое (транспонированное) разбиение $\lambda^*$ получается заменой строк диаграммы Феррерса на её столбцы. Длина $i$-й строки сопряжённого разбиения равна количеству строк исходного разбиения, длина которых не меньше $i$.

Для нашего примера $\lambda = (5, 4, 3, 2)$:

• 1-й столбец содержит 4 клетки;
• 2-й столбец содержит 4 клетки;
• 3-й столбец содержит 3 клетки;
• 4-й столбец содержит 2 клетки;
• 5-й столбец содержит 1 клетку.

Получаем сопряжённое разбиение $\lambda^* = (4, 4, 3, 2, 1)$. Сумма слагаемых осталась прежней: $4 + 4 + 3 + 2 + 1 = 14$.

Из этого геометрического факта мгновенно следует фундаментальная двойственность, которая в алгоритмах позволяет сокращать пространство перебора в разы:

Число разбиений числа $n$ ровно на $k$ слагаемых равно числу разбиений $n$, в которых наибольшее слагаемое в точности равно $k$.

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

Итеративная генерация в лексикографическом порядке

Как перебрать все разбиения числа $n$ без повторений и без построения промежуточного дерева рекурсии в памяти? Для этого зададим строгий линейный порядок. Договоримся перечислять разбиения в обратном лексикографическом порядке — от самого «крупного» разбиения к самому «мелкому».

Для $n = 5$ этот порядок выглядит так:

1. $(5)$
2. $(4, 1)$
3. $(3, 2)$
4. $(3, 1, 1)$
5. $(2, 2, 1)$
6. $(2, 1, 1, 1)$
7. $(1, 1, 1, 1, 1)$

Стартовое состояние всегда очевидно: кортеж из одного элемента $(n)$. Финальное — кортеж из $n$ единиц. Вся задача генератора сводится к одному шагу: имея текущее разбиение $\lambda$, детерминированно получить следующее за минимальное время.

Механика перехода к следующему разбиению

Посмотрим на переход от $(4, 1)$ к $(3, 2)$ или от $(3, 1, 1)$ к $(2, 2, 1)$. Принцип похож на алгоритм Нараяны: мы должны изменить суффикс текущего вектора так, чтобы уменьшить его лексикографический вес минимально возможным шагом.

Алгоритм выполняет три механических действия:

1. Поиск опорного элемента: сканируем текущее разбиение справа налево и находим самый правый элемент, который строго больше 1. Пусть он находится на позиции $idx$. Все элементы правее него — гарантированно единицы.
2. Уменьшение опоры: уменьшаем найденный элемент на 1: $\lambda[idx] \leftarrow \lambda[idx] - 1$.
3. Жадная упаковка остатка: подсчитываем сумму, которая «освободилась» (уменьшение на 1 плюс все единицы, стоявшие справа). Эту сумму необходимо распределить по позициям правее $idx$ блоками максимально возможного размера, но не превышающими новый $\lambda[idx]$, чтобы сохранить инвариант невозрастания $\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_k$.

Проследим этот шаг на примере $n = 8$ и текущего состояния $\lambda = (4, 2, 1, 1)$:

• Правее всех стоит элемент $> 1$ — это двойка на индексе 1 (значение 2).
• Уменьшаем её на 1: теперь на позиции 1 стоит 1.
• Собираем резерв суммы: была отнята 1 от двойки, плюс две единицы из хвоста. Итого доступный остаток $R = 1 + 1 + 1 = 3$.
• Ограничение сверху для новых слагаемых: они не могут быть больше $\lambda[1] = 1$.
• Упаковываем 3 единицами: получаем три единицы.
• Итог: $(4, 1, 1, 1, 1)$.

А теперь применим шаг к $(4, 1, 1, 1, 1)$:

• Правый элемент $> 1$ — это четвёрка на индексе 0.
• Уменьшаем её: $\lambda[0] = 3$.
• Освобождённый остаток: $1 + (1 + 1 + 1 + 1) = 5$.
• Ограничение сверху: слагаемые не могут превышать 3.
• Жадная упаковка: берём слагаемое 3 (остаток $5 - 3 = 2$). Следующее слагаемое не может превышать 3, берём оставшиеся 2.
• Итог: $(3, 3, 2)$. Никаких промежуточных единиц не потеряно, сумма в точности равна 8, порядок строго сохранён.

Программная реализация генератора

Реализуем итератор на Python, выполняющий этот переход in-place на динамическом массиве:

def integer_partitions(n: int):
    """
    Генерирует все разбиения целого положительного числа n
    в обратном лексикографическом порядке.
    """
    if n <= 0:
        return

    # Начальное состояние: одно слагаемое, равное n
    partition = [n]
    yield list(partition)

    while True:
        # Шаг 1: ищем самый правый элемент > 1
        idx = len(partition) - 1
        while idx >= 0 and partition[idx] == 1:
            idx -= 1

        # Если элементов > 1 не осталось, мы дошли до (1, 1, ..., 1)
        if idx < 0:
            break

        # Шаг 2: уменьшаем найденный опорный элемент
        partition[idx] -= 1
        val = partition[idx]

        # Подсчитываем сумму сброшенного хвоста
        # (1 от декремента + количество единиц справа: len - 1 - idx)
        remainder = (len(partition) - 1 - idx) + 1

        # Отрезаем старый хвост из единиц
        del partition[idx + 1:]

        # Шаг 3: жадно заполняем остаток блоками размера val
        while remainder > val:
            partition.append(val)
            remainder -= val
        partition.append(remainder)

        yield list(partition)

Проверим работу генератора для $n = 6$:

for p in integer_partitions(6):
    print(" + ".join(map(str, p)))

Вывод программы демонстрирует строгую последовательность:

6
5 + 1
4 + 2
4 + 1 + 1
3 + 3
3 + 2 + 1
3 + 1 + 1 + 1
2 + 2 + 2
2 + 2 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1

Ровно 11 разбиений. Каждое сгенерировано без единой аллокации лишней памяти и без возвратов рекурсивного стека.

Сколько всего существует разбиений? Скорость роста $p(n)$

При оценке сложности комбинаторных алгоритмов программисты привыкли к двум крайностям: экспоненте $2^n$ (для подмножеств) и факториалу $n!$ (для перестановок). Из-за этого возникает ложное ощущение, что перебор слагаемых для $n = 50$ или $n = 100$ моментально подвесит вычислительную систему.

Однако функция количества разбиений $p(n)$ ведёт себя принципиально иначе. Её асимптотику в 1918 году вывели Годфри Харди и Сриниваса Рамануджан:

$$p(n) \sim \frac{1}{4n\sqrt{3}} \exp\left(\pi \sqrt{\frac{2n}{3}}\right) \quad \text{при} \quad n \to \infty$$

Здесь показатель экспоненты растёт не пропорционально $n$, а пропорционально $\sqrt{n}$. Это так называемый субэкспоненциальный рост.

Давайте разберём, что даёт этот корень на практике:

• Для $n = 10$: $2^{10} = 1024$, а $p(10) = 42$.
• Для $n = 30$: $2^{30} \approx 10^9$ (перебор на пределе секунды), а $p(30) = 5604$ (доли миллисекунды).
• Для $n = 50$: $2^{50} \approx 1.12 \times 10^{15}$ (наивный перебор подмножеств не завершится при нашей жизни), тогда как $p(50) = 204\,226$ — этот объём перебирается алгоритмом за несколько десятых долей секунды!
• Для $n = 100$: $p(100) = 190\,569\,292 \approx 1.9 \times 10^8$ — вполне посильный объём для оптимизированного цикла на C++ или Rust за 1–2 секунды.

Благодаря этому свойству задачи оптимизации, сводящиеся к разбиению неразличимых ресурсов, поддаются полному прямому перебору при значениях параметров, совершенно недостижимых для задач на графах или множествах.

Практический каркас: генерация с ограничениями

В реальных олимпиадных и прикладных задачах редко требуется выдать абсолютно все разбиения числа. Обычно накладываются технологические фильтры:

1. Разбиение на слагаемые из фиксированного набора номиналов (задача о размене монет — Coin Change).
2. Разбиение на слагаемые не более чем определённой длины (распределение ресурсов по $k$ серверам).
3. Разбиение на строго нечётные или строго различные слагаемые.

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

def partitions_bounded(n: int, max_val: int, max_parts: int):
    """
    Генерирует разбиения числа n, содержащие не более max_parts слагаемых,
    где каждое слагаемое не превосходит max_val.
    """
    def backtrack(remaining_sum: int, limit: int, current: list):
        if remaining_sum == 0:
            yield list(current)
            return

        # Если исчерпан лимит на количество слагаемых
        if len(current) == max_parts:
            return

        # Следующее слагаемое не может превышать limit и remaining_sum
        upper_bound = min(remaining_sum, limit)
        for val in range(upper_bound, 0, -1):
            # Отсечение ветви: даже если мы возьмем оставшиеся (max_parts - len) слагаемых
            # величиной val, сможем ли набрать remaining_sum?
            if val * (max_parts - len(current)) < remaining_sum:
                break

            current.append(val)
            yield from backtrack(remaining_sum - val, val, current)
            current.pop()

    yield from backtrack(n, max_val, [])

Обратите внимание на проверку val * (max_parts - len(current)) < remaining_sum. Это классический пример отсечения ветвей: если максимальный потенциал оставшихся слотов меньше требуемой суммы, цикл мгновенно прерывается оператором break, срезая целые бесперспективные поддеревья поиска.

Мы научились генерировать разбиения чисел последовательно — от первого до последнего. Но что делать, если пространство комбинаторных объектов колоссально, и нам требуется мгновенно вычислить объект с порядковым номером 1 000 000 000, не совершая миллиард промежуточных шагов? Эту задачу решает ранжирование и нумерация, к которым мы перейдём в следующей главе.

Нумерация и ранжирование комбинаторных объектов

Представьте задачу: на распределённом вычислительном кластере из 1000 серверов нужно параллельно проверить все перестановки длины $n = 14$. Всего их $14! = 87\,178\,291\,200$ (более 87 миллиардов). Если заставить каждую ноду запускать алгоритм Нараяны с самого начала и отсчитывать свои 87 миллионов перестановок последовательно, система потратит часы лишь на холостой перебор. Как мгновенно получить $50\,000\,000\,000$-ю перестановку, не перебирая предыдущие сорок девять миллиардов?

Решение этой задачи опирается на взаимно-однозначное соответствие между натуральными числами от $0$ до $N-1$ и комбинаторными объектами заданного типа.

Ранжирование (ranking) — алгоритмическое отображение комбинаторного объекта в его порядковый номер (ранг) в каноническом лексикографическом порядке.

Деранжирование, или нумерация (unranking) — обратная операция: восстановление комбинаторного объекта по его номеру без генерации всех предшествующих элементов.

Если для подмножеств такое отображение тривиально — это обычная двоичная запись числа от $0$ до $2^n - 1$, где $i$-й бит указывает на наличие $i$-го элемента, — то для перестановок и сочетаний требуется принципиально иной математический аппарат.

Перестановки и факториальная система счисления

Чтобы восстановить перестановку по номеру или найти её индекс, классическая позиционная десятичная или двоичная система не подходит: у нас меняется количество доступных вариантов на каждом шаге. На первой позиции может стоять любой из $n$ элементов, на второй — любой из оставшихся $n-1$, на третьей — из $n-2$ и так далее.

Каждому выбору первого элемента соответствует блок ровно из $(n-1)!$ перестановок. Следовательно, если упорядочить все перестановки лексикографически, номер перестановки можно естественным образом разложить по факториальному базису.

Любое целое число $R$ в диапазоне от $0$ до $n! - 1$ единственным образом представляется в виде:

$$R = d_{n-1} (n-1)! + d_{n-2} (n-2)! + \dots + d_1 \cdot 1! + d_0 \cdot 0!$$

где каждый коэффициент $d_k$ удовлетворяет строгому ограничению: $0 \le d_k \le k$.

Разберём элементы формулы:

• $R$ — лексикографический номер (ранг) перестановки (нумерация с 0).
• $k!$ — вес $k$-го разряда факториальной системы.
• $d_k$ — цифра в $k$-м разряде. Она указывает, сколько ещё неиспользованных элементов, меньших текущего, было пропущено при выборе символа на текущую позицию.

Вектор коэффициентов $(d_{n-1}, d_{n-2}, \dots, d_1, d_0)$ называют кодом Лемера (Lehmer code).

От перестановки к номеру (Ranking)

Чтобы определить ранг перестановки $P = (p_1, p_2, \dots, p_n)$, нужно вычислить компоненты её кода Лемера. Коэффициент $d_{n-i}$ равен количеству элементов правее позиции $i$, которые строго меньше $p_i$:

$$d_{n-i} = \sum_{j=i+1}^{n} [p_j < p_i]$$

Здесь выражение в скобках Айверсона $[p_j < p_i]$ равно $1$, если условие истинно, и $0$ в противном случае.

Рассмотрим перестановку $P = (3, 1, 4, 2)$ элементов множества $\{1, 2, 3, 4\}$ ($n = 4$):

1. Для $p_1 = 3$: правее стоят $1, 4, 2$. Меньше трёх ровно два числа ($1$ и $2$). Значит, $d_3 = 2$.
2. Для $p_2 = 1$: правее стоят $4, 2$. Меньше единицы чисел нет. Значит, $d_2 = 0$.
3. Для $p_3 = 4$: правее стоит $2$. Число $2 < 4$. Значит, $d_1 = 1$.
4. Для последнего элемента $p_4 = 2$: правее ничего нет, $d_0 = 0$.

Код Лемера: $(2, 0, 1, 0)$. Переводим его в ранг:

$$R = 2 \cdot 3! + 0 \cdot 2! + 1 \cdot 1! + 0 \cdot 0! = 2 \cdot 6 + 0 + 1 + 0 = 13$$

Перестановка $(3, 1, 4, 2)$ имеет порядковый номер $13$ в лексикографическом списке из $24$ перестановок (индексация с нуля).

import math

def permutation_rank(perm: list[int]) -> int:
    n = len(perm)
    rank = 0
    for i in range(n):
        count = sum(1 for j in range(i + 1, n) if perm[j] < perm[i])
        rank += count * math.factorial(n - 1 - i)
    return rank

print(permutation_rank([3, 1, 4, 2]))  # 13

Сложность наивной реализации составляет $O(n^2)$. При больших $n$ подсчёт инверсий справа можно ускорить до $O(n \log n)$ с помощью дерева Фенвика или дерева отрезков.

От номера к перестановке (Unranking)

Деранжирование выполняет шаги в обратном порядке:

1. Делим номер $R$ на $(n-1)!$ с остатком. Частное даёт количество пропущенных доступных элементов, а остаток передаётся на следующий шаг.
2. Из отсортированного списка ещё не использованных чисел извлекаем элемент по индексу, равному частному.
3. Повторяем процедуру для делителей $(n-2)!, (n-3)!, \dots, 0!$.

Восстановим перестановку длины $4$ с рангом $R = 13$:

• Доступные числа: $[1, 2, 3, 4]$.
• Шаг 1: $13 // 3! = 13 // 6 = 2$, остаток $13 \% 6 = 1$. Берём элемент с индексом $2$: это число $3$. Список доступных: $[1, 2, 4]$.
• Шаг 2: $1 // 2! = 1 // 2 = 0$, остаток $1 \% 2 = 1$. Берём элемент с индексом $0$: это число $1$. Список доступных: $[2, 4]$.
• Шаг 3: $1 // 1! = 1 // 1 = 1$, остаток $1 \% 1 = 0$. Берём элемент с индексом $1$: это число $4$. Список доступных: $[2]$.
• Шаг 4: $0 // 0! = 0 // 1 = 0$, остаток $0$. Берём элемент с индексом $0$: это число $2$.

Результат: $(3, 1, 4, 2)$, что в точности совпадает с исходной перестановкой.

def permutation_unrank(n: int, rank: int) -> list[int]:
    elements = list(range(1, n + 1))
    result = []
    for i in range(n - 1, -1, -1):
        fact = math.factorial(i)
        index = rank // fact
        rank %= fact
        result.append(elements.pop(index))
    return result

print(permutation_unrank(4, 13))  # [3, 1, 4, 2]

Ранжирование и деранжирование сочетаний

Для сочетаний факториалы неприменимы: порядок элементов внутри выборки не имеет значения, и канонически каждое сочетание из $n$ по $k$ записывается в виде строго возрастающего кортежа $C = (c_1, c_2, \dots, c_k)$, где $1 \le c_1 < c_2 < \dots < c_k \le n$.

Как быстро узнать номер сочетания или восстановить его по индексу? Здесь позиционными весами блоков служат биномиальные коэффициенты.

Представьте, что мы выбираем первый элемент сочетания $c_1$.

• Если $c_1 = 1$, мы сразу переходим к выбору оставшихся $k-1$ элементов из диапазона $[2, n]$.
• Если $c_1 > 1$, это означает, что мы пропустили все сочетания, начинавшиеся с $1, 2, \dots, c_1 - 1$.

Сколько сочетаний начинается с конкретного префикса? Если мы зафиксировали первый элемент как $v$, то остальные $k-1$ элементов мы должны выбрать из оставшихся $n - v$ чисел. Таких вариантов ровно $\binom{n - v}{k - 1}$.

Формула ранга сочетания

Суммируя число пропущенных сочетаний для каждого разряда, получаем формулу ранга сочетания $(c_1, c_2, \dots, c_k)$:

$$R = \sum_{i=1}^{k} \sum_{v = c_{i-1} + 1}^{c_i - 1} \binom{n - v}{k - i}$$

где полагается $c_0 = 0$.

Поясним смысл составляющих:

• Внешняя сумма по $i$ перебирает позиции в сочетании от $1$ до $k$.
• Внутренняя сумма по $v$ перебирает все значения, которые могли бы стоять на $i$-м месте, но были пропущены в пользу выбранного $c_i$.
• $\binom{n - v}{k - i}$ — количество способов добрать оставшиеся $k - i$ элементов из чисел, строго больших $v$.

Вычислим ранг сочетания $(2, 4, 5)$ при $n = 5, k = 3$:

1. Первая позиция ($i = 1$): выбран элемент $c_1 = 2$. До него пропущен элемент $v = 1$. Количество пропущенных сочетаний: $\binom{5 - 1}{3 - 1} = \binom{4}{2} = 6$.
2. Вторая позиция ($i = 2$): выбран элемент $c_2 = 4$. До него (после $c_1 = 2$) пропущен элемент $v = 3$. Количество пропущенных сочетаний: $\binom{5 - 3}{3 - 2} = \binom{2}{1} = 2$.
3. Третья позиция ($i = 3$): выбран элемент $c_3 = 5$. До него (после $c_2 = 4$) никаких элементов пропущено не было ($v$ принимает пустое множество значений). Вклад равен $0$.

Суммарный ранг: $R = 6 + 2 + 0 = 8$.

Всего существует $\binom{5}{3} = 10$ сочетаний. Сочетание $(2, 4, 5)$ занимает 8-е место при нумерации от $0$ до $9$.

import math

def combination_rank(comb: list[int], n: int) -> int:
    k = len(comb)
    rank = 0
    prev = 0
    for i in range(k):
        curr = comb[i]
        for v in range(prev + 1, curr):
            rank += math.comb(n - v, k - 1 - i)
        prev = curr
    return rank

print(combination_rank([2, 4, 5], 5))  # 8

Деранжирование сочетания

Для восстановления сочетания по его рангу $R$ мы жадно определяем каждый элемент $c_i$ слева направо. Для очередного кандидата на позицию $i$ смотрим, сколько сочетаний начинается с этого кандидата. Если $R$ больше или равен этому количеству, мы вычитаем этот блок из $R$ и пробуем следующего кандидата. Как только остаток $R$ меньше размера блока — кандидат фиксируется.

def combination_unrank(rank: int, n: int, k: int) -> list[int]:
    result = []
    candidate = 1
    for i in range(k):
        while True:
            # Сколько сочетаний можно составить, если на текущую позицию взять candidate
            block_size = math.comb(n - candidate, k - 1 - i)
            if rank < block_size:
                result.append(candidate)
                candidate += 1
                break
            rank -= block_size
            candidate += 1
    return result

print(combination_unrank(8, 5, 3))  # [2, 4, 5]

Практическое применение: Равномерная генерация объектов

Одна из частых задач при тестировании алгоритмов и в машинном обучении — сэмплирование случайного комбинаторного объекта из равномерного распределения.

Наивный подход «сгенерировать все объекты в массив и взять random.choice» требует $O(N)$ памяти, что неприемлемо уже для $n = 15$ при работе с перестановками или $n = 50, k = 10$ для сочетаний. Другой наивный подход — случайное блуждание с проверкой корректности — часто искажает равномерность распределения.

Деранжирование даёт точный метод:

Чтобы выбрать случайный комбинаторный объект с равномерным распределением вероятностей, достаточно сгенерировать одно псевдослучайное целое число в диапазоне от $0$ до $N-1$ и применить к нему алгоритм деранжирования.

Тип объекта	Мощность множества ($N$)	Время unrank	Память
Подмножество $n$ элементов	$2^n$	$O(n)$	$O(n)$
Перестановка длины $n$	$n!$	$O(n^2)$ или $O(n \log n)$	$O(n)$
Сочетание из $n$ по $k$	$\binom{n}{k}$	$O(k \cdot n)$	$O(k)$

import secrets

def get_random_combination(n: int, k: int) -> list[int]:
    total = math.comb(n, k)
    # Генерируем криптографически стойкое случайное число от 0 до total - 1
    random_rank = secrets.randbelow(total)
    return combination_unrank(random_rank, n, k)

# Равномерный выбор 5 элементов из миллиона за доли миллисекунды:
sample = get_random_combination(1_000_000, 5)

Вернёмся к вопросу из начала статьи: кластер из 1000 серверов должен распределить между собой работу над $n = 14$ перестановками ($14! = 87\,178\,291\,200$). Благодаря деранжированию координатору не нужно передавать гигабайты данных:

• Базовый размер блока составляет $S = \lfloor 14! / 1000 \rfloor = 87\,178\,291$. Сервер $m$ ($0 \le m < 1000$) получает непрерывный отрезок индексов перестановок (первые 200 серверов берут по $S + 1$ перестановке, чтобы покрыть неделимый остаток $14! \bmod 1000 = 200$).
• Сервер выполняет permutation_unrank(14, start_rank) за микросекунды и получает стартовую перестановку напрямую.
• Далее сервер генерирует свой блок последующих перестановок алгоритмом Нараяны.

Таким образом, ранжирование и деранжирование замыкают алгоритмический фундамент перебора: они освобождают нас от необходимости последовательного сканирования пространства поиска, позволяя адресовать любой комбинаторный объект так же быстро и произвольно, как элемент массива по индексу в памяти.

Поиск с возвратом и отсечение ветвей

Полный перебор перестановок для $N = 16$ требует обхода $16! \approx 2 \times 10^{13}$ состояний — на современном процессоре это займёт недели непрерывных вычислений. Однако если наложить на эти состояния даже элементарные ограничения, подавляющее большинство вариантов окажется заведомо бессмысленным задолго до того, как перестановка будет собрана до конца. Зачем генерировать миллиарды суффиксов, если первые два элемента конфигурации уже нарушают условия задачи?

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

Дерево пространства поиска и механика отката

Любой комбинаторный перебор можно строго формализовать как обход ориентированного дерева — дерева пространства состояний (state-space tree).

Корень этого дерева представляет собой пустое частичное решение. Узлы на глубине $k$ соответствуют решениям, в которых определены первые $k$ компонентов вектора $(x_1, x_2, \dots, x_k)$. Листья на максимальной глубине $n$ представляют собой полностью сформированные комбинаторные объекты.

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

При наивном переборе мы обязаны обойти все листья дерева. При поиске с возвратом каждый узел проверяется предикатом допустимости.

Разница между пассивным перебором и поиском с возвратом наглядно проявляется в том, на каком этапе отбрасываются невалидные конфигурации:

Параметр	Полный перебор (Brute-force)	Поиск с возвратом (Backtracking)
Точка валидации	Только в листьях дерева ($k = n$)	В каждом промежуточном узле ($k < n$)
Затраты на тупиковую ветвь	Обход всего поддерева до листьев	Мгновенный откат при первой ошибке
Потребление памяти	$O(1)$ при итеративном обходе	$O(n)$ на стек рекурсии или состояние пути
Применимость	Генерация без строгих локальных фильтров	Задачи с жесткими ограничениями (CSP)

Общий каркас алгоритма строится вокруг рекурсивной функции, принимающей текущую глубину и изменяемое состояние:

def backtrack(path: list[int], state: dict) -> None:
    if is_solution(path):
        process_solution(path)
        return

    for candidate in get_candidates(path, state):
        if is_valid(candidate, path, state):
            apply(candidate, path, state)
            backtrack(path, state)
            revert(candidate, path, state)  # Шаг возврата (backtrack)

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

Задача о размещении N ферзей: локальные предикаты и битовые маски

Классический эталон для иллюстрации силы отсечений — задача о расстановке $N$ ферзей на шахматной доске $N \times N$ так, чтобы ни одна пара не атаковала друг друга по вертикали, горизонтали или диагонали.

Если рассматривать доску как $N^2$ клеток, число способов расставить $N$ фигур равно:

$$\binom{N^2}{N}$$

Для $N = 8$ это $\binom{64}{8} = 4\,426\,165\,368$ комбинаций. Понимая, что на каждой горизонтали обязан стоять ровно один ферзь, пространство можно сузить до вектора перестановок длины $N$, где индекс элемента задаёт строку, а значение — столбец. Это сокращает объём до $N!$, что для $N = 8$ даёт $8! = 40\,320$ конфигураций.

Однако с помощью локальных ограничений отсечение срабатывает задолго до листьев. Конфликт двух ферзей в позициях $(r_1, c_1)$ и $(r_2, c_2)$ возникает тогда и только тогда, когда:

$$c_1 = c_2 \quad \text{или} \quad |r_1 - r_2| = |c_1 - c_2|$$

Уравнение диагоналей эквивалентно проверке сумм и разностей координат:

• Главные диагонали (направление $\searrow$): разность $(r - c)$ постоянна. Чтобы избежать отрицательных индексов, используют смещение: $r - c + (N - 1)$.
• Побочные диагонали (направление $\swarrow$): сумма $(r + c)$ постоянна.

Вместо обхода массива уже расставленных фигур проверка выполняется за $O(1)$ с помощью битовых масок. Поскольку $N$ обычно не превышает 32, все занятые столбцы и диагонали упаковываются в целые числа:

def solve_n_queens(n: int) -> int:
    solutions = 0

    def place_queen(row: int, cols: int, diag1: int, diag2: int) -> None:
        nonlocal solutions
        if row == n:
            solutions += 1
            return

        # Битовая маска всех доступных столбцов в текущей строке
        # Единицы в full_mask ограничивают рабочую ширину до n бит
        full_mask = (1 << n) - 1
        occupied = cols | diag1 | diag2
        available = full_mask & ~occupied

        while available > 0:
            # Извлекаем младший единичный бит — позицию ферзя
            col_bit = available & -available
            available &= available - 1

            # При переходе на строку row + 1:
            # diag1 сдвигается влево (r - c сохраняется при увеличении row и col)
            # diag2 сдвигается вправо (r + c сохраняется при увеличении row и уменьшении col)
            place_queen(
                row + 1,
                cols | col_bit,
                (diag1 | col_bit) << 1,
                (diag2 | col_bit) >> 1,
            )

    place_queen(0, 0, 0, 0)
    return solutions

При таком подходе алгоритм вообще не генерирует заведомо ошибочные ходы. Для $N = 8$ вместо $40\,320$ перестановок алгоритм исследует всего $2\,057$ узлов дерева (считая корневой узел), находя все 92 решения за доли миллисекунды.

Оптимизация порядка перебора: эвристика Fail-First

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

Канонический принцип комбинаторного перебора — эвристика минимального количества оставшихся значений (Minimum Remaining Values, MRV), известная также как принцип Fail-First («падай раньше»).

Принцип Fail-First гласит: в дереве поиска следующей для раскрытия следует выбирать ту переменную, для которой существует наименьшее количество допустимых вариантов продолжения.

Интуиция проста: если ветка дерева всё равно бесперспективна, обнаружить это на шаге с фактором ветвления $b = 1$ или $b = 2$ на порядки дешевле, чем развернуть поддерево с $b = 9$ и лишь на глубине натолкнуться на противоречие. Именно этот подход лежит в основе высокоэффективных решателей судоку: всегда заполняется клетка с наименьшим числом легальных кандидатов.

Метод ветвей и границ (Branch and Bound)

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

На помощь приходит вычисление границ (bounds).

Пусть $f(x)$ — целевая функция стоимости, которую требуется минимизировать. В ходе перебора поддерживается глобальная переменная $C^*$ — стоимость наилучшего полного решения, найденного к данному моменту (верхняя граница минимума).

Для каждого частичного решения $P = (x_1, \dots, x_k)$ вычисляется функция эвристической оценки снизу:

$$L(P) = g(P) + h(P)$$

где:

• $g(P)$ — точная известная стоимость уже сделанных выборов для первых $k$ элементов;
• $h(P)$ — оптимистичная оценка (нижняя грань) стоимости завершения оставшейся части решения ($x_{k+1}, \dots, x_n$). Оценка обязана быть допустимой (admissible), то есть $h(P) \leq h^*(P)$, где $h^*(P)$ — истинная минимальная стоимость дополнения.

Если в узле дерева выполняется неравенство:

$$L(P) \geq C^*$$

это поддерево немедленно отсекается. Никакое продолжение частичного пути $P$ физически не сможет превзойти уже известное лучшее решение.

def branch_and_bound(path: list[int], current_cost: int, best_cost: int) -> int:
    lower_bound = current_cost + heuristic_lower_bound(path)

    # Главное условие отсечения ветвей и границ
    if lower_bound >= best_cost:
        return best_cost

    if is_complete(path):
        return min(best_cost, current_cost)

    for next_step, step_cost in generate_steps(path):
        best_cost = branch_and_bound(
            path + [next_step],
            current_cost + step_cost,
            best_cost
        )

    return best_cost

Практикум: Задача коммивояжёра через Branch and Bound

Рассмотрим решение задачи коммивояжёра (TSP) для $n$ городов с матрицей расстояний $D$.

В наивном сценарии перебор всех $(n-1)!$ маршрутов становится невозможным уже при $n > 12$. Построим для него метод ветвей и границ.

Чтобы отсекать бесперспективные неполные маршруты, нам нужна вычислимая за $O(n)$ оптимистичная нижняя граница $h(P)$ для оставшихся городов. Простейшая, но мощная оценка: для каждого ещё не посещённого города его вклад в оставшийся путь не может быть меньше веса минимального исходящего из него ребра.

Пусть текущий путь $P = [v_1, v_2, \dots, v_k]$, накопленная стоимость $g(P) = \sum_{i=1}^{k-1} D[v_i][v_{i+1}]$. Множество непосещённых вершин обозначим как $U = V \setminus \{v_1, \dots, v_k\}$.

Нижняя граница дополнения пути формируется из трёх компонентов:

1. Выход из текущей вершины $v_k$ в один из непосещённых городов: $\min_{u \in U} D[v_k][u]$.
2. Выход из каждого промежуточного непосещённого города $u \in U$: для каждого $u$ берётся $\min_{w \in (U \setminus \{u\}) \cup \{v_1\}} D[u][w]$.
3. Возврат в начальную вершину $v_1$.

Реализуем алгоритм:

def solve_tsp_branch_and_bound(dist: list[list[int]]) -> int:
    n = len(dist)
    all_visited_mask = (1 << n) - 1
    best_cost = float("inf")

    # Предрасчёт минимального исходящего ребра для каждой вершины
    min_out = [
        min(dist[i][j] for j in range(n) if i != j)
        for i in range(n)
    ]

    def compute_bound(curr: int, visited_mask: int, current_cost: int) -> int:
        bound = current_cost
        # Если все вершины посещены, остался только возврат в старт (город 0)
        if visited_mask == all_visited_mask:
            return current_cost + dist[curr][0]

        # Минимальный шаг из текущей вершины в ещё непосещённые
        unvisited = [j for j in range(n) if not (visited_mask & (1 << j))]
        bound += min(dist[curr][nxt] for nxt in unvisited)

        # Оценка для оставшихся вершин
        for u in unvisited:
            # Каждая непосещённая должна пойти либо в другую непосещённую, либо в 0
            possible_dest = [j for j in unvisited if j != u] + [0]
            bound += min(dist[u][dest] for dest in possible_dest)

        return bound

    def search(curr: int, visited_mask: int, current_cost: int) -> None:
        nonlocal best_cost

        if visited_mask == all_visited_mask:
            total = current_cost + dist[curr][0]
            if total < best_cost:
                best_cost = total
            return

        # Сортируем следующих кандидатов по возрастанию расстояния (жадный приоритет)
        candidates = [
            j for j in range(n) if not (visited_mask & (1 << j))
        ]
        candidates.sort(key=lambda nxt: dist[curr][nxt])

        for nxt in candidates:
            next_cost = current_cost + dist[curr][nxt]
            next_mask = visited_mask | (1 << nxt)

            # Вычисляем оценку снизу для этой ветки
            bound = compute_bound(nxt, next_mask, next_cost)

            # Отсечение: если даже оптимистичный прогноз хуже рекорда — не идём туда
            if bound < best_cost:
                search(nxt, next_mask, next_cost)

    # Стартуем из нулевого города
    search(0, 1, 0)
    return best_cost

Протестируем алгоритм на графе из 5 городов со следующей матрицей смежности:

dist_matrix = [
    [0, 10, 8, 9, 7],
    [10, 0, 10, 5, 6],
    [8, 10, 0, 8, 9],
    [9, 5, 8, 0, 6],
    [7, 6, 9, 6, 0]
]

min_cycle = solve_tsp_branch_and_bound(dist_matrix)
print(f"Минимальная длина цикла: {min_cycle}")

Благодаря отсечению $L(P) \geq C^*$ алгоритм отбрасывает ветви с длинными рёбрами на ранних стадиях, не погружаясь в бессмысленный перебор хвостов перестановок.

Отсечение по симметрии

Ещё один мощный класс сокращения перебора — нарушение симметрии (symmetry breaking).

Если переставляемые объекты или структура задачи инвариантны относительно вращений или зеркальных отражений, наивный алгоритм найдет каждое независимое решение несколько раз во взаимно симметричных формах:

• В задаче коммивояжёра для ненаправленного графа путь $0 \to 1 \to 2 \to \dots \to 0$ эквивалентен пути $0 \to \dots \to 2 \to 1 \to 0$. Мы сразу можем зафиксировать направление, потребовав, чтобы второй посещённый город имел индекс меньший, чем последний. Это сокращает пространство вдвое.
• В задаче о ферзях доска $N \times N$ обладает группой симметрий диэдра $D_4$ (8 симметрий: 4 поворота и 4 отражения). Ограничив положение ферзя в первой строке только первой половиной столбцов ($c < \lfloor N/2 \rfloor$ при 0-индексации или $c \leq \lfloor N/2 \rfloor$ при 1-индексации), мы отсекаем ровно половину начального дерева поиска.

Систематический поиск с возвратом в сочетании с битовыми масками, принципом Fail-First и эвристическими границами переводит алгоритмы из категории «теоретический факториальный перебор» в практический инструмент, решающий задачи комбинаторной оптимизации промышленного масштаба.