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

Материал из Algocode wiki
Версия от 13:17, 6 февраля 2021; Глеб (обсуждение | вклад) (Новая страница: «= Задача = Дана правильная скобочная подпоследовательность, надо вывести следующую за н...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Задача

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

Идея

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

Решение

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

Пример

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

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

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

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



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

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