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