Правилни последователности от скоби

Съдържание

Дефиниции [редактиране]

Определение:
Поредици от скоби(англ.Bracket Sequences) е клас от комбинаторни обекти, представляващи поредица от символи в скоби.

Примери за последователности от скоби

  • [математика](())))([/математика]
  • [math])()()))()(()())[/math]
Определение:
Правилни последователности от скобие специален случай на последователност от скоби, дефинирана както следва:
  • [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] , който е правилна последователност от скоби. Трябва да изведем следващата последователност от скоби и ако тя не съществува, тогава да изведем "Няма решение". За да получим следващата последователност от скоби, трябва да намерим последната отваряща скоба, която може да бъде заменена (на това място можем да поставим затварящата скоба, без да нарушаваме условията за коректност на последователността от скоби, т.е. по време на проверката за коректност броячът трябва да е неотрицателен), да я заменим със затварящата и да заменим скобите, останали в края (ако има такива), с минималната възможна последователност от скоби:

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

Кажете ни числото [math]n[/math] . Трябва да отпечатате всички правилни последователности от скоби в лексикографски ред с [math]n[/math] отварящи скоби:

Също така, като използвате този алгоритъм, можете да получите последователност от скоби по номер и число от последователност от скоби, като добавите сравнение с желаната последователност и брояч. Но това далеч не е най-оптималният алгоритъм за този тип задачи и няма да работи добре за големи [math]n[/math] .

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

Нека [math]n[/math] е броят на двойките скоби в редицата. При дадена правилна последователност от скоби се изисква да се намери нейният номер в списъка с лексикографски подредени правилни последователности от скоби.

Нека научим как да изчисляваме спомагателната динамика [math]d[i][j][/math] , където [math]i[/math] е дължината на последователността от скоби (тя е „полуправилна“: всяка затваряща скоба съответства на съвпадаща отваряща скоба, но не всички отворени скоби са затворени), [math]j[/math] е балансът (т.е. разликата между броя отварящи и затварящи скоби ets), [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]\rm дълбочина[/math], трябва да повторим всички скоби, които са по-малки от текущия знак в реда, установен по-рано, да се опитаме да поставим тази скоба в текущата позиция (като по този начин получаваме нов баланс [math]\rm ndepth = \rm дълбочина \pm 1[/math] ) и да добавим към отговора броя на съответните "tail s" - завършвания (които имат дължина [math]2n - i - 1[/math], баланс на типове скоби [math]\rm ndepth[/math] и [math]k[/math]). Формулата за това количество се казва:

Тази формула е получена от следните съображения. Първо „забравяме“, че има множество видове скоби, и просто вземаме отговора от [math]d[2n - i - 1][] [/math] (подобно на случая с един тип скоби, където увеличихме [math]depth[/math] с [math]1[/math], ако скобата беше отворена, и намалихме с [math]1[/math], ако се затваряше, [math]depth = deep + 1[/math], ако се опитахме да поставим отваряща скоба, и [math]ndepth = дълбочина - 1[/math], ако затваряме). Сега нека изчислим как ще се промени отговорът поради наличието на [math]k[/math] типове скоби. Имаме [math]2n - i - 1[/math] недефинирани позиции, от които [math]\rm ndepth[/math] са скоби, които затварят някои от предварително отворените, което означава, че не можем да променяме типа на такива скоби. И тук са всички останали скоби (и те ще бъдат [math](2n - i - 1 - ) /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][\rm ndepth][/math] по стойността на [math]k^[/math] , за да вземем предвид, че този остатък може да съдържа скоби от различни типове, а сдвоените скоби в този остатък ще бъдат само [math]2n - i - 1 - \rm ndepth[/math] , тъй като скобите [math]\rm ndepth[/math] се затварят за отварящи скоби, които са извън този остатък (и следователно не можем да променяме техните типове).

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

Брой правилни последователности от скоби[редактиране]

Броят на правилните последователности от скоби със скоби от същия тип е същият като каталонските числа.