$N^\text{th}$ (en orden lexicográfico) término de equilibrado soportes de cadena

Question

Tenemos los siguientes equilibrada soportes de permutaciones de longitud $4\cdot2$ en orden lexicográfico:

1.  (((())))
2.  ((()()))
3.  ((())())
4.  ((()))()
5.  (()(()))
6.  (()()())
7.  (()())()
8.  (())(())
9.  (())()()
10. ()((()))
11. ()(()())
12. ()(())()
13. ()()(())
14. ()()()()

Y quiero imprimir, por ejemplo, 7 de término que es: $(()())()$ sin calcular 6 anterior. Alguna idea de cómo hacerlo en $\mathcal{O}(n)$ tiempo? ($n$ = número de pares de corchetes)

Sé que el número de todos estos términos es $C(n)$ ($n^\text{th}$ catalán número) pero no, no me ayuda con la búsqueda de algoritmo eficiente.

Todas las sugerencias serán de gran ayuda.

Edit: Proporcionar a ti mismo con más ejemplos con este generador - https://ideone.com/5s4S3 .

Answer 1

Aquí es una implementación del algoritmo U en Java. Sin embargo, yo simplemente he restado $N$ $C(n)$.

public static String genNthBalParStr(int numPairs, int N) {
  int q, p, c, c1, m;
  String str = "";
  q = numPairs;
  m = p = c = 1;
  while  (p < numPairs)  {
    p = p + 1;
    c = ((4 * p - 2) * c)/(p + 1);
  }
  N = c - (N - 1);
  while  (true)  {
    if  (q != 0)  {
      c1 = ((q + 1) * (q - p) * c)/((q + p) * (q - p + 1));
      if  (N > c1)  {
        p = p - 1;
        c = c - c1; 
        N = N - c1;
        str += "(";
        m = m + 1;
      }
      else {
        q = q - 1;
        c = c1;
        str += ")";
        m = m + 1;
      }
    }
    else break;
  }
  return str;
}