Генерация всех правильных скобочных последовательностей: различия между версиями
Материал из Algocode wiki
(Новая страница: «= Задача = По данному $n$ надо вывести все правильные скобочные последовательности из $n$ па...») |
|||
Строка 10: | Строка 10: | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | void gen(int n, vector<char>& cur_seq, int cur_balance=0 int cur_index=0) { | + | void gen(int n, vector<char>& cur_seq, int cur_balance=0, int cur_index=0) { |
− | if ( | + | if (cur_index == 2 * n) { |
for (auto& bracket : cur_seq) { | for (auto& bracket : cur_seq) { | ||
cout << bracket; | cout << bracket; | ||
Строка 17: | Строка 17: | ||
cout << endl; | cout << endl; | ||
} else { | } else { | ||
− | if (cur_balance == | + | if (cur_balance == 2 * n - cur_index) { |
// если количество оставшихся позиций в точности равно | // если количество оставшихся позиций в точности равно | ||
// количеству скобок, которые надо закрыть, то новые скобки мы не можем открывать | // количеству скобок, которые надо закрыть, то новые скобки мы не можем открывать | ||
Строка 23: | Строка 23: | ||
cur_seq[cur_index] = ')'; | cur_seq[cur_index] = ')'; | ||
cur_balance--; | cur_balance--; | ||
− | + | gen(n, cur_seq, cur_balance, cur_index + 1); | |
} else { | } else { | ||
// пробуем поставить обе скобки, сначала ставим ту, | // пробуем поставить обе скобки, сначала ставим ту, | ||
Строка 32: | Строка 32: | ||
gen(n, cur_seq, cur_balance, cur_index + 1); | gen(n, cur_seq, cur_balance, cur_index + 1); | ||
− | cur_seq[cur_index] = ')'; | + | if (cur_balance > 1) { |
− | + | cur_seq[cur_index] = ')'; | |
− | + | cur_balance -= 2; | |
+ | gen(n, cur_seq, cur_balance, cur_index + 1); | ||
+ | } | ||
} | } | ||
} | } |
Версия 10:47, 22 февраля 2020
Задача
По данному $n$ надо вывести все правильные скобочные последовательности из $n$ пар скобок в лексикографическом порядке. Например, если $n = 2$, надо вывести
- (())
- ()()
Рекурсивный перебор
Давайте напишем следующую процедуру
void gen(int n, vector<char>& cur_seq, int cur_balance=0, int cur_index=0) {
if (cur_index == 2 * n) {
for (auto& bracket : cur_seq) {
cout << bracket;
}
cout << endl;
} else {
if (cur_balance == 2 * n - cur_index) {
// если количество оставшихся позиций в точности равно
// количеству скобок, которые надо закрыть, то новые скобки мы не можем открывать
cur_seq[cur_index] = ')';
cur_balance--;
gen(n, cur_seq, cur_balance, cur_index + 1);
} else {
// пробуем поставить обе скобки, сначала ставим ту,
// которая лексикографически меньше
cur_seq[cur_index] = '(';
cur_balance++;
gen(n, cur_seq, cur_balance, cur_index + 1);
if (cur_balance > 1) {
cur_seq[cur_index] = ')';
cur_balance -= 2;
gen(n, cur_seq, cur_balance, cur_index + 1);
}
}
}
}