__Whisper's blog

How to generate a regular bracket
By __Whisper, history, 4 months 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
  • 0
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +4 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
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
»
4 months ago, # |
  Vote: I like it 0 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
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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/cLbvx9

Thanks so much, guys!

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply