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 .