94
правки
Изменения
Новая страница: «Правильные скобочные последовательности Определение: Скобочная последовательность - кл...»
Правильные скобочные последовательности
Определение:
Скобочная последовательность - класс комбинаторных объектов, представляющий собой последовательность скобочных символов.
Пример:
(())))(
Определение:
Правильная скобочная последовательность - частный случай скобочной последовательности, определяющийся следующими образами:
- ""(пустая строка) есть правильная скобочная последовательность;
- правильная скобочная последовательность, взятая в скобки есть правильная скобочная последовательность;(*)
- скобочная последовательность, к которой приписана слева или справа другая скобочная последовательность, есть правильная скобочная последовательность;
Пример:
(())(()())
Алгоритм проверки правильности скобочной последовательности
Пусть нам дана скобочная последовательность записанная в строку 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 открывающимися скобками будет иметь вид:
((((...((()))...)))) (***)
0000...000111...1111
что соответствует самому маленькому возможному числу, а последняя:
()()...()()()...()()
0101...010101...0101
что соответствует самому большому возможному числу.
Для последовательностей с разным типом скобок надо определять свой порядок, например "("<"["<")"<"]".
Примеры лексикографического порядка для 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.
Определение:
Скобочная последовательность - класс комбинаторных объектов, представляющий собой последовательность скобочных символов.
Пример:
(())))(
Определение:
Правильная скобочная последовательность - частный случай скобочной последовательности, определяющийся следующими образами:
- ""(пустая строка) есть правильная скобочная последовательность;
- правильная скобочная последовательность, взятая в скобки есть правильная скобочная последовательность;(*)
- скобочная последовательность, к которой приписана слева или справа другая скобочная последовательность, есть правильная скобочная последовательность;
Пример:
(())(()())
Алгоритм проверки правильности скобочной последовательности
Пусть нам дана скобочная последовательность записанная в строку 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 открывающимися скобками будет иметь вид:
((((...((()))...)))) (***)
0000...000111...1111
что соответствует самому маленькому возможному числу, а последняя:
()()...()()()...()()
0101...010101...0101
что соответствует самому большому возможному числу.
Для последовательностей с разным типом скобок надо определять свой порядок, например "("<"["<")"<"]".
Примеры лексикографического порядка для 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.
