Перебор комбинаторных объектов: различия между версиями
м |
м |
||
(не показаны 4 промежуточные версии этого же участника) | |||
Строка 2: | Строка 2: | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | void f(int n, vector<int> & a, vector<char> & used) { | + | void f(int n, vector<int> & a, vector<char> & used) { // vector<bool> работает долго |
if (a.size() == n) { // получили новую перестановку в векторе a. Можем вывести/сохранить ее | if (a.size() == n) { // получили новую перестановку в векторе a. Можем вывести/сохранить ее | ||
... | ... | ||
Строка 18: | Строка 18: | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | |||
+ | Аналогичным образом можно перебирать, например, сочетания, правильные скобочные последовательности (поддерживая префикс и текущий баланс) и прочие радости. | ||
+ | |||
+ | Но вернемся к перестановкам. Кажется, что перебор всех их - весьма частая и простая задача, для которой должно быть что-то в стандартной библиотеке. Так и есть. Напишем код для перебора всех перестановок (опять же в лексикографическом порядке) с использованием встроенной функции <code>next_permutation()</code>: | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | sort(a.begin(), a.end()); // чтобы перебрать все перестановки с next_permutation, нужно чтобы a был отсортирован | + | sort(a.begin(), a.end()); // чтобы перебрать все перестановки с next_permutation, нужно чтобы a изначально был отсортирован |
do { | do { | ||
... // получили очередную перестановку | ... // получили очередную перестановку | ||
} while (next_permutation(a.begin(), a.end())); | } while (next_permutation(a.begin(), a.end())); | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | |||
+ | {{Автор|Егор Гутров|Egor_Gutrov}} | ||
[[Категория:Конспект]] | [[Категория:Конспект]] |
Текущая версия на 14:20, 5 апреля 2020
Допустим, нам хочется перебрать все перестановки в лексикографическом порядке. Как это можно сделать? Напишем простую рекурсию: нам приходит префикс перестановки, и мы знаем, перестановки какой длины нам нужны. Тогда мы можем перебрать еще не использованные числа от 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