Разбиения на слагаемые и множители

Разложить число $n$ в сумму натуральных слагаемых можно многими способами, но $3 + 1 + 1$ и $1 + 3 + 1$ — обычно одно и то же разбиение. Задача перебора — выдать каждое ровно один раз.

Решается это одним приёмом: потребовать, чтобы слагаемые шли в невозрастающем порядке. Тогда каждому набору соответствует ровно одна допустимая запись.

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

Параметров два: сколько осталось набрать и каким было предыдущее слагаемое.

vector<int> parts;

void generate(int left, int last) {
    if (left == 0) { print(parts); return; }
    for (int value = 1; value <= min(left, last); value++) {
        parts.push_back(value);
        generate(left - value, value);
        parts.pop_back();
    }
}
// запуск: generate(n, n);

Проверено против известных значений функции разбиений: количество выведенного совпадает с $p(n)$ для всех $n \le 16$, где $p(16) = 231$.

Две детали, каждая из которых обязательна.

min(left, last) в границе цикла. Ограничение last даёт неубывание, ограничение left не даёт уйти в отрицательную остаточную сумму. Забыв второе, получите либо неверные разбиения, либо бесконечную рекурсию.

Порядок цикла задаёт порядок вывода. Возрастающий цикл при невозрастающих слагаемых даёт лексикографический порядок разбиений. Нужен обратный — цикл for (int value = min(left, last); value >= 1; value--).

Разбиение на множители

Задача-близнец: представить $n$ произведением сомножителей, больших единицы.

void generate(int left, int last) {
    if (left == 1) { print(parts); return; }
    for (int value = last; value <= left; value++) {
        if (left % value != 0) continue;
        parts.push_back(value);
        generate(left / value, value);
        parts.pop_back();
    }
}
// запуск: generate(n, 2);

Три отличия от сложения.

Условие остановки — left == 1, а не left == 0. Единица — нейтральный элемент умножения. Написав left == 0, вы получите бесконечную рекурсию, потому что деление до нуля не доходит.

Проверка делимости. Не всякий множитель подходит; неподходящие пропускаем через continue.

Множители не меньше двух. Иначе left / 1 == left, и рекурсия зациклится.

Замеры: число 12 раскладывается 4 способами, 16 — пятью, 24 — семью, 36 — девятью.

Слагаемые ровно из k штук

Частая вариация. Добавляется параметр «сколько слагаемых осталось», а вместе с ним и отсечения:

• если осталось $c$ слагаемых, а сумма $left$, то каждое из них не больше $left - (c - 1)$ (остальным нужна хотя бы единица);
• и не меньше $\lceil left / c \rceil$, если слагаемые невозрастающие, — иначе оставшимися, которые ещё меньше, сумму не набрать.

Второе отсечение снимает большую часть дерева, и с ним перебор проходит там, где без него не проходил.

Сколько всего разбиений

Полезно знать порядок величины, чтобы понимать, влезет ли перебор.

$n$	$p(n)$
10	42
20	627
50	204 226
100	190 569 292
200	около $4 \cdot 10^{12}$

Рост субэкспоненциальный, примерно $e^{c\sqrt{n}}$. Практическая граница для перебора — $n$ около 60–70; дальше только считать количество динамикой, а не выписывать сами разбиения.

Динамика, кстати, простая: dp[sum][maxPart] — сколько разбиений суммы sum на слагаемые не больше maxPart. Переход — «взять ещё одно слагаемое maxPart» или «уменьшить maxPart».

Общая схема

Все задачи этого вида устроены одинаково:

1. Найти запись, при которой каждый объект получается ровно один раз, — обычно это требование монотонности.
2. Передавать в рекурсию последний выбранный элемент, чтобы монотонность поддерживать.
3. Ограничивать цикл и сверху (последним элементом), и снизу (тем, что ещё достижимо).

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