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
    The Catalan numbers count a lot of things, e.g., number of ways to triangulate a polygon. Perhaps one of these has a natural and easily computable ordering which you could use to induce an ordering on the balanced strings of brackets.2012-08-30
  • 5
    This problem is discussed at some length in volume 4A of Knuth *The Art of Computer Programming*, in the section "enumerating all trees".2012-08-30
  • 0
    Thanks. It's called algorithm U and here it is: http://imageshack.us/photo/my-images/832/knuth.png . But can You explain it? Or at least reverse it as it works for '('>')' ? I could ofc subtract n from C(n), but as You know Catalan numbers are pretty big.2012-08-31
  • 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;
}