Htykuut

We have the following balanced brackets permutations of length $4cdot2$ 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 .

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;

}