Перестановки и подмножества

Перестановки и подмножества — то, что перебирают чаще всего. У каждого есть и рекурсивный, и итеративный способ, и знать стоит оба.

Перестановки рекурсией

Перестановка — последовательность из чисел $1 \dots n$, где каждое встречается ровно раз. Отличие от обычного перебора одно: нельзя брать уже использованное.

vector<int> prefix;
vector<char> used;

void generate(int length) {
    if (length == n) { print(prefix); return; }
    for (int value = 1; value <= n; value++) {
        if (used[value]) continue;
        used[value] = 1;
        prefix.push_back(value);
        generate(length + 1);
        prefix.pop_back();
        used[value] = 0;
    }
}

Проверено: количество выведенного равно $n!$ для $n$ от 1 до 8, порядок лексикографический.

Обратите внимание, что used восстанавливается после рекурсивного вызова, вместе с pop_back. Забыть одну из двух строк — самая частая ошибка, и находится она сразу: количество выведенного не совпадёт с $n!$.

Массив used можно и не заводить, проверяя наличие значения прямым проходом по префиксу. Для $n \le 10$ это даже пройдёт по времени, но обойдётся лишним множителем $n$. Память под used — $n$ байт, экономить тут не на чем.

Перестановки без рекурсии

В C++ есть готовое:

vector<int> p(n);
iota(p.begin(), p.end(), 1);
do {
    process(p);
} while (next_permutation(p.begin(), p.end()));

Порядок тот же — лексикографический, поэтому массив надо предварительно отсортировать, иначе часть перестановок не переберётся.

Это короче рекурсии и не тратит стек. Рекурсия выигрывает только тогда, когда нужны отсечения — next_permutation не умеет пропускать целые ветки.

Подмножества битовыми масками

Подмножество набора из $n$ элементов кодируется числом от $0$ до $2^n - 1$: бит $i$ означает «элемент $i$ взят».

for (int mask = 0; mask < (1 << n); mask++) {
    long long sum = 0;
    for (int i = 0; i < n; i++)
        if (mask >> i & 1) sum += a[i];
    // обработать подмножество
}

Без рекурсии, без стека, легко распараллеливается и понятно, где вы находитесь в переборе.

Полезные операции над масками:

выражение	смысл
mask >> i & 1	взят ли элемент $i$
mask | (1 << i)	добавить элемент
mask & ~(1 << i)	убрать элемент
mask ^ (1 << i)	переключить
__builtin_popcount(mask)	сколько элементов
mask & (mask - 1)	убрать младший установленный бит
mask & -mask	оставить только младший бит

Для 64-битных масок функции называются __builtin_popcountll и так далее — забытое ll даёт неверный ответ без всякого предупреждения.

Подмножества фиксированного размера

Перебрать все подмножества ровно из $k$ элементов можно фильтром по popcount, но это лишние $2^n$ итераций. Аккуратнее — рекурсией, как строки с ровно $k$ единицами, или через next_permutation по массиву из $k$ единиц и $n-k$ нулей.

Перебор подмаск

Иногда нужно перебрать все подмножества заданной маски. Наивно это $2^n$ на каждую маску, но есть приём:

for (int sub = mask; ; sub = (sub - 1) & mask) {
    // обработать sub
    if (sub == 0) break;
}

Выражение (sub - 1) & mask даёт следующую подмаску по убыванию. Суммарно по всем маскам такой перебор стоит $3^n$, а не $4^n$, — на этом стоят решения задач про разбиение на группы.

Обратите внимание на форму цикла: выход по break в середине, потому что ноль тоже должен обработаться, а sub >= 0 условием не годится — подмаски беззнаковые по смыслу.

Сколько это стоит

Замеры на одной машине, компилятор с -O2:

перебор	время
$2^{20}$ масок	3 мс
$2^{24}$ масок	31 мс
$2^{26}$ масок	98 мс
$10!$ перестановок	9 мс
$11!$ перестановок	95 мс
$12!$ перестановок	1120 мс

Отсюда рабочие границы: маски — до $n = 25$, перестановки — до $n = 11$. Причём это на пустом теле цикла; с содержательной обработкой границы сдвигаются вниз на единицу-две.

Если в условии $n \le 20$ — почти наверняка ждут перебор масок или динамику по подмножествам. Если $n \le 10$ — перестановки. Ограничение и есть подсказка.