Правильная скобочная последовательность python

Содержание:

Содержание

Определения [ править ]

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

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

  • [math](())))([/math]
  • [math])()()))()(()())[/math]
Определение:
Правильная скобочная последовательность (анлг. Correct Bracket Sequences) — частный случай скобочной последовательности, определяющийся следующими образами:

  • [math]varepsilon[/math] (пустая строка) есть правильная скобочная последовательность;
  • пусть [math]S[/math] — правильная скобочная последовательность, тогда [math](S)[/math] есть правильная скобочная последовательность;
  • пусть [math]S1[/math] , [math]S2[/math] — правильные скобочные последовательности, тогда [math]S1S2[/math] есть правильная скобочная последовательность;

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

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

Пусть нам дана скобочная последовательность, записанная в строку [math]s[/math] . Возьмем переменную [math]mathtt[/math] , [math]mathtt = 0[/math] , в которой мы будем поддерживать баланс. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем [math]mathtt[/math] на [math]1[/math] , закрывающую — уменьшаем на [math]1[/math] . Если на протяжении всего перебора [math]mathtt[/math] было неотрицательным (не встречалось закрывающих скобок, для которых не было соответствующих открывающих) и после завершения осталось нулем (все открывающие скобки закрыты, при этом нет лишних закрытых скобок), то скобочная последовательность правильна.

Псевдокод [ править ]

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

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

  • [math]()[()]<()()[]>[/math] — верно
  • [math][(]<>)[/math] — неверно

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

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

Для того, чтобы определить лексикографический порядок для правильных скобочных последовательностей, надо установить порядок на алфавите, например так [math]( lt )[/math] . Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например [math]( lt [ lt ) lt ][/math] .

Примеры лексикографического порядка для [math]n[/math] и [math]k[/math] , где [math]n[/math] — число открывающихся скобок, а [math]k[/math] — число видов скобок [ править ]

[math]n = 3[/math] [math]k = 1[/math]
[math]((()))[/math] [math](()())[/math] [math](())()[/math] [math]()(())[/math] [math]()()()[/math]
[math]n = 2[/math] [math]k = 2[/math]
[math]()[][/math] [math]([])[/math] [math][()][/math] [math][]()[/math]

Алгоритмы генерации [ править ]

Рекурсивный алгоритм получения лексикографического порядка [ править ]

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

Для запуска алгоритма необходимо сделать вызов [math]mathrm(n[/math] , [math]0[/math] , [math]0[/math] , [math]"")[/math] .

  • [math] mathtt[/math] — строка, в которой мы считаем ответ
  • [math] mathtt[/math] — количество открывающих скобок в данный момент
  • [math] mathtt[/math] — количество закрывающих скобок в данный момент

Если есть возможность поставить открывающую скобку, то мы ставим её. Аналогично после этого если есть возможность поставить закрывающую скобку, то после этого мы ставим и её.
Таким образом строки будут выведены в лексографическом порядке, так как сначала мы мы пытаемся поставить открывающую скобку. При этом мы перебираем все возможные варианты последующих скобок для каждого возможного префикса [math]mathtt[/math] , а следовательно в результате получаем все возможножные правильные скобочные последовательности

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

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

Читайте также:  Ippon back power pro 1000

Получение лексикографического порядка [ править ]

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

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

Получение номера последовательности [ править ]

Пусть [math]n[/math] — количество пар скобок в последовательности. Требуется по заданной правильной скобочной последовательности найти её номер в списке лексикографически упорядоченных правильных скобочных последовательностей.

Научимся считать вспомогательную динамику [math]d[i][j][/math] , где [math]i[/math] — длина скобочной последовательности (она "полуправильная": всякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки закрыты), [math]j[/math] — баланс (т.е. разность между количеством открывающих и закрывающих скобок), [math]d[i][j][/math] — количество таких последовательностей. При подсчёте этой динамики мы считаем, что скобки бывают только одного типа.

Считать эту динамику можно следующим образом. Пусть [math]d[i][j][/math] — величина, которую мы хотим посчитать. Если [math]i = 0[/math] , то ответ понятен сразу: [math]d[0][0] = 1[/math] , все остальные [math]d[0][j] = 0[/math] . Пусть теперь [math]i gt 0[/math] , тогда переберём, чему мог быть равен последний символ этой последовательности. Если он был равен [math]'(‘[/math] , то до этого символа мы находились в состоянии [math](i-1,j-1)[/math] . Если он был равен [math]’)'[/math] , то предыдущим было состояние [math](i-1,j+1)[/math] . Таким образом, получаем формулу:

(считается, что все значения [math]d[i][j][/math] при отрицательном [math]j[/math] равны нулю). Таким образом, эту динамику мы можем посчитать за [math]O(n^2)[/math] .

Перейдём теперь к решению самой задачи. Сначала пусть допустимы только скобки одного типа:

Пусть теперь разрешены скобки [math]k[/math] типов. Тогда при рассмотрении текущего символа [math]s[i][/math] до пересчёта [math]
m depth[/math] мы должны перебирать все скобки, которые меньше текущего символа в установленном ранее порядке, пробовать ставить эту скобку в текущую позицию (получая тем самым новый баланс [math]
m ndepth =
m depth pm 1[/math] ), и прибавлять к ответу количество соответствующих "хвостов" — завершений (которые имеют длину [math]2n — i — 1[/math] , баланс [math]
m ndepth[/math] и [math]k[/math] типов скобок). Утверждается, что формула для этого количества имеет вид:

Эта формула выводится из следующих соображений. Сначала мы "забываем" про то, что скобки бывают нескольких типов, и просто берём ответ из [math]d[2n — i — 1][<
m ndepth>] [/math] (аналогично случаю с одним типом скобок, где мы увеличивали [math]depth[/math] на [math]1[/math] , если скобка открывающая, и уменьшали на [math]1[/math] , если закрывающая, [math]ndepth = depth + 1[/math] , если мы пробуем поставить открывающую скобку, и [math]ndepth = depth — 1[/math] , если закрывающую). Теперь посчитаем, как изменится ответ из-за наличия [math]k[/math] типов скобок. У нас имеется [math]2n — i — 1[/math] неопределённых позиций, из которых [math]
m ndepth[/math] являются скобками, закрывающими какие-то из открытых ранее, — значит, тип таких скобок мы варьировать не можем. А вот все остальные скобки (а их будет [math](2n — i — 1 — <
m ndepth>) / 2[/math] пар) могут быть любого из [math]k[/math] типов, поэтому ответ умножается на эту степень числа [math]k[/math] .

Сложность данного алгоритма [math]O(n^2 + n cdot k)[/math] .

Получение k-й последовательности [ править ]

Пусть [math]n[/math] — количество пар скобок в последовательности. В данной задаче по заданному [math]k[/math] требуется найти [math]k[/math] -ую правильную скобочную последовательность в списке лексикографически упорядоченных последовательностей.

Как и в предыдущем разделе, посчитаем динамику [math]d[i][j][/math] — количество правильных скобочных последовательностей длины [math]i[/math] с балансом [math]j[/math] .

Пусть сначала допустимы только скобки одного типа:

Пусть теперь разрешён не один, а [math]k[/math] типов скобок. Тогда алгоритм решения будет отличаться от предыдущего случая только тем, что мы должны домножать значение [math]d[i + 1][
m ndepth][/math] на величину [math]k^<(2n — i — 1 —
m ndepth) / 2>[/math] , чтобы учесть, что в этом остатке могли быть скобки различных типов, а парных скобок в этом остатке будет только [math]2n — i — 1 —
m ndepth[/math] , поскольку [math]
m ndepth[/math] скобок являются закрывающими для открывающих скобок, находящихся вне этого остатка (а потому их типы мы варьировать не можем).

Сложность данного алгоритма [math]O(n^2 + n cdot k)[/math] .

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

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

Читайте также:  Как отключиться от подписок на айфоне

Всем привет, кто может помочь с реализацией проверки на правильность скобочной последовательности через стек на Python. Суть проверки я знаю, и просто через условия реализовала, но со стеком не могу понять, помогите пожалуйста.

2 ответа 2

А мне понравился этот простой и хитрый алгоритм — главное чтобы строка в нем не имела символом, кроме ()[]<> , там даже объяснять ничего не нужно:

На самом деле, всё очень просто.

Вы идёте от начала строки. Каждый раз, когда встречаете открывающую скобку — кладёте её в стек. Каждый раз, когда встречаете закрывающую — убираете из стека ранее положенную скобку.

Если нужно убрать скобку из стека, а их там больше не осталось — последовательность неправильная. Если после разбора строки в стеке остались лишние скобки — последовательность неправильная. Во всех остальных случаях — правильная.

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

.collapse">Содержание

Этим постом начинается разбор задачек по алгоритмам, которые крупные IT-компании (Mail.Ru Group, Google и т.п.) так любят давать кандидатам на собеседованиях (если плохо пройти собеседование по алгоритмам, то шансы устроиться на работу в компанию мечты, увы, стремятся к нулю). В первую очередь этот пост полезен для тех, кто не имеет опыта олимпиадного программирования или тяжеловесных курсов по типу ШАДа или ЛКШ, в которых тематика алгоритмов разобрана достаточно серьезно, или же для тех, кто хочет освежить свои знания в какой-то определенной области.

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

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

1. Начнем с баян-баяныча: нужно сгенерировать все правильные скобочные последовательности со скобками одного вида (что такое правильная скобочная последовательность), где количество скобок равно k.

Эту задачу можно решить несколькими способами. Начнем с рекурсивного.

В этом способе предполагается, что мы начинаем перебирать последовательности с пустого списка. После того, как в список добавлена скобка (открывающая или закрывающая), снова выполняется вызов рекурсии и проверка условий. Какие могут быть условия? Необходимо следить за разницей между открывающими и закрывающими скобками (переменная cnt ) — нельзя добавить закрывающую скобку в список, если эта разница не является положительной, иначе скобочная последовательность перестанет быть правильной. Осталось аккуратно реализовать это в коде.

Сложность этого алгоритма — , дополнительной памяти требуется .

При заданных параметрах вызов функции выведет следующее:

Итеративный способ решения этой задачи: в этом случае идея будет принципиально другой — нужно ввести понятие лексикографического порядка для скобочных последовательностей.

Все правильные скобочные последовательности для одного типа скобок можно упорядочить с учётом того, что . Например, для n=6 самой лексикографически младшей последовательностью будет , а самой старшей — .

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

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

Сложность этого алгоритма такая же, как и в прошлом примере.

Кстати, есть несложный способ, который демонстрирует, что количество сгенерированных скобочных последовательностей для данного n/2 должно совпадать с числами Каталана.

Отлично, со скобками пока всё, теперь перейдем к генерированию подмножеств. Начнем с простой задачки.

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

Заметим, что количество подмножеств такого множества равно в точности . Если каждое подмножество представить в виде массива индексов, где означает, что элемент не входит в множество, а — что входит, тогда генерирование всех таких массивов будет являться генерированием всех подмножеств.

Если рассмотреть побитовое представление чисел от 0 до , то они будут задавать искомые подмножества. То есть для решения задачи необходимо реализовать прибавление единицы к двоичному числу. Начинаем со всех нулей и заканчиваем массивом, в котором одни единицы.

Сложность этого алгоритма — , по памяти — .

Читайте также:  P5wd2 premium core 2 duo

Теперь чуть-чуть усложним предыдущую задачу.

3. Дан упорядоченный массив по возрастанию с числами от до , требуется сгенерировать все его -элементные подмножества (решить итеративным способом).

Замечу, что по формулировке эта задача похожа на предыдущую и решать её можно с помощью примерно такой же методики: взять изначальный массив с единицами и нулями и последовательно перебрать все варианты таких последовательностей длиной

Однако требуются небольшие изменения. Нам нужно перебрать все -значные наборы чисел от до . Необходимо понять, как именно нужно перебирать подмножества. В данном случае можно ввести понятие лексикографического порядка для таких множеств.

Также упорядочим последовательность по кодам символов: (это, конечно, странно, но так надо, и сейчас поймем, почему). Например, для самой младшей и старшей будут последовательности и .

Осталось понять, как описать переход от одной последовательности к другой. Тут всё просто: если меняем на , то слева пишем лексикографически минимальное с учетом сохранения условия на . Код:

Сложность этого алгоритма — , по памяти — .

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

Теперь попробуем рекурсию. Идея простая: на этот раз обойдемся без описания, смотрите код.

Пример работы:

Сложность такая же, как и у прошлого способа.

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

Будем решать с помощью рекурсии. Решение похожа на предыдущее, где у нас есть вспомогательный список. Изначально он нулевой, если на -ом месте элемента стоит единица, то элемент уже есть в перестановке. Сказано — сделано:

Сложность этого алгоритма — , по памяти —

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

6. Сгенерировать все двумерные коды Грея длиной n.

Идея решения этой задачи классная, но если не знать решения, то бывает очень сложно додуматься. Замечу, что количество таких последовательностей равно .

Будем решать итеративно. Пусть мы сгенерировали какую-то часть таких последовательностей и они лежат в каком-то списке. Если мы продублируем такой список и запишем его в обратном порядке, то последняя последовательность в первом списке совпадает с первой последовательностью во втором списке, предпоследняя совпадает со второй и т.д. Соединим эти списки в один.

Что необходимо сделать, чтобы все последовательности в списке отличались друг от друга в одном разряде? Поставить в соответствующих местах одну единицу в элементы второго списка, чтобы получить коды Грея.

Это сложно воспринять «на слух», изобразим итерации этого алгоритма.

Сложность этой задачи — , по памяти такая же.

Теперь усложним задачу.

7. Сгенерировать все k-мерные коды Грея длиной n.

Понятно, что прошлая задача является лишь частным случаем этой задачи. Однако тем красивым способом, которым была решена прошлая задача, эту решить не получится, здесь необходимо перебирать последовательности в правильном порядке. Заведем двумерный массив . Изначально в последней строчке стоят единицы, а в остальных стоят нули. При этом в матрице также могут встречаться и . Здесь и отличаются друг от друга направлением: указывает вверх, указывает вниз. Важно: в каждом столбике в любой момент времени может быть только одна или , а остальные числа будут нулями.

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

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

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

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

Сложность алгоритма — , по памяти — .

Корректность данного алгоритма доказывается индукцией по , здесь я не будут описывать доказательство.

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