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

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

Кількість правильних дужкових послідовностей Кількість правильних дужкових послідовностей з дужок (, що відкривають та , що закривають) одного виду дорівнює числу Каталана , що можна вивести кількома способами: Рекурентне співвідношення: і для Це співвідношення легко отримати, звернувши увагу на те, що будь-яка непорожня правильна дужкова послідовність однозначно зображувана в формі , де — правильні дужкові послідовності. Відображення через біноміальні коефіцієнти:

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

При цьому

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

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

Введемо тепер лексикографічний порядок на дужкових послідовностях. В першу чергу зауважимо, що відкриваюча дужка іде раніше ніж закриваюча. Тепер кожному з типів дужок присвоїмо свій лексикографічний пріоритет. Вибір цього пріоритету не принциповий і ніяк не впливає на розвиток наступних міркувань. Через це будемо вважати, що 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 = '('; 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; }

Зноски