### SaSa's blog

By SaSa, history, 6 years ago,

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

 » 6 years ago, # |   +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
•  » » 6 years ago, # ^ | ← 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.
 » 6 years ago, # | ← 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.
 » 6 years ago, # | ← 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.
•  » » 6 years ago, # ^ | ← 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.
•  » » » 6 years ago, # ^ | ← 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).
•  » » » » 6 years ago, # ^ | ← 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 timeLet's try to think how to get rid of quadratic running time. Actually we don't need a DP to calculate Catalan numbers since we know a closed formula But we still need to choose a value from the distribution defined by weights Cn - 1C0, Cn - 2C1, ..., C1Cn - 2, Cn - 1For large $n$ we may use the following approximation for Catalan numbers (that follows from Striling formula): So, for the most part of the distribution we may use the formula above with high precision. It allows us to generate a random number from this distribution in $O(1)$ by analytically integrating and inversing the density function above.This will not lead to a large error only for large numbers of n, so we will use the naive quadratic approach for the innermost recursive calls.
•  » » » » » 6 years ago, # ^ |   0 Thank you for great explanation!Btw, this is the updated version, do you think it is correct now?
•  » » » » » 6 years ago, # ^ | ← 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")
•  » » » » » » 6 years ago, # ^ | ← 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.
 » 6 years ago, # | ← 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).
 » 6 years ago, # |   +16 Post in RussianPython source code from this post (see function tryAndFix)
 » 6 years ago, # |   +8 A linear algorithm not using big numbers for reasonable n is here (The Art of Computer Programming, fascicle 4a) on page 13.