Изменения
Нет описания правки
*"" (пустая строка) есть правильная скобочная последовательность;
*пусть $S$ - правильная скобочная последовательность, взятая в скобки тогда $(S)$ есть правильная скобочная последовательность;(*)*пусть $S$ - правильная скобочная последовательность, к которой приписана слева или справа другая правильная скобочная последовательность, тогда $()S$ и $S()$ есть правильная скобочная последовательностьправильные скобочные последовательности;
}}
''Примеры правильных скобочный последовательностей:''
''псевдокод'':
Надо отметить что, скобочные последовательности могут состоять не только из одного типа скобок, при этом недопустимо такое расположение, когда один тип скобок закрывает другой:
== Лексикографический порядок порядок правильных скобочных последовательностей ==
Для того чтобы определить лексикографический порядок для правильных скобочных последовательностей будем интерпретировать открывающуюся скобку как "$0$"надо установить порядок на алфавите, а закрывающуюся как "например так '$1$" (**). Тогда первая последовательность с $n' < '$ открывающимися скобками будет иметь вид: {| border="1" cellpadding="3" | (||(||(||(||...||(||(||(||)||)||)||...||)||)||)||)||(***) |- |0||0||0||0||...||0||0||0||1||1||1||...||1||1||1||1 |} что соответствует самому маленькому возможному числу, а последняя: {| border="1" cellpadding="3" | (||)||(||)||...||(||)||(||)||(||)||...||(||)||(||) |- |0||1||0||1||...||0||1||0||1||0||1||...||0||1||0||1 |} что соответствует самому большому возможному числу$'.Для последовательностей с разным типом скобок надо определять свой порядокв зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например "$($"<"$[$"<"$)$"<"$]$".
''Примеры лексикографического порядка для $n$ и $k$, где $n$ - число открывающихся скобок, а $k$ - число видов скобок''
|id = def1
|definition =Числа Каталана {{---}} последовательность чисел, выражающих:
*количество неизоморфных не изоморфных упорядоченных бинарных деревьев с корнем и $n + 1$ листьями;*количество способов соединения $2n$ точек на окружности n непересекающимися не пересекающимися хордами;*количество разбиений выпуклого $(n + 2)$ - угольника на треугольники непересекающимися не пересекающимися диагоналями;
*количество правильных скобочных последовательностей имеющих $n$ открывающихся скобок.}}
Числа Каталана удовлетворяют следующему рекурентному рекуррентному соотношению:
$C_0 = 1$; {{---}} так как существует только одна скобочная последовательность с $0$ открывающихся скобок - пустая
$C_n = \sum_{i = 1}^{n - 1} C_i C_{n - 1 - i}$.
''Генерация следующей скобочной последовательности:''
Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то - "No solution". Воспользуемся интерпретацией (**). Чтобы получить следующий битовый вектор следующую скобочную последовательность надо найти самый последний нулевой элемент, заменить его на единицу, а элементы следующие за ним сделать минимально возможными (все нули). Тоже самое и со скобочными последовательностями, только после замены нуля на единицу оставшиеся скобки надо расположить в минимальном порядке (в виде (***))минимальную:
else
Если эта функция после выполнения выводит $true$ тогда надо напечатать полученную строку $s$, если $false$, то следует вывести "No solution".
Пусть нам известно число $n$. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с $n$ открывающимися скобками:
Так же с помощью этого алгоритма можно получить скобочную последовательность по номеру и номер по скобочной последовательности, добавив сравнение с нужной последовательностью и счетчик. Но это далеко не самый оптимальный алгоритм для подобного типа задач и он не будет нормально работать для больших $n$.
