Генерация следующей ПСП
Задача
Дана правильная скобочная подпоследовательность, надо вывести следующую за ней в лексикографическом порядке.
Идея
Также как и в перестановках, нам нужно найти максимальный суффикс, который нельзя сделать больше лексикографически
Решение
Нетрудно заметить, что последняя ПСП образуется путем чередования открывающей и закрывающей, следовательно нам нужно найти минимальный суффикс, на котором подряд стоят две закрывающие скобки, затем когда мы нашли такой момент нам нужно найти первую открывающую скобку и свапнуть ее с закрывающий, полученный суффикс также как и в случае с перестановками надо сделать минимально возможным лексикографически.
Пример
Допустим нам дана ПСП ()()(())() :
1) Тогда интересующий нас суффикс - ()()(( || ))()
2) Свапнем ( и ), получим ()()()()()
3) Сделаем минимально возможный суффикс - ()()()(())
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin