Пра́вильная ско́бочная после́довательность (ПСП) — символьная последовательность, составленная в алфавите, состоящем из символов, сгруппированных в упорядоченные пары (типы скобок, графически обозначаемые "(" и «)», "[" и «]», «/*» и «*/» и т. п.), удовлетворяющая определённым правилам, обеспечивающим последовательную вложенность подпоследовательностей, обрамлённых открытой и закрытой скобкой одного типа.
Правильные скобочные последовательности образуют язык Дика и формально определяются следующим образом: пустая строка — правильная скобочная последовательность; правильная скобочная последовательность, взятая в скобки одного типа — правильная скобочная последовательность; правильная скобочная последовательность, к которой приписана слева или справа правильная скобочная последовательность — тоже правильная скобочная последовательность.
Число правильных скобочных последовательностей Число правильных скобочных последовательностей из скобок ( открывающих и закрывающих) одного вида равно числу Каталана , что можно вывести несколькими способами: Рекуррентное соотношение: и для Это соотношение легко получить, заметив, что любая непустая правильная скобочная последовательность однозначно представима в форме , где — правильные скобочные последовательности. Выражение через биномиальные коэффициенты:
Ещё одно рекуррентное соотношение:
При этом
Легко показать, что если в скобочной последовательности имеется типов скобок, то число возможных правильных скобочных последовательностей с открывающими скобками равно произведению на . Действительно, для каждой открывающей скобки из существует различных вариантов её выбора. Выбор закрывающей скобки однозначно определён уже выбранной парной ей открывающей и не учитывается.
Генерация правильных скобочных последовательностей Введём теперь лексикографический порядок на скобочных последовательностях. В первую очередь заметим, что открывающая скобка идёт раньше, чем закрывающая; так как скобочная последовательность, начинающаяся с закрывающей скобки, не является правильной. Теперь каждому из типов скобок присвоим свой лексикографический приоритет. Выбор этого приоритета не принципиален и ни на что не повлияет в ходе дальнейших рассуждений. Поэтому будем считать, что iй тип скобок находится на iй позиции в лексикографическом порядке. Очевидно, что первой последовательностью с открывающими скобками будет последовательность вида .
Пример рекурсивной реализации алгоритма генерации ПСП на 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); Категория:Комбинаторика