3. Идентификация

Еремин Геннадий
опубликовано 17 May 2015 13:46

 

Все элементы ряда Дика уникальные (первое условие лексикографического ряда), поэтому слова Дика занимают в последовательности фиксированные места. Иначе говоря, каждому слову Дика соответствует определенный порядковый номер (индекс), а каждому целому положительному числу можно поставить в соответствие единст­венное слово Дика. Можно сказать и так: между скобочными наборами ряда Дика и числами натурального ряда существует взаимно-однозначное соответствие.

Реализовать такое соответствие можно, решив следующие две идентификационные задачи: а) вы­числение порядкового номера слова Дика и б) реконструкция слова Дика по заданному натуральному числу. Сошлемся еще раз на ресурс, где приведены алгоритмы без достаточных, на наш взгляд, пояснений. На этой странице мы опишем и докажем логику этих алгоритмов с привлечением треугольника Дика.

Индекс произвольного слова Дика может быть задан двояко: абсолютный индекс – порядковый номер элемента в ряде Дика или относительный индекс – порядковый номер слова среди скобочных наборов фиксированной длины. Во втором случае дополнительно указывается число пар скобок. Связь между абсолютным индексом I и относительным индексом I_0 слова Дика длиной 2n очевидна:

    \[I = I_0 + \sum_{k=1}^{n-1} c_k.\]

Напомним, ряд Дика начинается с элемента  ( ).

Вычисление индекса слова Дика

Длина заданного скобочного набора известна, поэтому требуемый знаковый диапазон ряда Дика определяется сразу. Вычислить относительный индекс можно прямым перебором от начала или обратным перебором с конца диапазона (направление перебора определяется по начальным символам слова). И это самый простой способ, если длина скобочных наборов невелика – порядка 20 пар скобок, когда надо перебрать не более 1010 слов Дика. Но уже при удвоении числа скобок такой перебор нереален.

Треугольник Дика содержит исчерпывающую информацию по взаимному распо­ложению элементов в ряде Дика. Используя динамику, можно просто и быстро вычислить номер скобочного набора, практически за один просмотр скобок. Будем искать относительный индекс слова Дика среди скобочных наборов такой же длины. Сначала опишем логику рассматриваемого метода.

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

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

Алгоритм заканчивается после просмотра всех левых скобок слова Дика. Следова­тельно, для определения номера скобочного набора достаточно зафиксировать все правые скобки, предшествующие левым скобкам, рассчитать и просуммировать прыжки по скобочному ряду.

Пример 3.1. Вернемся к скобочному набору из примера 2.1

( ( ( ( ( ( ) ) ) )

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

фрагментНа рис. 5 на фоне тре­угольника Дика показана соответствующая ломаная линия (без заключи­тельных нисходящих звеньев). Нам потребуется опорный треугольник с внешней нисходящей диа­гональю – череда меток 1, 6, 20, 48 и т.д. В скобоч­ном наборе 6 пар скобок, поэтому мы выделили в опорном треугольнике центральный столбец (узлы с абсциссой 6). Вокруг 6-ого столбца центри­руются две интересующие нас зеркальные пары (4,4)~(8,4) и (5,5)~(7,5). На рисунке зеркала обведены синим цветом, путь Дика показан красными стрелками.

Предварительно индекс заданного набора принимаем равным 1. Первые три диагональных звена восходящие, и на этом участке индекс не меняется. Но в точке (3,3) кривая делает излом, и здесь индекс должен быть увеличен, потому что группа путей с 4-ым восходящим звеном (зеленая стрелка) из точки (3,3) в точку (4,4) соответствует словам Дика с меньшими индексами. Количество этих путей равно обратной метке точки (4,4), которая, в свою очередь, равна прямой метке зеркальной точ­ки (8,4), т.е. d^{-1}_{4,4} \!=\! d_{8,4} \!=\! 20. Иначе говоря, надо пропустить 20 элементов ряда Дика с четырьмя левыми скобками в начале кода. В результате выполняется первый прыжок по ряду, текущий индекс нашего набора становится равным 1+20=21.

Следующие два звена восходящие, индекс не меняется. Затем следует нисходящее звено из точки (6,4) в точку (7,3), и снова необходим скачок. Анализ новой зеркальной пары показывает, что надо пропустить еще один элемент ряда Дика, поскольку d^{-1}_{7,5}=d_{5,5}=1. Индекс становится равным 22.

Пройдя последнее восходящее звено, мы выходим на внешнюю нисходящую диагональ опорного треугольника. Зафиксировать выход достаточно просто: для узла такой диагонали сумма координат равна 2n (в нашем случае 12). Конечные нисходящие звенья ломаной линии не меняют индекс заданного набора, и на этом расчет заканчивается.

Таким образом, заданный скобочный набор размещается под номером 22 в 6-ом диа­пазоне ряда Дика. Чтобы получить абсолютный индекс, надо учесть элементы предшествующих пяти диапазонов, т.е. подсуммировать соответ­ствующие числа Каталана. В конечном итоге абсолютный индекс равен 22 \!+\! (1\!+\!2\!+\!5\!+\!14\!+\!42) \!=\! 86.

Максимальное слово Дика в  n-ом диапазоне представляет собой последовательный набор из n блоков парных скобок ()()\ldots() и имеет относительный индекс cn. Если применить рассмотренную методику для расчета индекса макси­мума, то придется сложить все метки в третьей строке соответствующего опорного треугольника. Отсюда получаем еще одну формулу для чисел Каталана:

    \[c_n=1+\sum_{i=1}^{n-1} d_{2i,2}, \;\; n>0.\]

Реконструкция слова Дика по индексу

В рассмотренной методике, просматривая скобочный набор, мы суммировали метки отобранных узлов треугольника Дика. Здесь обратная ситуация: из заданного индекса надо вычленить (извлечь) слагаемые суммарного скачка.

Будем считать, что заданы относительный индекс I0 слова Дика и число пар ско­бок n. В случае, если известен абсолютный индекс, то последовательно вычитаются числа Каталана, пока не получим ноль или отрицательное число. Последнее положительное (ненулевое) значение и будет относительным индексом, а индекс последнего вычитаемого числа Каталана – число пар скобок (номер знакового диапазона).

Определимся со значением скачка Jmp по скобочному ряду для перемещения от начального набора к конструируемому, очевидно сначала \mbox{Jmp} \!=\! I_0 \!-\! 1. Величину Jmp надо разложить на слагаемые, которые равны пошаговым перемещениям по скобочному ряду. А эти перемещения связаны, в свою очередь, с теми нисходящими звеньями ломаной линии, которые и определяют индекс.

Ломаная линия строится в процессе обхода опорного треугольника, начиная с внешней восходящей диагонали, с переходом на внутренние диагонали при отборе подходящих меток с одновременной корректировкой величины Jmp. Процесс заканчивается, как только ломаная выйдет на внешнюю нисходящую диагональ с обнулением Jmp. Очевидно, мы сразу попадем на внешнюю нисходящую, двигаясь по восходящей, если изначально \mbox{Jmp} \!=\! 0.

Итак, начинаем ломаную линию от узла (0,0), поднимаемся в точку (1,1), поскольку все слова Дика начинаются с левой скобки. Далее надо выбирать между звеном подъема и звеном спада. Сравниваем Jmp и обратную метку следующего узла (2,2) по восходящей диагонали. Если  \mbox{Jmp} \!<\!  d^{-1}_{2,2}, скачок невозможен, и надо прокладывать путь далее по восходящей диагонали, при этом Jmp остается прежним. В противном случае выбирается звено спада, ломаная линия делает излом в точке (1,1),  и мы выходим к узлу (2,0). При этом выполняется первый скачок по ряду Дика, размер скачка равен  d^{-1}_{2,2}, и  на эту же величину уменьшается Jmp.

Далее процесс продолжается аналогичным образом. В общем случае, находясь в узле (i,j) и сравнивая текущее значение Jmp с обратной меткой контрольного узла (i\!+\!1,j\!+\!1), мы определяемся со следующим звеном ломаной линии. Если  \mbox{Jmp} \!<\! d^{-1}_{i+1,j+1}, выбираем звено подъема, иначе выбирается звено спада с одновременной корректировкой Jmp. Когда кривая выйдет на внешнюю нисходящую диагональ опорного треугольника, остается прописать последние нисходящие звенья до конечной точки (2n,0).

Пример 3.2. Построим слово Дика с абсолютным индексом 1329. Сначала найдем относительный индекс:

    \[I_0 = 1329-1-2-5-14-42-132-429 = 704\]

Последним вычитаемым оказалось число Каталана  c_7 \!=\! 429, поэтому будем искать слово Дика с относительным индексом 704 в 8-ом диапазоне ряда (n \!=\! 8). Начальное значение скачка равно \mbox{Jmp} \!=\! 704 \!-\! 1 \!=\! 703.

путь ДикаНа рис. 6 показан рабочий фраг­мент опорного треугольника с основанием 16, для наглядности в узлах проставлены обратные метки. Красным цветом прори­сована ломаная линия, синим цветом обведены метки контрольных узлов, которые повлияли на вид кривой. Первый излом произошел в точке (2,2), здесь выполнен первый сдвиг по скобочному ряду на 572 элемента. В результате текущее значение скачка изменилось \mbox{Jmp} \!=\! 703 \!-\! 572 \!=\! 131.

Второй излом образовался в точке (5,3), и следующие два нисходящих звена дают дополнительные сдвиги на 75 и 48 элементов ряда Дика. Текущее значение скачка стало равным \mbox{Jmp} \!=\!\! 132\!\!-\!\!75\!\!-\!\!48 \!\!=\!\! 8. Далее выполняется сдвиг на 5 элементов в точке (9,3) и еще три сдвига каждый на один элемент в точках (11,4), (12,3), (13,2). Наконец, ломаная линия выходит на внешнюю нисходящую диагональ, последнее звено спада завершает реконструкцию скобочной последова­тельности (()(())(()()))(). Очевидно, если сложить метки задействованных контрольных точек, то получим начальное значе­ние Jmp.


<<<<<  Начала динамики  ||  Полиномы Дика  >>>>>

Добавить комментарий