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

Материал из Algocode wiki
Версия от 16:20, 6 февраля 2021; Глеб (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Задача

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

Идея

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

Решение

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

Пример

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

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

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

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

Доказательство

Чтобы доказать корректность, надо доказать:

1) Что получившаяся последовательность лексикографически больше исходной

Несложно это проверить так как теперь закрывающая скобка находится раньше

2) Что не существует последовательности, которая лексикографически больше исходной, но лексикографически меньше получившейся.

Если бы такая существовала, у нее бы был либо меньший суффикс(что невозможно, так как мы взяли минимально возможный) либо она была бы меньше в той позиции, которую мы свапнули, но это невозможно, так как мы взяли минимально возможный суффикс.



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

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