Перебор комбинаторных объектов
Материал из Algocode wiki
Версия от 13:35, 5 апреля 2020; Gutrov Egor (обсуждение | вклад) (Новая страница: «Допустим, нам хочется перебрать все перестановки в лексикографическом порядке. Как это...»)
Допустим, нам хочется перебрать все перестановки в лексикографическом порядке. Как это можно сделать? Напишем простую рекурсию: нам приходит префикс перестановки, и мы знаем, перестановки какой длины нам нужны. Тогда мы можем перебрать еще не использованные числа от 1 до $n$ по возрастанию (ведь интересен лексикографический порядок), поставить это число следующим и запуститься от нового префикса. Напишем код:
void f(int n, vector<int> & a, vector<char> & used) {
if (a.size() == n) { // получили новую перестановку в векторе a. Можем вывести/сохранить ее
...
}
for (int i = 1; i <= n; ++i) {
}
}