Генерация всех правильных скобочных последовательностей

Материал из Algocode wiki
Версия от 21:24, 8 мая 2020; Rationalex (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Задача

По данному $n$ надо вывести все правильные скобочные последовательности из $n$ пар скобок в лексикографическом порядке. Например, если $n = 3$, надо вывести

  1. ((()))
  2. (()())
  3. (())()
  4. ()(())
  5. ()()()

Рекурсивный перебор

Давайте напишем следующую процедуру


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);
       }
    }
  }
}



Автор конспекта: Александр Гришутин

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