Правильные скобочные последовательности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
Скобочная последовательность - класс комбинаторных объектов, представляющий собой последовательность скобочных символов.
+
<wikitex>
  
Пример:
+
{{Определение
 +
|id = def1
 +
|definition ='''Скобочная последовательность''' {{---}} класс комбинаторных объектов, представляющий собой последовательность скобочных символов.}}
 +
''Примеры скобочных последовательностей''
 +
*$(())))($
 +
*$)()()))()(()())$
 +
{{Определение
 +
|id = def1
 +
|definition ='''Правильная скобочная последовательность''' - частный случай скобочной последовательности, определяющийся следующими образами:
  
(())))(
+
*""(пустая строка) есть правильная скобочная последовательность;
 +
*правильная скобочная последовательность, взятая в скобки есть правильная скобочная последовательность;(*)
 +
*скобочная последовательность, к которой приписана слева или справа другая скобочная последовательность, есть правильная скобочная последовательность;
 +
}}
 +
''Примеры правильных скобочный последовательностей''
 +
*$((()()()()))$
 +
*$(())(()())$
  
Определение:
+
== Алгоритм проверки правильности скобочной последовательности ==
 
 
Правильная скобочная последовательность - частный случай скобочной последовательности, определяющийся следующими образами:
 
 
 
- ""(пустая строка) есть правильная скобочная последовательность;
 
- правильная скобочная последовательность, взятая в скобки есть правильная скобочная последовательность;(*)
 
- скобочная последовательность, к которой приписана слева или справа другая скобочная последовательность, есть правильная скобочная последовательность;
 
 
 
Пример:
 
 
 
(())(()())
 
 
 
Алгоритм проверки правильности скобочной последовательности
 
  
 
Пусть нам дана скобочная последовательность записанная в строку s. Возьмем переменную a, a = 0. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем a на 1, закрывающую - уменьшаем на 1. Если на протяжении всего перебора a было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.
 
Пусть нам дана скобочная последовательность записанная в строку s. Возьмем переменную a, a = 0. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем a на 1, закрывающую - уменьшаем на 1. Если на протяжении всего перебора a было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.
  
псевдокод:
+
''псевдокод'':
  
 
   function check(s: string): boolean;
 
   function check(s: string): boolean;
Строка 45: Строка 47:
 
Надо отметить что, скобочные последовательности могут состоять не только из одного типа скобок, при этом недопустимо такое расположение, когда один тип скобок закрывает другой:
 
Надо отметить что, скобочные последовательности могут состоять не только из одного типа скобок, при этом недопустимо такое расположение, когда один тип скобок закрывает другой:
  
Пример:
+
''Примеры скобочных последовательностей с несколькими типами скобок''
  
()[()]{()()[]} - верно
+
*$( ) [ ( ) ]\{()()[]\}$ - верно
 
+
*$[(]\{\})$ - неверно
[(]{}) - неверно
 
  
 
В этом случае для проверки надо будет использовать стек.
 
В этом случае для проверки надо будет использовать стек.
  
Лексикографический порядок порядок правильных скобочных последовательностей
+
== Лексикографический порядок порядок правильных скобочных последовательностей ==
  
 
Для того чтобы определить лексикографический порядок для правильных скобочных последовательностей будем интерпретировать открывающуюся скобку как "0", а закрывающуюся как "1"(**). Тогда первая последовательность с n открывающимися скобками будет иметь вид:
 
Для того чтобы определить лексикографический порядок для правильных скобочных последовательностей будем интерпретировать открывающуюся скобку как "0", а закрывающуюся как "1"(**). Тогда первая последовательность с n открывающимися скобками будет иметь вид:
  
((((...((()))...)))) (***)
+
{| border="1" cellpadding="3"
 
+
| (||(||(||(||...||(||(||(||)||)||)||...||)||)||)||)||(***)
0000...000111...1111
+
|-
 +
|0||0||0||0||...||0||0||0||1||1||1||...||1||1||1||1
 +
|}
  
 
что соответствует самому маленькому возможному числу, а последняя:
 
что соответствует самому маленькому возможному числу, а последняя:
  
()()...()()()...()()
+
{| border="1" cellpadding="3"
 
+
| (||)||(||)||...||(||)||(||)||(||)||...||(||)||(||)
0101...010101...0101
+
|-
 
+
|0||1||0||1||...||0||1||0||1||0||1||...||0||1||0||1
 +
|}
  
 
что соответствует самому большому возможному числу.
 
что соответствует самому большому возможному числу.
Строка 72: Строка 76:
 
Для последовательностей с разным типом скобок надо определять свой порядок, например "("<"["<")"<"]".
 
Для последовательностей с разным типом скобок надо определять свой порядок, например "("<"["<")"<"]".
  
Примеры лексикографического порядка для n и k, где n - число открывающихся скобок, а k - число видов скобок:
+
''Примеры лексикографического порядка для n и k, где n - число открывающихся скобок, а k - число видов скобок''
  
n = 3;
+
{| border="1" cellpadding="3"
 +
|n = 3||k = 1
 +
|-
 +
|$((()))$||$(()())$||$(())()$||$()(())$||$()()()$
 +
|}
  
k = 1
+
{| border="1" cellpadding="3"
 
+
|n = 2||k = 2
((()))
+
|-
 
+
|$()[]$||$([])$||$[()]$||$[]()$
(()())
+
|}
 
 
(())()
 
 
 
()(())
 
 
 
()()()
 
 
 
n = 2;
 
 
 
k = 2;
 
 
 
()[]
 
 
 
([])
 
 
 
[()]
 
 
 
[]()
 
  
 
Алгоритм генерации лексикографического порядка будет предложен ниже.
 
Алгоритм генерации лексикографического порядка будет предложен ниже.
  
Количество правильных скобочных последовательностей. Числа Каталана
+
== Количество правильных скобочных последовательностей. Числа Каталана ==
  
 
Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана.
 
Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана.
  
Числа Каталана представляют собой:
+
{{Определение
 
+
|id = def1
- количество неизоморфных упорядоченных бинарных деревьев с корнем и n+1 листьями;
+
|definition =Числа Каталана {{---}} последовательность чисел, выражающихЖ
- Количество способов соединения 2n точек на окружности n непересекающимися хордами;
+
*количество неизоморфных упорядоченных бинарных деревьев с корнем и n+1 листьями;
- количество разбиений выпуклого (n+2)-угольника на треугольники непересекающимися диагоналями;
+
*Количество способов соединения 2n точек на окружности n непересекающимися хордами;
- Количество правильных скобочных последовательностей имеющих n открывающихся скобок.
+
*количество разбиений выпуклого (n+2)-угольника на треугольники непересекающимися диагоналями;
 +
*Количество правильных скобочных последовательностей имеющих n открывающихся скобок.}}
  
 
Числа Каталана удовлетворяют следующему рекурентному соотношению:
 
Числа Каталана удовлетворяют следующему рекурентному соотношению:
  
c_0 = 1; - так как существует только одна скобочная последовательность с 0 открывающихся скобок - пустая
+
$c_0$ = 1; - так как существует только одна скобочная последовательность с 0 открывающихся скобок - пустая
  
C_n = (Сумма по i от 1 до n - 1) C_i * C_(n - 1 - i).
+
$C_n$ = (Сумма по i от 1 до n - 1) C_i * C_(n - 1 - i).
  
 
Это соотношение легко получается из (*). Для этого надо перебрать все возможные последовательности d_1 и d_2, являющиеся правильными скобочными последовательностями, такие, что (d_1)d_2 образуют новые правильные скобочные последовательности необходимой нам длины.
 
Это соотношение легко получается из (*). Для этого надо перебрать все возможные последовательности d_1 и d_2, являющиеся правильными скобочными последовательностями, такие, что (d_1)d_2 образуют новые правильные скобочные последовательности необходимой нам длины.

Версия 08:52, 7 января 2012

<wikitex>


Определение:
Скобочная последовательность — класс комбинаторных объектов, представляющий собой последовательность скобочных символов.

Примеры скобочных последовательностей

  • $(())))($
  • $)()()))()(()())$
Определение:
Правильная скобочная последовательность - частный случай скобочной последовательности, определяющийся следующими образами:
  • ""(пустая строка) есть правильная скобочная последовательность;
  • правильная скобочная последовательность, взятая в скобки есть правильная скобочная последовательность;(*)
  • скобочная последовательность, к которой приписана слева или справа другая скобочная последовательность, есть правильная скобочная последовательность;

Примеры правильных скобочный последовательностей

  • $((()()()()))$
  • $(())(()())$

Алгоритм проверки правильности скобочной последовательности

Пусть нам дана скобочная последовательность записанная в строку s. Возьмем переменную a, a = 0. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем a на 1, закрывающую - уменьшаем на 1. Если на протяжении всего перебора a было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.

псевдокод:

 function check(s: string): boolean;
   var 
     i, a :integer;
     begin
       a := 0
       for i := 1 to length(s) do  {перебираем последовательно все символы строки (подразумевается, что в ней нет символов отличных от "(" и ")")}
         begin
           if s[i] = '(' then  {проверяем символ и производим соответствующие действия над переменной a}
           inc(a)
           else
           dec(a);
           if a < 0 then
           check := false;  
         end;
       if a = 0 then  {проверяем на равенство нулю}
       check := true
       else
       check := false;
     end;

Надо отметить что, скобочные последовательности могут состоять не только из одного типа скобок, при этом недопустимо такое расположение, когда один тип скобок закрывает другой:

Примеры скобочных последовательностей с несколькими типами скобок

  • $( ) [ ( ) ]\{()()[]\}$ - верно
  • $[(]\{\})$ - неверно

В этом случае для проверки надо будет использовать стек.

Лексикографический порядок порядок правильных скобочных последовательностей

Для того чтобы определить лексикографический порядок для правильных скобочных последовательностей будем интерпретировать открывающуюся скобку как "0", а закрывающуюся как "1"(**). Тогда первая последовательность с n открывающимися скобками будет иметь вид:

( ( ( ( ... ( ( ( ) ) ) ... ) ) ) ) (***)
0 0 0 0 ... 0 0 0 1 1 1 ... 1 1 1 1

что соответствует самому маленькому возможному числу, а последняя:

( ) ( ) ... ( ) ( ) ( ) ... ( ) ( )
0 1 0 1 ... 0 1 0 1 0 1 ... 0 1 0 1

что соответствует самому большому возможному числу.

Для последовательностей с разным типом скобок надо определять свой порядок, например "("<"["<")"<"]".

Примеры лексикографического порядка для n и k, где n - число открывающихся скобок, а k - число видов скобок

n = 3 k = 1
$((()))$ $(()())$ $(())()$ $()(())$ $()()()$
n = 2 k = 2
$()[]$ $([])$ $[()]$ $[]()$

Алгоритм генерации лексикографического порядка будет предложен ниже.

Количество правильных скобочных последовательностей. Числа Каталана

Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана.


Определение:
Числа Каталана — последовательность чисел, выражающихЖ
  • количество неизоморфных упорядоченных бинарных деревьев с корнем и n+1 листьями;
  • Количество способов соединения 2n точек на окружности n непересекающимися хордами;
  • количество разбиений выпуклого (n+2)-угольника на треугольники непересекающимися диагоналями;
  • Количество правильных скобочных последовательностей имеющих n открывающихся скобок.


Числа Каталана удовлетворяют следующему рекурентному соотношению:

$c_0$ = 1; - так как существует только одна скобочная последовательность с 0 открывающихся скобок - пустая

$C_n$ = (Сумма по i от 1 до n - 1) C_i * C_(n - 1 - i).

Это соотношение легко получается из (*). Для этого надо перебрать все возможные последовательности d_1 и d_2, являющиеся правильными скобочными последовательностями, такие, что (d_1)d_2 образуют новые правильные скобочные последовательности необходимой нам длины.

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

Генерация следующей скобочной последовательности:

Пусть нам известна строка s, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то - "No solution". Воспользуемся интерпретацией (**). Чтобы получить следующий битовый вектор надо найти самый последний нулевой элемень, заменить его на единицу, а элементы следующие за ним сделать минимально возможными(все нули). Тоже самое и со скобочными последовательностями, только после замены нуля на единицу оставшиеся скобки надо расположить в минимальном порядке (в виде (***)):

 function next(var s: string): boolean;
   var 
     i, k, l:integer;    
   begin  
     k := 0;  {счетчик для закрывающихся скобок}
     l := 0;  {счетчик для закрывающихся скобок}
     for i := length(s) downto 1 do  {Начинаем перебирать скобки с конца}
       begin
         if s[i] = '(' then 
           begin
             inc(l);  
             if k > l then  {встретив открывающуюся скобку, которую можно поменять на закрывающуюся, меняяем ее и выходим из цикла}
             break;
           end 
         else 
         inc(k);
       end;
     delete(s, length(s) - l - k + 1, k + l);  {удаляем все скобки включая открывающуюся}
     if s =  then
     next := false
     else
       begin
         s := s +')';  {записываем закрывающуюся скобку}
         for j := 1 to l do  {расставляем скобки в минимально возможном порядке}
         s := s + '(';
         for j := 1 to k - 1 do
         s := s + ')';
         next := true;
       end;
   end;

Если эта функция после выполнения выводит true тогда надо напечатать полученную строку s, если false, то следует вывести "No solution".

Получение лексикографического порядка:

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

 procedure (n: integer);
   var
     s: string;
     j: integer;
     t: boolean;
     begin
       s := ;
       if n = 0 then
       writeln()
       else
         begin
           for j := 1 to n do  {создаем начальную строку}
           s := s + '(';
           for j := 1 to n do
           s := s + ')';
           writeln(s);
           t := next(s);
           while t <> false do  {выполняем до тех пор пока не будет получена последняя последовательность}
             begin
               writeln(s);
               t := next(s);
             end;
         end;
     end;

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