### __Whisper's blog

By __Whisper, history, 3 weeks ago,

Hi guys, I got stuck in a problem and i want to make test generation but idk how to generate a regular bracket does anyone know how to do that?

• 0

 » 3 weeks ago, # |   +4 Maintain stack. Randomly choose an operation to add a forward bracket or reverse bracket. When you add a forward bracket, add it to the stack. Add a reverse bracket only if there is at least one forward bracket in the stack. And in that case remove one forward bracket from the stack. In order to maintain a size limit, note that a bracket sequnce of size 2n has exactly n forward brackets. So use it to restrict the length of the sequence.
•  » » 3 weeks ago, # ^ |   +6 I found my mistake btw thank you so much for the solution :D
 » 3 weeks ago, # |   0 You can represent a regular bracket sequence as an Eulerian traversal of a tree — an opening bracket ( is a descent into a new vertex, a closing bracket ) is an ascent to an ancestor vertex.Random trees can be generated using a Prüfer code. Then it becomes possible to generate a regular bracket sequence with equal probability.
•  » » 3 weeks ago, # ^ |   0 What a nice idea! thank you :DD
 » 3 weeks ago, # |   0 I tried to write it and I think I successfully implemented for it. This is the source code for anyone who need it: https://ideone.com/cLbvx9Thanks so much, guys!
•  » » 3 weeks ago, # ^ |   0 This generates some regular bracket sequence, and it may be enough. But also may be too regular for some uses. For example, the generated sequence is symmetric: $i$-th bracket from the left and $i$-th bracket from the right are always different.