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 .