Генерация следующей ПСП: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «= Задача = Дана правильная скобочная подпоследовательность, надо вывести следующую за н...»)
 
 
Строка 19: Строка 19:
  
 
3) Сделаем минимально возможный суффикс - ()()()(())
 
3) Сделаем минимально возможный суффикс - ()()()(())
 +
 +
=Доказательство=
 +
Чтобы доказать корректность, надо доказать:
 +
 +
1) Что получившаяся последовательность лексикографически больше исходной
 +
 +
Несложно это проверить так как теперь закрывающая скобка находится раньше
 +
 +
2) Что не существует последовательности, которая лексикографически больше исходной, но лексикографически меньше получившейся.
 +
 +
Если бы такая существовала, у нее бы был либо меньший суффикс(что невозможно, так как мы взяли минимально возможный) либо она была бы меньше в той позиции, которую мы свапнули, но это невозможно, так как мы взяли минимально возможный суффикс.
  
 
{{Автор|Глеб Лобанов|glebodin}}
 
{{Автор|Глеб Лобанов|glebodin}}
  
 
[[Категория:Конспект]]
 
[[Категория:Конспект]]

Текущая версия на 16:20, 6 февраля 2021

Задача

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

Идея

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

Решение

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

Пример

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

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

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

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

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

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

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

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

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

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



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

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