Дужкові послідовності

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

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

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

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

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

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

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

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

• Відображення через біноміальні коефіцієнти:

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

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

${\displaystyle 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}}}$

При цьому ${\displaystyle C_{n}=R(0,2n).}$

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

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

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

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

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

#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.