Блог пользователя SaSa

Автор SaSa, история, 8 лет назад, По-английски

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)

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      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).

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

        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
        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Thank you for great explanation!

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

          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")

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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).

»
8 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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