1. Введение
2. Числа и скобки
3. Скобочный ряд
4. Операции на скобках
5. Сервис on-line
СОДЕРЖАНИЕ (показать)

            2. Числа и скобки

Каждое множество слов Моцкина длины  k  (k >1) содержит два типа элементов: скобоч­ные наборы, которые унасле­дованы от множе­ства наборов длины  k−1, и уникаль­ные  k-на­боры. Коды всех унас­ледован­ных элементов начи­наются с нуля. У одного автора все девять слов Моцкина длины 4 приведены в следующем порядке:

0000, ()00, 0()0, 00(), (0)0, 0(0), (00), ()(), (()).
(2.1)

Цветом выделены четыре элемента с нулем в начале кода. Эти элементы унаследованы от множе­ства ПСПРН длины 3, и первое, что бросается в глаза, это их разобщенность в спис­ке (2.1), возникает желание разместить их компактно и в начале списка.

Если мы хотим ввести операции на скобках (почему бы и нет?), то лидирующие нули в кодах станут бал­лас­том. Напра­шива­ется такая анало­гия с чис­лами. При записи матема­тичес­ких выра­жений не ука­зывают лиди­рующие нули в числах, напри­мер, мы не пишем 111− 072 или совсем несу­разное 00111− 00072. Убирая лиди­рую­щие нули в числах, мы абстра­гиру­емся от разряд­ности чисел. Если же убрать лиди­рующие нули в словах Моцкина, то, например, в случае прямо­угольных реше­ток мы абстра­гиру­емся от ширины решеток. Пере­пишем элементы списка (2.1) в том же порядке, но уже в нормали­зованном виде, без бал­ласта в кодах:

0, ()00, ()0, (), (0)0, (0), (00), ()(), (()).
(2.2)

Естественно, в первом элементе один ноль надо сохранить, и это единственный элемент, начи­нающийся с нуля. Все остальные нормали­зованные ПСПРН (этот список можно продолжить до беско­неч­ности) начи­наются с откры­вающей скобки. Заме­тим, в списке (2.2) пред­став­лены только уни­каль­ные наборы (будем считать элемент "0" также уникаль­ным). Нево­ору­жен­ным глазом видно, что новый список не упоря­дочен, наборы рас­поло­жены хаотично, и напра­шива­ется сорти­ровка. Уложим все элементы списка (2.2) в линию, выст­роим цепь, иначе говоря, введем на мно­жестве нормали­зованных ПСПРН строгий порядок.

Продолжим аналогию с числами, точнее с натуральными десятичными числами. Проана­лизи­руем нату­раль­ный ряд на чисто фор­маль­ном уров­не. (Здесь и далее счи­таем, что нуль исклю­чен из нату­раль­ного ряда.) Каждое число зани­мает свое фикси­рован­ное место в ряду, исходя из сле­дующих двух крите­риев. Все  k-раз­рядные числа разме­щены компак­тно в своем знаковом диапа­зоне правее чисел с разряд­ностью мень­ше  k  и левее чисел с раз­ряд­ностью больше  k. И вто­рое, внутри каждого знако­вого диапа­зона дейст­вует строгий лекси­когра­фичес­кий порядок, в основе кото­рого лежит система нера­венств 0<1<2<3<4<5<6<7<8<9. Исполь­зуя ана­ло­гич­ные крите­рии, пост­роим стро­гий поря­док на множе­стве нормали­зованных ПСПРН.

Первый критерий связан с длиной слов Моцкина, и здесь все просто. Элемент с одним знаком "0" (аналог однораз­рядных нату­раль­ных чисел) един­ствен­ный, поэтому с него начнем цепь, прис­воив ему индекс 1. Элемент с двумя знаками (аналог двух­раз­ряд­ных чисел) также един­ствен­ный – это смежные парные скобки "( )". Смежные скобки размес­тим на втором месте, т.е. под индексом 2. В трех­зна­ковом диапа­зоне два элемента "( )0", "(0)". И здесь надо вво­дить лекси­когра­фичес­кий поря­док.

Установим лексикографический порядок с помощью неравенств  0 < ( < ). Нера­вен­ства логи­чны, так как единс­твенный символ первого элемента ноль, и естес­твенно счи­тать ноль мини­маль­ным знаком (или знаком с наимень­шим весом). Другие нормали­зованные ПСПРН начи­на­ются с левой скоб­ки, поэтому мы указали левую скобку второй в цепочке нера­венств. В итоге, на 3-ем и 4-ом местах в упоря­дочен­ном списке раз­меща­ются соот­ветст­венно "(0)" и "( )0". Осталь­ные эле­менты также нес­ложно выст­роить в цепочку. Полу­чаем сле­дую­щую после­дова­тель­ность:

0, (), (0), ()0, (00), (0)0, (()), ()00, ()()
(2.3)

Можно получить такой же порядок, если просто закодировать скобки. Напри­мер, если левую скобку кодиро­вать 1, пра­вую – 2, а затем числа отсор­тиро­вать по воз­рас­танию, то полу­чим экви­вален­тную после­дова­тель­ность троич­ных чисел 0, 12, 102, 120, 1002, 1020, 1122, 1200, 1212. Но при дру­гой коди­ровке можно полу­чить иную после­дова­тель­ность.

Рассмотрим рисунок, который мы позаимствовали у Robert M. Dickau. реш-4 Девять путей дли­ны 4 соот­ветс­твуют тем же словам Моцкина. Как видим, пути приве­дены в по­ряд­ке, обрат­ном (2.3). Можно ска­зать, автор для упоря­доче­ния при­дер­жи­вался сис­темы обратных нера­венств  0 > ( > ). Конечно, в каждом кон­крет­ном случае исполь­зова­ния скобочных наборов порядок их перечис­ления не имеет практи­ческого значения. Мно­гое зави­сит от харак­тера и особен­ности задач, которые стоят перед разра­ботчи­ками того или иного прило­жения. В этой работе пред­лага­ется, во-пер­вых, сгруп­пиро­вать и упако­вать всевоз­можные скобоч­ные наборы произ­вольной длины и, во-вто­рых, выст­роить наборы в линию "по ранжиру" по образцу нату­рального ряда со всеми выте­ка­ющими отсюда послед­стви­ями.

Чисто логически мы вводим простой и удобный строгий порядок на мно­жестве скобочных наборов. Выделим четыре этапа пост­роения стро­гого порядка:

 

<<   Введение   ||   Скобочный ряд   >>