Перебор комбинаторных объектов

Допустим, нам хочется перебрать все перестановки в лексикографическом порядке. Как это можно сделать? Напишем простую рекурсию: нам приходит префикс перестановки, и мы знаем, перестановки какой длины нам нужны. Тогда мы можем перебрать еще не использованные числа от 1 до $n$ по возрастанию (ведь интересен лексикографический порядок), поставить это число следующим и запуститься от нового префикса. Напишем код:

void f(int n, vector<int> & a, vector<char> & used) { // vector<bool> работает долго
    if (a.size() == n) { // получили новую перестановку в векторе a. Можем вывести/сохранить ее
        ...
    }
    a.push_back();
    for (int i = 1; i <= n; ++i) {
        if (!used[i]) {
            used[i] = true;
            a.back() = i;
            f(n, a, used);
            used[i] = false;
        }
    }
    a.pop_back();
}

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

Но вернемся к перестановкам. Кажется, что перебор всех их - весьма частая и простая задача, для которой должно быть что-то в стандартной библиотеке. Так и есть. Напишем код для перебора всех перестановок (опять же в лексикографическом порядке) с использованием встроенной функции next_permutation():

sort(a.begin(), a.end());  // чтобы перебрать все перестановки с next_permutation, нужно чтобы a изначально был отсортирован
do {
    ... // получили очередную перестановку
} while (next_permutation(a.begin(), a.end()));

---

Автор конспекта: Егор Гутров

По всем вопросам пишите в telegram @Egor_Gutrov