9
$\begingroup$

We have the following balanced brackets permutations of length $4\cdot2$ in lexicographical order:

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

And I want to print for example 7th term which is: $(()())()$ without calculating 6 previous terms. Any ideas how to do it in $\mathcal{O}(n)$ time? ($n$ = number of pairs of brackets)

I know that number of all these terms is $C(n)$ ($n^\text{th}$ Catalan number) but it didn't help me with finding efficient algorithm.

Any hints will be helpful.

Edit: Provide yourself with more examples with this generator - https://ideone.com/5s4S3 .

  • 0
    [Related](http://math.stackexchange.com/questions/189391/given-algorithm-which-prints-n-th-string-of-nested-parentheses-find-a-reverse) question.2013-05-29

1 Answers 1

0

Here is an implementation of Algorithm-U in Java. However, I have simply subtracted $N$ from $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; }