# $N^\text{th}$ (in lexicographical order) term of balanced brackets string

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 .

• 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. Commented Aug 30, 2012 at 2:40
• This problem is discussed at some length in volume 4A of Knuth The Art of Computer Programming, in the section "enumerating all trees".
– MJD
Commented Aug 30, 2012 at 3:02
• Thanks. It's called algorithm U and here it is: 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. Commented Aug 31, 2012 at 0:09
• Related question. Commented May 29, 2013 at 16:10

## 1 Answer

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