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)
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)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
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
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.
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
linearquadratic algorithm for the desired problem.I think this should work. It's O(n).
UPD: Now that I looked, it's the same idea with what Zlobober said.
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.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).
Exactly. A nice thing to think about is the expected running time of such algorithm. Is it actually smaller than O(n2)?
Let'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
For 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.
Thank you for great explanation!
Btw, this is the updated version, do you think it is correct now?
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")
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.
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).
Post in Russian
Python source code from this post (see function tryAndFix)
A linear algorithm not using big numbers for reasonable n is here (The Art of Computer Programming, fascicle 4a) on page 13.