Генерация следующей ПСП

Задача

Дана правильная скобочная подпоследовательность, надо вывести следующую за ней в лексикографическом порядке.

Идея

Также как и в перестановках, нам нужно найти максимальный суффикс, который нельзя сделать больше лексикографически

Решение

Нетрудно заметить, что последняя ПСП образуется путем чередования открывающей и закрывающей, следовательно нам нужно найти минимальный суффикс, на котором подряд стоят две закрывающие скобки, затем когда мы нашли такой момент нам нужно найти первую открывающую скобку и свапнуть ее с закрывающий, полученный суффикс также как и в случае с перестановками надо сделать минимально возможным лексикографически.

Пример

Допустим нам дана ПСП ()()(())() :

1) Тогда интересующий нас суффикс - ()()(( || ))()

2) Свапнем ( и ), получим ()()()()()

3) Сделаем минимально возможный суффикс - ()()()(())

---

Автор конспекта: Глеб Лобанов

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