SaSa's blog

A random problem!
By SaSa, history, 8 years ago, In English

Hi :)
Given n can you find a uniformly random correct bracket sequence with 2 * n characters ?
(uniformly random means all possible answer for the problem have same probability for the outcome of the algorithm)

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

»
8 years ago, # |
  Vote: I like it +46 Vote: I do not like it

for these kind of problems you could pick a random number out of all of the ways to arrange it like for this you pick a random number from 1 to Catalan(n) let that number be k
you find the kth bracket sequence in lexigraphical order
this would be O(n ^ 3) i guess tell me if that isn't enough

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Yeah i knew that approach.
    It was not actually something that i needed for a problem but i was wondering if it has a linear solution.

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

A hint: do you know how to prove the recurrent formula for Catalan numbers in application to counting correct bracket sequences? It automatically yields the linear quadratic algorithm for the desired problem.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think this should work. It's O(n).

UPD: Now that I looked, it's the same idea with what Zlobober said.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

    Nope. Your distribution is not uniform.

    The bracket sequence ((())) will appear with probability 1/6, though it should appear with probability 1/5.

    But it can easily be adjusted to a correct one by fixing a distribution you use to choose left_len.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      Oops. I didn't realize that. Thanks!

      To fix the distribution I need to find the number of ways it can be done for each case, right? Then, it will become O(n2).

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it +18 Vote: I do not like it

        Exactly. A nice thing to think about is the expected running time of such algorithm. Is it actually smaller than O(n2)?

        Here is an idea of improvement towards O(n) running time
        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you for great explanation!

          Btw, this is the updated version, do you think it is correct now?

          → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          Thanks[user:Zlobober]! But how to actually deal with the n*sqrt(n) part in O(1)?
          (its maybe because i didn't get the part "integrating and inversing the density function above")

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            Using that approximation you need to find a new function f that gives the partial sum. After that you need to find the inverse of it so that you can find the x such that f(x) = randomly selected number.

            → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

It can be done with simple dp. States are [how many characters left][how many unclosed parantheses left]. You will randomly go another state a randomly with prob f(a)/(sum for all f(a)`s).

→ Reply
»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Post in Russian

Python source code from this post (see function tryAndFix)

→ Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

A linear algorithm not using big numbers for reasonable n is here (The Art of Computer Programming, fascicle 4a) on page 13.

→ Reply