Правильна дужкова послідовність

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Дужкові послідовністі — клас комбінаторних об'єктів. Будь-який представник цього класу складається з набору дужкових символів, тобто "(", «)», «[» та інших аналогічних. У дужковій послідовності може бути один або декілька типів дужок. Типом дужки називають пару фіксованих символів: відкриваючу та закриваючу дужки. Наприклад, «(1» та «)1»; «[10» та «]10». Зазвичай в комбінаториці розглядають правильні дужкові послідовності.

Правильна дужкова послідовність(ПДП) — окремий випадок дужкової послідовності. Правильні дужкові послідовності утворюють мову Діка[en] та формально визначаються таким чином:

  • "" (порожній рядок) - ПДП
  • ПДП, взята в дужки одного типу - ПДП
  • ПДП, до якої приписана зліва або справа ПДП - також ПДП

Кількість правильних дужкових послідовностей

[ред. | ред. код]

Кількість правильних дужкових послідовностей з дужок (, що відкривають та , що закривають) одного виду дорівнює числу Каталана [1], що можна вивести кількома способами:

і для

Це співвідношення легко отримати, звернувши увагу на те, що будь-яка непорожня правильна дужкова послідовність однозначно зображувана в формі , де — правильні дужкові послідовності.

  • Ще одне рекурентне співвідношення:

При цьому

Легко показати, що якщо в дужковій послідовності є типів дужок, тоді кількість можливих правильних послідовностей із відкриваючими дужками дорівнює добутку та . Дійсно, для кожної дужки, що відкривається із існує різних варіантів її вибору. Вибір дужки, що закривається однозначно визначений вже вибраною парною до неї, що відкривається і не враховується.

Генерація правильних дужкових послідовностей

[ред. | ред. код]

Введемо тепер лексикографічний порядок на дужкових послідовностях. В першу чергу зауважимо, що відкриваюча дужка іде раніше ніж закриваюча. Тепер кожному з типів дужок присвоїмо свій лексикографічний пріоритет. Вибір цього пріоритету не принциповий і ніяк не впливає на розвиток наступних міркувань. Через це будемо вважати, що iй тип дужок знаходиться на iй позиції в лексикографічному порядку. Очевидно, що першою послідовністю з відкриваючими дужками буде послідовність виду . Тепер розглянемо задачу про отримання наступної дужкової послідовності після даної.

Отримання наступної правильної послідовності

[ред. | ред. код]

Реалізація алгоритму генерації ПДП на С++

[ред. | ред. код]
#include <stdio.h>
#include <memory.h>

// повертає число Каталана для даної кількості пар дужок
long nCatalan(int n)
{
    long sum = 0;
    for (int i = 0; i <= n - 1; i++)
        sum += nCatalan(i) * nCatalan(n - 1 - i);
    return sum;
}

const int N = 3; // Кількість пар дужок, тобто довжина рядка (N * 2)

// рекурсивно знаходить і виводить на консоль дужкові послідовності
void bs(char cur_sequence[N * 2 + 1] = 0, int npos = 0, int left_brackets = 0)
{
    if (!cur_sequence)
    {
        cur_sequence = new char[N * 2 + 1];
        cur_sequence[N * 2] = 0;
    }
    if (npos == N * 2 - 1)
    {
        cur_sequence[npos] = ')';
        printf("%s\n", cur_sequence);
        cur_sequence[npos] = 0;
        return;
    }
    if (npos > 0)
    {
        if (left_brackets < N) 
        {
            cur_sequence[npos] = '(';
            bs(cur_sequence, npos + 1, left_brackets + 1);
            if (npos + 1 <= left_brackets * 2)
            {
                cur_sequence[npos] = ')';
                bs(cur_sequence, npos + 1, left_brackets);
            }
        }
        else
        {
            cur_sequence[npos] = ')';
            bs(cur_sequence, npos + 1, left_brackets);
        }
    }
    else
    {
        cur_sequence[0] = '(';
        bs(cur_sequence, npos + 1, left_brackets + 1);
    }
    cur_sequence[npos] = 0;
}

int main()
{
    bs();
    getchar();
    return 0;
}

Нерекурсивний варіант за допомогою бітового представлення С++

[ред. | ред. код]
#include <iostream>
#include <bitset>

using namespace std;

const int N = 10; //Кількість пар дужок

//Перевантажений оператор для полегшення виводу
template <size_t seq_size>
ostream& operator<<(ostream& os, const bitset<seq_size>& bs)
{
    for (size_t i = seq_size - 1; i > 0; --i)
    {
        os << (bs.test(i) ? "(" : ")");
    }
    os << ")";

    return os;
}

int main(int argc, char* argv[])
{
    const unsigned long int count = N * 2;

    unsigned long int base = 0;
    for (int i = count - 1; i >= count / 2; --i)
    {
        base += (0x1 << i);
    }
    //Перший біт повинен завжди дорівнювати 1 (послідовніть починається з відкриваючої дужки)
    //Крім того, після 100... немає правильних послідовностей.
    while ((base & (0x1 << (count - 1))) && (base > ((0x1 << (count - 1)) + (0x1 << (count - 3)) - 1)))
    {
        int sum = 0;
        for (int j = count - 1; (j >= 0) && (sum >= 0); --j)
        {
            if (base & (0x1 << j))
            {
                ++sum;
            }
            else
            {
                --sum;
            }
        }
        if (sum == 0)
        {
            cout << bitset<count>(base) << endl;
        }
        base -= 2;
    }
    return 0;
}

Зноски

[ред. | ред. код]
  1. Daniel Kleitman (2004). Principles of Discrete Applied Mathematics /29. Parentheses, Catalan Numbers and Ruin (PDF). Professor Kleitman's Homepage. Процитовано 7 серпня 2023.