__Whisper's blog

How to generate a regular bracket
By __Whisper, history, 4 hours ago, In English

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?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    94 minutes ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I found my mistake btw thank you so much for the solution :D

    → Reply
»
36 minutes ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply