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

Пра́вильная ско́бочная после́довательность (ПСП) — символьная последовательность, составленная в алфавите, состоящем из символов, сгруппированных в упорядоченные пары (типы скобок, графически обозначаемые "(" и «)», "[" и «]», «/*» и «*/» и т. п.), удовлетворяющая определённым правилам, обеспечивающим последовательную вложенность подпоследовательностей, обрамлённых открытой и закрытой скобкой одного типа.

Правильные скобочные последовательности образуют язык Дика и формально определяются следующим образом:

• пустая строка — правильная скобочная последовательность;
• правильная скобочная последовательность, взятая в скобки одного типа — правильная скобочная последовательность;
• правильная скобочная последовательность, к которой приписана слева или справа правильная скобочная последовательность — тоже правильная скобочная последовательность.

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

Число правильных скобочных последовательностей из $2n$ скобок ($n$ открывающих и $n$ закрывающих) одного вида равно числу Каталана $C_{n}$, что можно вывести несколькими способами:

• Рекуррентное соотношение:

$C_{0}=1$ и $\qquad C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}$ для $n\geq 1.$

Это соотношение легко получить, заметив, что любая непустая правильная скобочная последовательность $\omega$ однозначно представима в форме $\omega =(\omega _{1})\omega _{2}$, где $\omega _{1,2}$ — правильные скобочные последовательности.

• Выражение через биномиальные коэффициенты:

$C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{n!(n+1)!}}={2n \choose n}-{2n \choose n-1}.$

• Ещё одно рекуррентное соотношение:

$R(o,n)={\begin{cases}1,&o=0\,\,{\mbox{and}}\,\,n=0;\\0,&n=0\,\,{\mbox{or}}\,\,o>n\,\,{\mbox{or}}\,\,o<0;\\R(o+1,n-1)+R(o-1,n-1),&{\mbox{otherwise}}.\\\end{cases}}$

При этом $C_{n}=R(0,2n).$

Легко показать, что если в скобочной последовательности имеется $k$ типов скобок, то число возможных правильных скобочных последовательностей с $n$ открывающими скобками равно произведению $C_{n}$ на $k^{n}$. Действительно, для каждой открывающей скобки из $n$ существует $k$ различных вариантов её выбора. Выбор закрывающей скобки однозначно определён уже выбранной парной ей открывающей и не учитывается.

Генерация правильных скобочных последовательностей

Введём теперь лексикографический порядок на скобочных последовательностях. В первую очередь заметим, что открывающая скобка идёт раньше, чем закрывающая; так как скобочная последовательность, начинающаяся с закрывающей скобки, не является правильной. Теперь каждому из $k$ типов скобок присвоим свой лексикографический приоритет. Выбор этого приоритета не принципиален и ни на что не повлияет в ходе дальнейших рассуждений. Поэтому будем считать, что i^й тип скобок находится на i^й позиции в лексикографическом порядке. Очевидно, что первой последовательностью с $n$ открывающими скобками будет последовательность вида $(_{1}(_{1}...(_{1})_{1})_{1}...)_{1}$.

Пример рекурсивной реализации алгоритма генерации ПСП на PHP

<?php

function generateBracketsSequence(
    int $length,
    int $countOpenBrackets = 0,
    int $countCloseBrackets = 0,
    string $sequence = '',
): void {

    if (mb_strlen($sequence) < $length * 2) {

        if ($countOpenBrackets < $length) {
            generateBracketsSequence(
                $length,
                $countOpenBrackets + 1,
                $countCloseBrackets,
                $sequence . '(',
            );
        }

        if ($countCloseBrackets < $countOpenBrackets) {
            generateBracketsSequence(
                $length,
                $countOpenBrackets,
                $countCloseBrackets + 1, 
                $sequence . ')',
            );
        }

    } else {
        echo $sequence.' - '."\r\n";
    }

}

generateBracketsSequence(4);