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