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

Правильна дужкова послідовність — це рядок, що складається лише з дужок, такий, що ця послідовність, якщо вставити в неї певні числа й математичні операції, дає коректний математичний вираз. Формально правильну дужкову послідовність можна означити так:

• $e$ (порожній рядок) є правильною дужковою послідовністю.
• якщо $s$ — правильна дужкова послідовність, то й $(s)$ — теж.
• якщо $s$ і $t$ — правильні дужкові послідовності, то й $s t$ — теж.

Наприклад, $(())()$ є правильною дужковою послідовністю, а $())($ — ні.

Звісно, аналогічно можна означити й інші дужкові послідовності з кількома типами дужок.

У цій статті ми розглянемо кілька класичних задач, пов'язаних із правильними дужковими послідовностями (для простоти ми називатимемо їх просто послідовностями): перевірку коректності, кількість послідовностей, пошук наступної в лексикографічному порядку послідовності, генерування всіх послідовностей заданого розміру, пошук індексу послідовності та генерування $k$-ї послідовності. Ми також розглянемо два варіанти цих задач: простіший, коли дозволено лише один тип дужок, і складніший, коли типів кілька.

Коли підходить цей алгоритм?

• Чи об'єкти задачі — це власне дужкові послідовності (рядки з дужок), які треба перевірити, занумерувати, згенерувати по порядку чи знайти $k$-ту?
• Чи треба згенерувати/проіндексувати конкретні послідовності, а не лише порахувати їхню кількість? (якщо потрібен лише підрахунок → Числа Каталана)
• Чи задача про збалансованість зводиться до балансу «відкрив/закрив» (можливо, з кількома типами дужок)?

Перевірка коректності

Ми хочемо перевірити, чи є заданий рядок правильним.

Спочатку припустимо, що є лише один тип дужок. Для цього випадку існує дуже простий алгоритм. Нехай $\text{depth}$ — це поточна кількість відкритих дужок. Спочатку $\text{depth} = 0$. Ми проходимо по всіх символах рядка: якщо поточний символ дужки — відкривна дужка, то збільшуємо $\text{depth}$, інакше зменшуємо. Якщо в якийсь момент змінна $\text{depth}$ стає від'ємною або в кінці вона відмінна від $0$, то рядок не є правильною послідовністю. Інакше — є.

Якщо ж задіяно кілька типів дужок, то алгоритм потрібно змінити. Замість лічильника $\text{depth}$ ми створюємо стек, у якому зберігатимемо всі відкривні дужки, які зустрічаємо. Якщо поточний символ дужки — відкривний, ми кладемо його на стек. Якщо ж закривний, то перевіряємо, чи непорожній стек і чи верхній елемент стека того самого типу, що й поточна закривна дужка. Якщо обидві умови виконуються, то прибираємо відкривну дужку зі стека. Якщо в якийсь момент одна з умов не виконується або в кінці стек непорожній, то рядок не є правильним. Інакше — є.

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

Формула

Кількість правильних дужкових послідовностей лише з одним типом дужок можна обчислити за допомогою чисел Каталана. Кількість правильних дужкових послідовностей довжини $2n$ ($n$ пар дужок) дорівнює:

$$\frac{1}{n+1} \binom{2n}{n}$$

Якщо дозволити $k$ типів дужок, то кожна пара може бути будь-якого з $k$ типів (незалежно від інших), тож кількість правильних дужкових послідовностей дорівнює:

$$\frac{1}{n+1} \binom{2n}{n} k^n$$

Динамічне програмування

З іншого боку, ці числа можна обчислити за допомогою динамічного програмування. Нехай $d[n]$ — це кількість правильних дужкових послідовностей з $n$ парами дужок. Зауважимо, що на першій позиції завжди стоїть відкривна дужка. А десь далі стоїть відповідна закривна дужка цієї пари. Зрозуміло, що всередині цієї пари є правильна дужкова послідовність, і так само після цієї пари є правильна дужкова послідовність. Отже, щоб обчислити $d[n]$, ми розглянемо, скільки правильних послідовностей з $i$ парами дужок міститься всередині цієї першої пари дужок і скільки правильних послідовностей з $n-1-i$ парами міститься після цієї пари. Відповідно, формула має вигляд:

$$d[n] = \sum_{i=0}^{n-1} d[i] \cdot d[n-1-i]$$

Початкове значення для цього рекурентного співвідношення — $d[0] = 1$.

Пошук наступної правильної послідовності в лексикографічному порядку

Тут ми розглядаємо лише випадок з одним допустимим типом дужок.

Маючи правильну послідовність, ми маємо знайти наступну (у лексикографічному порядку) правильну послідовність.

Має бути очевидно, що нам потрібно знайти найправішу відкривну дужку, яку можна замінити закривною, не порушуючи умову, що закривних дужок до цієї позиції не більше, ніж відкривних. Замінивши цю позицію, ми можемо заповнити решту рядка лексикографічно мінімальним способом: тобто спершу якомога більшою кількістю відкривних дужок, а потім заповнити решту позицій закривними дужками. Іншими словами, ми намагаємося лишити якомога довший префікс незмінним, а суфікс замінити на лексикографічно мінімальний.

Щоб знайти цю позицію, ми можемо проходити по символах справа наліво й підтримувати баланс $\text{depth}$ відкривних і закривних дужок. Коли ми зустрічаємо відкривну дужку, ми зменшуємо $\text{depth}$, а коли зустрічаємо закривну дужку, ми його збільшуємо. Якщо в якийсь момент ми зустрічаємо відкривну дужку, і баланс після обробки цього символу додатний, то ми знайшли найправішу позицію, яку можна змінити. Ми змінюємо символ, обчислюємо кількість відкривних і закривних дужок, які треба додати праворуч, і розставляємо їх лексикографічно мінімальним способом.

Якщо ми не знаходимо відповідної позиції, то ця послідовність уже є максимально можливою, і відповіді немає.

C++

bool next_balanced_sequence(string & s) {
    int n = s.size();
    int depth = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '(')
            depth--;
        else
            depth++;

        if (s[i] == '(' && depth > 0) {
            depth--;
            int open = (n - i - 1 - depth) / 2;
            int close = n - i - 1 - open;
            string next = s.substr(0, i) + ')' + string(open, '(') + string(close, ')');
            s.swap(next);
            return true;
        }
    }
    return false;
}

Python

def next_balanced_sequence(s: str):
    # Повертає наступну послідовність або None, якщо її немає.
    n = len(s)
    depth = 0
    for i in range(n - 1, -1, -1):
        if s[i] == '(':
            depth -= 1
        else:
            depth += 1

        if s[i] == '(' and depth > 0:
            depth -= 1
            open_cnt = (n - i - 1 - depth) // 2
            close_cnt = n - i - 1 - open_cnt
            return s[:i] + ')' + '(' * open_cnt + ')' * close_cnt
    return None

TypeScript

// Повертає наступну послідовність або null, якщо її немає.
function nextBalancedSequence(s: string): string | null {
  const n = s.length;
  let depth = 0;
  for (let i = n - 1; i >= 0; i--) {
    if (s[i] === '(') depth--;
    else depth++;

    if (s[i] === '(' && depth > 0) {
      depth--;
      const open = (n - i - 1 - depth) / 2;
      const close = n - i - 1 - open;
      return s.slice(0, i) + ')' + '('.repeat(open) + ')'.repeat(close);
    }
  }
  return null;
}

Go

// Повертає наступну послідовність і true, або "" і false, якщо її немає.
func nextBalancedSequence(s string) (string, bool) {
	n := len(s)
	depth := 0
	for i := n - 1; i >= 0; i-- {
		if s[i] == '(' {
			depth--
		} else {
			depth++
		}

		if s[i] == '(' && depth > 0 {
			depth--
			open := (n - i - 1 - depth) / 2
			closeCnt := n - i - 1 - open
			return s[:i] + ")" + strings.Repeat("(", open) + strings.Repeat(")", closeCnt), true
		}
	}
	return "", false
}

Ця функція обчислює за час $O(n)$ наступну правильну дужкову послідовність і повертає false, якщо наступної немає.

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

Інколи потрібно знайти й вивести всі правильні дужкові послідовності заданої довжини $n$.

Щоб згенерувати їх, ми можемо почати з лексикографічно найменшої послідовності $((\dots(())\dots))$, а потім продовжувати знаходити наступні в лексикографічному порядку послідовності за допомогою алгоритму, описаного в попередньому розділі.

Однак, якщо довжина послідовності невелика (наприклад, $n$ менше за $12$), то ми також можемо зручно згенерувати всі перестановки за допомогою функції C++ STL next_permutation і перевірити кожну на правильність.

Також їх можна згенерувати, використовуючи ідеї, які ми застосовували для підрахунку всіх послідовностей за допомогою динамічного програмування. Ці ідеї ми обговоримо в наступних двох розділах.

Індекс послідовності

Маємо правильну дужкову послідовність з $n$ парами дужок. Нам треба знайти її індекс у лексикографічно впорядкованому списку всіх правильних послідовностей з $n$ парами дужок.

Означимо допоміжний масив $d[i][j]$, де $i$ — це довжина дужкової послідовності (напівправильної: кожна закривна дужка має відповідну відкривну, але не кожна відкривна дужка обов'язково має відповідну закривну), а $j$ — поточний баланс (різниця між кількістю відкривних і закривних дужок). $d[i][j]$ — це кількість таких послідовностей, що відповідають заданим параметрам. Ми обчислюватимемо ці числа лише з одним типом дужок.

Для початкового значення $i = 0$ відповідь очевидна: $d[0][0] = 1$ і $d[0][j] = 0$ для $j > 0$. Тепер нехай $i > 0$, і ми розглядаємо останній символ послідовності. Якщо останнім символом була відкривна дужка $($, то попередній стан був $(i-1, j-1)$; якщо це була закривна дужка $)$, то попередній стан був $(i-1, j+1)$. Таким чином, ми отримуємо рекурентну формулу:

$$d[i][j] = d[i-1][j-1] + d[i-1][j+1]$$

Очевидно, що $d[i][j] = 0$ для від'ємного $j$. Отже, ми можемо обчислити цей масив за $O(n^2)$.

Тепер згенеруємо індекс для заданої послідовності.

Спершу нехай є лише один тип дужок. Ми використаємо лічильник $\text{depth}$, який каже нам, наскільки глибоко ми зараз вкладені, і проходитимемо по символах послідовності. Якщо поточний символ $s[i]$ дорівнює $($, то ми збільшуємо $\text{depth}$. Якщо поточний символ $s[i]$ дорівнює $)$, то ми маємо додати $d[2n-i-1][\text{depth}+1]$ до відповіді, врахувавши всі можливі закінчення, що починаються з $($ (а вони є лексикографічно меншими послідовностями), а потім зменшити $\text{depth}$.

Тепер нехай є $k$ різних типів дужок.

Таким чином, коли ми розглядаємо поточний символ $s[i]$ перед переобчисленням $\text{depth}$, ми маємо перебрати всі типи дужок, менші за поточний символ, і спробувати поставити цю дужку на поточну позицію (отримавши новий баланс $\text{ndepth} = \text{depth} \pm 1$), і додати до відповіді кількість способів завершити послідовність (довжина $2n-i-1$, баланс $ndepth$):

$$d[2n - i - 1][\text{ndepth}] \cdot k^{\frac{2n - i - 1 - ndepth}{2}}$$

Цю формулу можна вивести так: Спочатку ми «забуваємо», що є кілька типів дужок, і просто беремо відповідь $d[2n - i - 1][\text{ndepth}]$. Тепер розглянемо, як зміниться відповідь, якщо ми маємо $k$ типів дужок. У нас є $2n - i - 1$ невизначених позицій, з яких $\text{ndepth}$ вже наперед визначені через відкривні дужки. Але всі інші дужки ($(2n - i - 1 - \text{ndepth})/2$ пар) можуть бути будь-якого типу, тому ми множимо це число на такий степінь $k$.

Пошук $k$-ї послідовності

Нехай $n$ — кількість пар дужок у послідовності. Нам треба знайти $k$-ту правильну послідовність у лексикографічно відсортованому списку всіх правильних послідовностей для заданого $k$.

Як і в попередньому розділі, ми обчислюємо допоміжний масив $d[i][j]$ — кількість напівправильних дужкових послідовностей довжини $i$ з балансом $j$.

Спершу почнемо лише з одним типом дужок.

Ми проходитимемо по символах рядка, який хочемо згенерувати. Як і в попередній задачі, ми зберігаємо лічильник $\text{depth}$ — поточну глибину вкладеності. На кожній позиції ми маємо вирішити, чи ставити відкривну, чи закривну дужку. Щоб поставити відкривну дужку, має виконуватися $d[2n - i - 1][\text{depth}+1] \ge k$. Якщо так, то ми збільшуємо лічильник $\text{depth}$ і переходимо до наступного символу. Інакше ми зменшуємо $k$ на $d[2n - i - 1][\text{depth}+1]$, ставимо закривну дужку й рухаємося далі.

C++

string kth_balanced(int n, int k) {
    vector<vector<int>> d(2*n+1, vector<int>(n+1, 0));
    d[0][0] = 1;
    for (int i = 1; i <= 2*n; i++) {
        d[i][0] = d[i-1][1];
        for (int j = 1; j < n; j++)
            d[i][j] = d[i-1][j-1] + d[i-1][j+1];
        d[i][n] = d[i-1][n-1];
    }

    string ans;
    int depth = 0;
    for (int i = 0; i < 2*n; i++) {
        if (depth + 1 <= n && d[2*n-i-1][depth+1] >= k) {
            ans += '(';
            depth++;
        } else {
            ans += ')';
            if (depth + 1 <= n)
                k -= d[2*n-i-1][depth+1];
            depth--;
        }
    }
    return ans;
}

Python

def kth_balanced(n: int, k: int) -> str:
    # d[i][j] — кількість напівправильних послідовностей довжини i з балансом j
    d = [[0] * (n + 1) for _ in range(2 * n + 1)]
    d[0][0] = 1
    for i in range(1, 2 * n + 1):
        d[i][0] = d[i-1][1]
        for j in range(1, n):
            d[i][j] = d[i-1][j-1] + d[i-1][j+1]
        d[i][n] = d[i-1][n-1]

    ans = []
    depth = 0
    for i in range(2 * n):
        if depth + 1 <= n and d[2*n-i-1][depth+1] >= k:
            ans.append('(')
            depth += 1
        else:
            ans.append(')')
            if depth + 1 <= n:
                k -= d[2*n-i-1][depth+1]
            depth -= 1
    return ''.join(ans)

TypeScript

function kthBalanced(n: number, k: number): string {
  // d[i][j] — кількість напівправильних послідовностей довжини i з балансом j
  const d: number[][] = Array.from({ length: 2 * n + 1 }, () =>
    new Array<number>(n + 1).fill(0)
  );
  d[0][0] = 1;
  for (let i = 1; i <= 2 * n; i++) {
    d[i][0] = d[i-1][1];
    for (let j = 1; j < n; j++) d[i][j] = d[i-1][j-1] + d[i-1][j+1];
    d[i][n] = d[i-1][n-1];
  }

  let ans = '';
  let depth = 0;
  for (let i = 0; i < 2 * n; i++) {
    if (depth + 1 <= n && d[2*n-i-1][depth+1] >= k) {
      ans += '(';
      depth++;
    } else {
      ans += ')';
      if (depth + 1 <= n) k -= d[2*n-i-1][depth+1];
      depth--;
    }
  }
  return ans;
}

Go

func kthBalanced(n, k int) string {
	// d[i][j] — кількість напівправильних послідовностей довжини i з балансом j
	d := make([][]int, 2*n+1)
	for i := range d {
		d[i] = make([]int, n+1)
	}
	d[0][0] = 1
	for i := 1; i <= 2*n; i++ {
		d[i][0] = d[i-1][1]
		for j := 1; j < n; j++ {
			d[i][j] = d[i-1][j-1] + d[i-1][j+1]
		}
		d[i][n] = d[i-1][n-1]
	}

	var ans strings.Builder
	depth := 0
	for i := 0; i < 2*n; i++ {
		if depth+1 <= n && d[2*n-i-1][depth+1] >= k {
			ans.WriteByte('(')
			depth++
		} else {
			ans.WriteByte(')')
			if depth+1 <= n {
				k -= d[2*n-i-1][depth+1]
			}
			depth--
		}
	}
	return ans.String()
}

Тепер нехай є $k$ типів дужок. Розв'язок відрізнятиметься лише незначно: ми маємо помножити значення $d[2n-i-1][\text{ndepth}]$ на $k^{(2n-i-1-\text{ndepth})/2}$ і врахувати, що для наступного символу можливі різні типи дужок.

Ось реалізація з використанням двох типів дужок: круглих і квадратних:

C++

string kth_balanced2(int n, int k) {
    vector<vector<int>> d(2*n+1, vector<int>(n+1, 0));
    d[0][0] = 1;
    for (int i = 1; i <= 2*n; i++) {
        d[i][0] = d[i-1][1];
        for (int j = 1; j < n; j++)
            d[i][j] = d[i-1][j-1] + d[i-1][j+1];
        d[i][n] = d[i-1][n-1];
    }

    string ans;
    int shift, depth = 0;

    stack<char> st;
    for (int i = 0; i < 2*n; i++) {

        // '('
        shift = ((2*n-i-1-depth-1) / 2);
        if (shift >= 0 && depth + 1 <= n) {
            int cnt = d[2*n-i-1][depth+1] << shift;
            if (cnt >= k) {
                ans += '(';
                st.push('(');
                depth++;
                continue;
            }
            k -= cnt;
        }

        // ')'
        shift = ((2*n-i-1-depth+1) / 2);
        if (shift >= 0 && depth && st.top() == '(') {
            int cnt = d[2*n-i-1][depth-1] << shift;
            if (cnt >= k) {
                ans += ')';
                st.pop();
                depth--;
                continue;
            }
            k -= cnt;
        }
            
        // '['
        shift = ((2*n-i-1-depth-1) / 2);
        if (shift >= 0 && depth + 1 <= n) {
            int cnt = d[2*n-i-1][depth+1] << shift;
            if (cnt >= k) {
                ans += '[';
                st.push('[');
                depth++;
                continue;
            }
            k -= cnt;
        }

        // ']'
        ans += ']';
        st.pop();
        depth--;
    }
    return ans;
}

Python

def kth_balanced2(n: int, k: int) -> str:
    d = [[0] * (n + 1) for _ in range(2 * n + 1)]
    d[0][0] = 1
    for i in range(1, 2 * n + 1):
        d[i][0] = d[i-1][1]
        for j in range(1, n):
            d[i][j] = d[i-1][j-1] + d[i-1][j+1]
        d[i][n] = d[i-1][n-1]

    ans = []
    depth = 0
    st = []  # стек відкривних дужок
    for i in range(2 * n):
        # '('
        shift = (2*n - i - 1 - depth - 1) // 2
        if shift >= 0 and depth + 1 <= n:
            cnt = d[2*n-i-1][depth+1] << shift
            if cnt >= k:
                ans.append('(')
                st.append('(')
                depth += 1
                continue
            k -= cnt

        # ')'
        shift = (2*n - i - 1 - depth + 1) // 2
        if shift >= 0 and depth and st[-1] == '(':
            cnt = d[2*n-i-1][depth-1] << shift
            if cnt >= k:
                ans.append(')')
                st.pop()
                depth -= 1
                continue
            k -= cnt

        # '['
        shift = (2*n - i - 1 - depth - 1) // 2
        if shift >= 0 and depth + 1 <= n:
            cnt = d[2*n-i-1][depth+1] << shift
            if cnt >= k:
                ans.append('[')
                st.append('[')
                depth += 1
                continue
            k -= cnt

        # ']'
        ans.append(']')
        st.pop()
        depth -= 1
    return ''.join(ans)

TypeScript

function kthBalanced2(n: number, k: number): string {
  const d: number[][] = Array.from({ length: 2 * n + 1 }, () =>
    new Array<number>(n + 1).fill(0)
  );
  d[0][0] = 1;
  for (let i = 1; i <= 2 * n; i++) {
    d[i][0] = d[i-1][1];
    for (let j = 1; j < n; j++) d[i][j] = d[i-1][j-1] + d[i-1][j+1];
    d[i][n] = d[i-1][n-1];
  }

  let ans = '';
  let depth = 0;
  const st: string[] = []; // стек відкривних дужок
  for (let i = 0; i < 2 * n; i++) {
    // '('
    let shift = Math.floor((2*n - i - 1 - depth - 1) / 2);
    if (shift >= 0 && depth + 1 <= n) {
      const cnt = d[2*n-i-1][depth+1] << shift;
      if (cnt >= k) {
        ans += '(';
        st.push('(');
        depth++;
        continue;
      }
      k -= cnt;
    }

    // ')'
    shift = Math.floor((2*n - i - 1 - depth + 1) / 2);
    if (shift >= 0 && depth && st[st.length - 1] === '(') {
      const cnt = d[2*n-i-1][depth-1] << shift;
      if (cnt >= k) {
        ans += ')';
        st.pop();
        depth--;
        continue;
      }
      k -= cnt;
    }

    // '['
    shift = Math.floor((2*n - i - 1 - depth - 1) / 2);
    if (shift >= 0 && depth + 1 <= n) {
      const cnt = d[2*n-i-1][depth+1] << shift;
      if (cnt >= k) {
        ans += '[';
        st.push('[');
        depth++;
        continue;
      }
      k -= cnt;
    }

    // ']'
    ans += ']';
    st.pop();
    depth--;
  }
  return ans;
}

Go

func kthBalanced2(n, k int) string {
	d := make([][]int, 2*n+1)
	for i := range d {
		d[i] = make([]int, n+1)
	}
	d[0][0] = 1
	for i := 1; i <= 2*n; i++ {
		d[i][0] = d[i-1][1]
		for j := 1; j < n; j++ {
			d[i][j] = d[i-1][j-1] + d[i-1][j+1]
		}
		d[i][n] = d[i-1][n-1]
	}

	var ans strings.Builder
	depth := 0
	st := []byte{} // стек відкривних дужок
	for i := 0; i < 2*n; i++ {
		// '('
		shift := (2*n - i - 1 - depth - 1) / 2
		if shift >= 0 && depth+1 <= n {
			cnt := d[2*n-i-1][depth+1] << shift
			if cnt >= k {
				ans.WriteByte('(')
				st = append(st, '(')
				depth++
				continue
			}
			k -= cnt
		}

		// ')'
		shift = (2*n - i - 1 - depth + 1) / 2
		if shift >= 0 && depth > 0 && st[len(st)-1] == '(' {
			cnt := d[2*n-i-1][depth-1] << shift
			if cnt >= k {
				ans.WriteByte(')')
				st = st[:len(st)-1]
				depth--
				continue
			}
			k -= cnt
		}

		// '['
		shift = (2*n - i - 1 - depth - 1) / 2
		if shift >= 0 && depth+1 <= n {
			cnt := d[2*n-i-1][depth+1] << shift
			if cnt >= k {
				ans.WriteByte('[')
				st = append(st, '[')
				depth++
				continue
			}
			k -= cnt
		}

		// ']'
		ans.WriteByte(']')
		st = st[:len(st)-1]
		depth--
	}
	return ans.String()
}

Відеоматеріали