1632
правки
Изменения
м
Скобочная последовательность - класс комбинаторных объектов, представляющий собой последовательность скобочных символов.== Определения ==
Пример{{Определение|id = def1|definition ='''Скобочная последовательность''' (англ. ''Bracket Sequences'') {{---}} класс комбинаторных объектов, представляющих собой последовательность скобочных символов.}}'''Примеры скобочных последовательностей'''*<tex>(())))(</tex>*<tex>)()()))()(()())</tex>{{Определение|id = def1|definition ='''Правильная скобочная последовательность''' (анлг. ''Correct Bracket Sequences'') {{---}} частный случай скобочной последовательности, определяющийся следующими образами:
Определение:== Алгоритм проверки правильности скобочной последовательности ==
Правильная Пусть нам дана скобочная последовательность , записанная в строку <tex>s</tex>. Возьмем переменную <tex>\mathtt{counter}</tex>, <tex>\mathtt{counter} = 0</tex>, в которой мы будем поддерживать баланс. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем <tex>\mathtt{counter}</tex> на <tex>1</tex>, закрывающую {{- частный случай скобочной последовательности--}} уменьшаем на <tex>1</tex>. Если на протяжении всего перебора <tex>\mathtt{counter}</tex> было неотрицательным (не встречалось закрывающих скобок, определяющийся следующими образами:для которых не было соответствующих открывающих) и после завершения осталось нулем (все открывающие скобки закрыты, при этом нет лишних закрытых скобок), то скобочная последовательность правильна.
- ""(пустая строка) есть правильная скобочная последовательность; - правильная скобочная последовательность, взятая в скобки есть правильная скобочная последовательность;(*) - скобочная последовательность, к которой приписана слева или справа другая скобочная последовательность, есть правильная скобочная последовательность;===Псевдокод===
Пример '''boolean''' check(s:'''string'''): counter = 0 '''for''' i = 1 '''to''' length(s) '''if''' s[i] == '(' counter++ '''else''' counter-- '''if''' counter < 0 '''return''' ''false'' '''return''' counter == 0
(())(()())Надо отметить, что скобочные последовательности могут состоять не только из одного типа скобок. При этом недопустимо такое расположение, когда один тип скобок закрывает другой:
Алгоритм проверки правильности скобочной последовательности===Примеры скобочных последовательностей с несколькими типами скобок===
Пусть нам дана скобочная последовательность записанная в строку s. Возьмем переменную a, a = 0. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем a на 1, закрывающую *<tex>()[()]\{()()[]\}</tex> {{- уменьшаем на 1. Если на протяжении всего перебора a было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.--}} верно*<tex>[(]\{\})</tex> {{---}} неверно
псевдокод:В этом случае для проверки надо будет использовать [[Стек | стек]].
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;
Надо отметить чтоДля того, скобочные последовательности могут состоять не только из одного типа чтобы определить лексикографический порядок для правильных скобочных последовательностей, надо установить порядок на алфавите, например так <tex>(\ <\ )</tex>. Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, при этом недопустимо такое расположениепричем любая открывающаяся скобка должна быть меньше закрывающейся, когда один тип скобок закрывает другой:например <tex>(\ <\ [\ <\ )\ <\ ]</tex>.
Пример:===Примеры лексикографического порядка для <tex>n</tex> и <tex>k</tex>, где <tex>n</tex> {{---}} число открывающихся скобок, а <tex>k</tex> {{---}} число видов скобок===
В этом случае для проверки надо будет использовать стек.== Алгоритмы генерации ==
Лексикографический порядок порядок правильных скобочных последовательностей===Рекурсивный алгоритм получения лексикографического порядка===Пусть нам известно число <tex>n</tex>. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с <tex>n</tex> открывающимися скобками:
((((Если есть возможность поставить открывающую скобку, то мы ставим её.Аналогично после этого если есть возможность поставить закрывающую скобку, то после этого мы ставим и её.<br>Таким образом строки будут выведены в лексографическом порядке, так как сначала мы мы пытаемся поставить открывающую скобку.((()))...)))) (***)При этом мы перебираем все возможные варианты последующих скобок для каждого возможного префикса <tex>\mathtt{ans}</tex>, а следовательно в результате получаем все возможножные правильные скобочные последовательности
0000...000111...1111===Генерация следующей скобочной последовательности===
что соответствует самому маленькому возможному числуПусть нам известна строка <tex>s</tex>, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то вывести "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить (на этом месте мы можем поставить закрывающую скобку, не нарушив условия правильности скобочной последовательности, то есть на протяжении проверки на правильность counter должен быть неотрицательным), заменить ее на закрывающуюся, а последняяоставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:
0101...010101...0101===Получение лексикографического порядка===
что соответствует самому большому возможному числу. '''function''' order(n: '''int'''): s = "" '''for''' j = 1 '''to''' n s = s + '(' '''for''' j = 1 '''to''' n s = s + ')' print(s) '''while''' next(s) != "No Solution" print(s = next(s)) '''return'''
Для последовательностей Также с разным типом скобок надо определять свой порядокпомощью этого алгоритма можно получить скобочную последовательность по номеру и номер по скобочной последовательности, например "("<"["добавив сравнение с нужной последовательностью и счетчик. Но это далеко не самый оптимальный алгоритм для подобного типа задач и он не будет нормально работать для больших <")"tex>n<"]"/tex>.
Примеры лексикографического порядка для n и k, где n - число открывающихся скобок, а k - число видов скобок:===Получение номера последовательности===
k = 1Научимся считать вспомогательную [[Динамическое программирование | динамику]] <tex>d[i][j]</tex>, где <tex>i</tex> — длина скобочной последовательности (она "полуправильная": всякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки закрыты), <tex>j</tex> — баланс (т.е. разность между количеством открывающих и закрывающих скобок), <tex>d[i][j]</tex> — количество таких последовательностей. При подсчёте этой динамики мы считаем, что скобки бывают только одного типа.
(()())<tex>d[i][j] = d[i-1][j-1] + d[i-1][j+1]</tex>
()(())Перейдём теперь к решению самой задачи. Сначала пусть допустимы только скобки одного типа:
n Пусть теперь разрешены скобки <tex>k</tex> типов. Тогда при рассмотрении текущего символа <tex>s[i]</tex> до пересчёта <tex>\rm depth</tex> мы должны перебирать все скобки, которые меньше текущего символа в установленном ранее порядке, пробовать ставить эту скобку в текущую позицию (получая тем самым новый баланс <tex>\rm ndepth = 2;\rm depth \pm 1</tex>), и прибавлять к ответу количество соответствующих "хвостов" {{---}} завершений (которые имеют длину <tex>2n - i - 1</tex>, баланс <tex>\rm ndepth</tex> и <tex>k</tex> типов скобок). Утверждается, что формула для этого количества имеет вид:
[()]===Получение k-й последовательности===
[]()Пусть <tex>n</tex> — количество пар скобок в последовательности. В данной задаче по заданному <tex>k</tex> требуется найти <tex>k</tex>-ую правильную скобочную последовательность в списке лексикографически упорядоченных последовательностей.
Алгоритм генерации лексикографического порядка будет предложен нижеКак и в предыдущем разделе, посчитаем динамику <tex>d[i][j]</tex> — количество правильных скобочных последовательностей длины <tex>i</tex> с балансом <tex>j</tex>.
Количество правильных скобочных последовательностей. Числа КаталанаПусть сначала допустимы только скобки одного типа:
Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана. '''string''' get_sequence(n: '''int''', k: '''int'''): depth = 0 s = "" '''for''' i = 0 '''to''' 2 * n - 1 '''if''' d[2 * n - (i + 1)][depth + 1] <tex>\geqslant</tex> k s += '(' depth++ '''else''' k -= d[2 * n - (i + 1)][depth + 1] s += ')' depth-- '''return''' s
Числа Каталана представляют собой:Пусть теперь разрешён не один, а <tex>k</tex> типов скобок. Тогда алгоритм решения будет отличаться от предыдущего случая только тем, что мы должны домножать значение <tex>d[2n - i - 1][\rm ndepth]</tex> на величину <tex>k^{(2n - i - 1 - \rm ndepth) / 2}</tex>, чтобы учесть, что в этом остатке могли быть скобки различных типов, а парных скобок в этом остатке будет только <tex>2n - i - 1 - \rm ndepth</tex>, поскольку <tex>\rm ndepth</tex> скобок являются закрывающими для открывающих скобок, находящихся вне этого остатка (а потому их типы мы варьировать не можем).
- количество неизоморфных упорядоченных бинарных деревьев с корнем и Сложность данного алгоритма <tex>O(n^2 +1 листьями; - Количество способов соединения 2n точек на окружности n непересекающимися хордами; - количество разбиений выпуклого (n+2\cdot k)-угольника на треугольники непересекающимися диагоналями; - Количество правильных скобочных последовательностей имеющих n открывающихся скобок</tex>.
c_0 = 1; - так как существует только одна скобочная последовательность с 0 открывающихся скобок - пустая= См. также ==*[[Числа Каталана]]*[[Комбинаторные объекты]]*[[Лексикографический порядок]]*[[Генерация комбинаторных объектов в лексикографическом порядке]]*[[Получение номера по объекту]]*[[Получение объекта по номеру]]*[[Получение следующего объекта]]
C_n = (Сумма по i от 1 до n - 1) C_i * C_(n - 1 - i).= Источники ==
Это соотношение легко получается из (*)[http://ru.wikipedia. Для этого надо перебрать все возможные org/wiki/%D0%A1%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8 Скобочные последовательности d_1 и d_2, являющиеся правильными скобочными последовательностями, такие, что (d_1)d_2 образуют новые правильные скобочные последовательности необходимой нам длины.Материал из Википедии — свободной энциклопедии]
Алгоритмы для генерации следующей правильной скобочной последовательности в лексекографическом порядке и самого лексикографического порядка* [http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8 Правильная скобочная последовательность, Материал из Википедии — свободной энциклопедии]
Генерация следующей скобочной * [http://e-maxx.ru/algo/bracket_sequences MAXimal :: algo :: Правильные скобочные последовательности:]
Пусть нам известна строка 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.
rollbackEdits.php mass rollback
*<tex>\varepsilon</tex> (пустая строка) есть правильная скобочная последовательность;*пусть <tex>S</tex> {{---}} правильная скобочная последовательность, тогда <tex>(S)</tex> есть правильная скобочная последовательность;*пусть <tex>S1</tex>, <tex>S2</tex> {{---}} правильные скобочные последовательности, тогда <tex>S1S2</tex> есть правильная скобочная последовательность;}}'''Примеры правильных скобочных последовательностей'''*<tex>((()()()()))</tex>*<tex>(())(()())</tex>
{| class="wikitable" !colspan="2" style="padding:7px"| <tex>n = 3</tex> !colspan="3" style="padding:7px"| <tex>k = 1</tex> |- !style="padding:7px"|<tex>((()))</tex> !style="padding:7px"|<tex>(()())</tex> !style="padding:7px"|<tex>(()[)()</tex> !style="padding:7px"|<tex>()(())</tex> !style="padding:7px"|<tex>()]{()()[]</tex> |} - верно
{| class="wikitable" cellpadding="3" !colspan="2" style="padding:7px"|<tex>n = 2</tex> !colspan="2" style="padding:7px"|<tex>k = 2</tex> |- !style="padding:7px"|<tex>()[]</tex> !style="padding:7px"|<tex>([])</tex> !style="padding:7px"|<tex>[()]{</tex> !style="padding:7px"|<tex>[]()</tex> |}) - неверно
Для того чтобы определить лексикографический порядок для правильных скобочных последовательностей будем интерпретировать открывающуюся скобку как "запуска алгоритма необходимо сделать вызов <tex>\mathrm{gen}(n</tex>, <tex>0</tex>, <tex>0"</tex>, а закрывающуюся как <tex>"1")</tex>.*<tex> \mathtt{ans}</tex> {{---}} строка, в которой мы считаем ответ*<tex> \mathtt{counter\_open}</tex> - количество открывающих скобок в данный момент*<tex> \mathtt{counter\_close}</tex> - количество закрывающих скобок в данный момент '''function''' gen(n: '''int''', counter_open: '''int''', counter_close: '''int''', ans: '''string'''): '''if''' counter_open + counter_close == 2 **n print(ans) '''return''' '''if''' counter_open < n gen(n, counter_open + 1, counter_close, ans + '('). Тогда первая последовательность с '''if''' counter_open > counter_close gen(n открывающимися скобками будет иметь вид:, counter_open, counter_close + 1, ans + ')')
'''string''' next(s: '''string'''): counter_close = 0 counter_open = 0 '''for''' i = length(s)...'''downto''' 1 '''if''' s[i] == '(' counter_open++ '''if''' counter_close > counter_open '''break''' '''else''' counter_close++ <font color="Green">// начиная с символа с индексом "length(s)- counter_open - counter_close" удаляем все символы (индексация с 0)</font> remove(s[length(s)...- counter_open - counter_close], s[length(s) - 1]) '''if''' s == "" '''return''' "No Solution" '''else''' s = s +')' '''for''' j = 1 '''to''' counter_open s = s + '(' '''for''' j = 1 '''to''' counter_close - 1 s = s + ')' '''return''' s
Пусть нам известно число <tex>n</tex>. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с <tex>n</tex> открывающимися скобками:
Пусть <tex>n = 3;</tex> — количество пар скобок в последовательности. Требуется по заданной правильной скобочной последовательности найти её номер в списке лексикографически упорядоченных правильных скобочных последовательностей.
Считать эту динамику можно следующим образом. Пусть <tex>d[i][j]</tex> — величина, которую мы хотим посчитать. Если <tex>i = 0</tex>, то ответ понятен сразу: <tex>d[0][0] = 1</tex>, все остальные <tex>d[0][j] = 0</tex>. Пусть теперь <tex>i > 0</tex>, тогда переберём, чему мог быть равен последний символ этой последовательности. Если он был равен <tex>'('</tex>, то до этого символа мы находились в состоянии <tex>((i-1,j-1)</tex>. Если он был равен <tex>')'</tex>, то предыдущим было состояние <tex>(i-1,j+1)</tex>. Таким образом, получаем формулу:
(()считается, что все значения <tex>d[i][j]</tex> при отрицательном <tex>j</tex> равны нулю). Таким образом, эту динамику мы можем посчитать за <tex>O(n^2)</tex>.
'''int''' get_number(s: '''string'''): num = 0 depth = 0 '''for''' i = 0 '''to''' 2 * n - 1 '''if''' s[i] == '()()' depth++ '''else''' num += d[2 * n - i - 1][depth + 1] depth-- '''return''' num
<tex>d[2n - i - 1][ndepth] \cdot k = ^{(2n - i - 1 - ndepth) / 2;}</tex>
Эта формула выводится из следующих соображений. Сначала мы "забываем" про то, что скобки бывают нескольких типов, и просто берём ответ из <tex>d[2n - i - 1][{\rm ndepth}] </tex> (аналогично случаю с одним типом скобок, где мы увеличивали <tex>depth</tex> на <tex>1</tex>, если скобка открывающая, и уменьшали на <tex>1</tex>, если закрывающая, <tex>ndepth = depth + 1</tex>, если мы пробуем поставить открывающую скобку, и <tex>ndepth = depth - 1</tex>, если закрывающую). Теперь посчитаем, как изменится ответ из-за наличия <tex>k</tex> типов скобок. У нас имеется <tex>2n - i - 1</tex> неопределённых позиций, из которых <tex>\rm ndepth</tex> являются скобками, закрывающими какие-то из открытых ранее, — значит, тип таких скобок мы варьировать не можем. А вот все остальные скобки (а их будет <tex>(2n - i - 1 - {\rm ndepth})[]/ 2</tex> пар) могут быть любого из <tex>k</tex> типов, поэтому ответ умножается на эту степень числа <tex>k</tex>.
Сложность данного алгоритма <tex>O([]n^2 + n \cdot k)</tex>.
==Количество правильных скобочных последовательностей==Количество правильных скобочных последовательностей со скобками одного типа совпадает с [[Числа Каталана удовлетворяют следующему рекурентному соотношению:| числами Каталана]].
