Secuencias de paréntesis balanceadas

Una secuencia de paréntesis balanceada (balanced bracket sequence) es un string que consiste solo de paréntesis, tal que esta secuencia, al insertarle ciertos números y operaciones matemáticas, da una expresión matemática válida. Formalmente se puede definir una secuencia de paréntesis balanceada con:

$e$ (el string vacío) es una secuencia de paréntesis balanceada.
si $s$ es una secuencia de paréntesis balanceada, entonces también lo es $(s)$ .
si $s$ y $t$ son secuencias de paréntesis balanceadas, entonces también lo es $s t$ .

Por ejemplo $(())()$ es una secuencia de paréntesis balanceada, pero $())($ no lo es.

Por supuesto también se pueden definir otras secuencias de paréntesis con varios tipos de paréntesis de manera similar.

En este artículo discutimos algunos problemas clásicos que involucran secuencias de paréntesis balanceadas (por simplicidad solo las llamaremos secuencias): validación, número de secuencias, hallar la siguiente secuencia en orden lexicográfico, generar todas las secuencias de un cierto tamaño, hallar el índice de una secuencia, y generar la $k$ -ésima secuencia. También discutiremos dos variantes de los problemas, la versión más simple cuando solo se permite un tipo de paréntesis, y el caso más difícil cuando hay varios tipos.

Validación de balance

Queremos comprobar si un string dado está balanceado o no.

Primero supongamos que hay solo un tipo de paréntesis. Para este caso existe un algoritmo muy sencillo. Sea $\text{depth}$ el número actual de paréntesis abiertos. Inicialmente $\text{depth} = 0$ . Iteramos sobre todos los caracteres del string; si el carácter de paréntesis actual es un paréntesis de apertura, entonces incrementamos $\text{depth}$ , en caso contrario lo decrementamos. Si en cualquier momento la variable $\text{depth}$ se vuelve negativa, o al final es distinta de $0$ , entonces el string no es una secuencia balanceada. En caso contrario lo es.

Si hay varios tipos de paréntesis involucrados, entonces el algoritmo necesita cambiarse. En lugar de un contador $\text{depth}$ creamos una pila, en la que guardaremos todos los paréntesis de apertura que encontremos. Si el carácter de paréntesis actual es de apertura, lo ponemos en la pila. Si es de cierre, entonces comprobamos si la pila no está vacía, y si el elemento tope de la pila es del mismo tipo que el paréntesis de cierre actual. Si se cumplen ambas condiciones, entonces quitamos el paréntesis de apertura de la pila. Si en cualquier momento una de las condiciones no se cumple, o al final la pila no está vacía, entonces el string no está balanceado. En caso contrario lo está.

Número de secuencias balanceadas

Fórmula

El número de secuencias de paréntesis balanceadas con solo un tipo de paréntesis se puede calcular usando los números de Catalan. El número de secuencias de paréntesis balanceadas de longitud $2n$ ( $n$ pares de paréntesis) es:

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

Si permitimos $k$ tipos de paréntesis, entonces cada par puede ser de cualquiera de los $k$ tipos (independientemente de los demás), así que el número de secuencias de paréntesis balanceadas es:

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

Programación dinámica

Por otro lado estos números se pueden computar usando programación dinámica. Sea $d[n]$ el número de secuencias de paréntesis regulares con $n$ pares de paréntesis. Nótese que en la primera posición siempre hay un paréntesis de apertura. Y en algún lugar más adelante está el paréntesis de cierre correspondiente del par. Está claro que dentro de este par hay una secuencia de paréntesis balanceada, y de manera similar después de este par hay una secuencia de paréntesis balanceada. Así que para computar $d[n]$ , veremos cuántas secuencias balanceadas de $i$ pares de paréntesis hay dentro de este primer par de paréntesis, y cuántas secuencias balanceadas con $n-1-i$ pares hay después de este par. En consecuencia la fórmula tiene la forma:

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

El valor inicial de esta recurrencia es $d[0] = 1$ .

Hallar la siguiente secuencia balanceada en orden lexicográfico

Aquí solo consideramos el caso con un tipo de paréntesis válido.

Dada una secuencia balanceada, tenemos que hallar la siguiente secuencia balanceada (en orden lexicográfico).

Debería ser obvio que tenemos que hallar el paréntesis de apertura más a la derecha, que podemos reemplazar por un paréntesis de cierre sin violar la condición de que hay más paréntesis de cierre que de apertura hasta esta posición. Después de reemplazar esta posición, podemos llenar la parte restante del string con la lexicográficamente mínima: es decir, primero con tantos paréntesis de apertura como sea posible, y luego llenar las posiciones restantes con paréntesis de cierre. En otras palabras, intentamos dejar un prefijo tan largo como sea posible sin cambios, y el sufijo se reemplaza por el lexicográficamente mínimo.

Para hallar esta posición, podemos iterar sobre los caracteres de derecha a izquierda, y mantener el balance $\text{depth}$ de paréntesis de apertura y de cierre. Cuando encontramos un paréntesis de apertura, decrementaremos $\text{depth}$ , y cuando encontramos un paréntesis de cierre, lo aumentamos. Si en algún punto encontramos un paréntesis de apertura, y el balance después de procesar este símbolo es positivo, entonces hemos hallado la posición más a la derecha que podemos cambiar. Cambiamos el símbolo, computamos el número de paréntesis de apertura y de cierre que tenemos que añadir al lado derecho, y los disponemos de la manera lexicográficamente mínima.

Si no hallamos una posición adecuada, entonces esta secuencia ya es la máxima posible, y no hay respuesta.


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;
}

Esta función computa en tiempo $O(n)$ la siguiente secuencia de paréntesis balanceada, y devuelve false si no hay una siguiente.

Hallar todas las secuencias balanceadas

A veces se requiere hallar y emitir todas las secuencias de paréntesis balanceadas de una longitud específica $n$ .

Para generarlas, podemos empezar con la secuencia lexicográficamente más pequeña $((\dots(())\dots))$ , y luego continuar hallando las siguientes secuencias en orden lexicográfico con el algoritmo descrito en la sección anterior.

Sin embargo, si la longitud de la secuencia no es muy grande (p. ej. $n$ menor que $12$ ), entonces también podemos generar todas las permutaciones convenientemente con la función de la STL de C++ next_permutation, y comprobar cada una por balanceo.

También se pueden generar usando las ideas que usamos para contar todas las secuencias con programación dinámica. Discutiremos las ideas en las siguientes dos secciones.

Índice de una secuencia

Dada una secuencia de paréntesis balanceada con $n$ pares de paréntesis. Tenemos que hallar su índice en la lista ordenada lexicográficamente de todas las secuencias balanceadas con $n$ pares de paréntesis.

Definamos un arreglo auxiliar $d[i][j]$ , donde $i$ es la longitud de la secuencia de paréntesis (semibalanceada: cada paréntesis de cierre tiene un paréntesis de apertura correspondiente, pero no todo paréntesis de apertura tiene necesariamente un paréntesis de cierre correspondiente), y $j$ es el balance actual (diferencia entre paréntesis de apertura y de cierre). $d[i][j]$ es el número de tales secuencias que encajan en los parámetros. Calcularemos estos números con solo un tipo de paréntesis.

Para el valor inicial $i = 0$ la respuesta es obvia: $d[0][0] = 1$ , y $d[0][j] = 0$ para $j > 0$ . Ahora sea $i > 0$ , y miremos el último carácter de la secuencia. Si el último carácter fue un paréntesis de apertura $($ , entonces el estado anterior era $(i-1, j-1)$ ; si fue un paréntesis de cierre $)$ , entonces el estado anterior era $(i-1, j+1)$ . Así obtenemos la fórmula de recurrencia:

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

$d[i][j] = 0$ vale obviamente para $j$ negativo. Así podemos computar este arreglo en $O(n^2)$ .

Ahora generemos el índice de una secuencia dada.

Primero sea que hay solo un tipo de paréntesis. Usaremos el contador $\text{depth}$ que nos dice cuán anidados estamos actualmente, e iteraremos sobre los caracteres de la secuencia. Si el carácter actual $s[i]$ es igual a $($ , entonces incrementamos $\text{depth}$ . Si el carácter actual $s[i]$ es igual a $)$ , entonces debemos sumar $d[2n-i-1][\text{depth}+1]$ a la respuesta, teniendo en cuenta todos los finales posibles que empiezan con un $($ (que son secuencias lexicográficamente menores), y luego decrementar $\text{depth}$ .

Ahora sea que hay $k$ tipos distintos de paréntesis.

Así, cuando miramos el carácter actual $s[i]$ antes de recomputar $\text{depth}$ , tenemos que recorrer todos los tipos de paréntesis que son menores que el carácter actual, e intentar colocar este paréntesis en la posición actual (obteniendo un nuevo balance $\text{ndepth} = \text{depth} \pm 1$ ), y sumar el número de formas de terminar la secuencia (longitud $2n-i-1$ , balance $ndepth$ ) a la respuesta:

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

Esta fórmula se puede derivar como sigue: Primero “olvidamos” que hay varios tipos de paréntesis, y simplemente tomamos la respuesta $d[2n - i - 1][\text{ndepth}]$ . Ahora consideramos cómo cambiará la respuesta si tenemos $k$ tipos de paréntesis. Tenemos $2n - i - 1$ posiciones indefinidas, de las cuales $\text{ndepth}$ ya están predeterminadas por los paréntesis de apertura. Pero todos los demás paréntesis ( $(2n - i - 1 - \text{ndepth})/2$ pares) pueden ser de cualquier tipo, por lo tanto multiplicamos el número por tal potencia de $k$ .

Hallar la $k$ -ésima secuencia {data-toc-label=“Hallar la k-ésima secuencia”}

Sea $n$ el número de pares de paréntesis en la secuencia. Tenemos que hallar la $k$ -ésima secuencia balanceada en la lista ordenada lexicográficamente de todas las secuencias balanceadas para un $k$ dado.

Como en la sección anterior computamos el arreglo auxiliar $d[i][j]$ , el número de secuencias de paréntesis semibalanceadas de longitud $i$ con balance $j$ .

Primero, empezamos con solo un tipo de paréntesis.

Iteraremos sobre los caracteres del string que queremos generar. Como en el problema anterior guardamos un contador $\text{depth}$ , la profundidad de anidamiento actual. En cada posición, tenemos que decidir si colocar un paréntesis de apertura o de cierre. Para colocar un paréntesis de apertura, debe cumplirse $d[2n - i - 1][\text{depth}+1] \ge k$ . Si es así, incrementamos el contador $\text{depth}$ , y pasamos al siguiente carácter. En caso contrario, decrementamos $k$ en $d[2n - i - 1][\text{depth}+1]$ , colocamos un paréntesis de cierre, y seguimos.


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;
}

Ahora sea que hay $k$ tipos de paréntesis. La solución solo diferirá ligeramente en que tenemos que multiplicar el valor $d[2n-i-1][\text{ndepth}]$ por $k^{(2n-i-1-\text{ndepth})/2}$ y tener en cuenta que puede haber distintos tipos de paréntesis para el siguiente carácter.

Aquí hay una implementación usando dos tipos de paréntesis: redondos y cuadrados:


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;
}