Timeline for Generating uniformly distributed trees
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 7, 2019 at 17:39 | comment | added | Brendan McKay | 10^8000 is not a problem. Use pairs $(d,i)$ where $d$ is double-precision and $i$ is integer. This represents $d\times 10^i$. I do this often. The only question is whether enough precision is maintained. | |
| Jun 7, 2019 at 9:25 | comment | added | Timothy Budd | Assuming your trees are ordered (labeled or not), there is a simple (and very efficient) algorithm to sample them uniformly. See M. D. Atkinson, "Uniform Generation of Rooted Ordered Trees with Prescribed Degrees", The Computer Journal 36 (1993), 593–594. | |
| Jun 7, 2019 at 8:43 | history | edited | Stefan Kahrs | CC BY-SA 4.0 |
added 16 characters in body
|
| Jun 7, 2019 at 8:40 | comment | added | Stefan Kahrs | @EmilJeřábek I did come up with a formula for the size, but the problem is that the formula is a sum, indexed by varying values for $n_1$, because for every two unary symbols I add to the degree profile a binary and a nullary symbol is taken out. Each summand of this is then a multiple of the Catalan number for the number of binary symbols. I call this "a problem", because the sums are not any easier to compute than the recurrences, and there is very little room for simplification when computing the quotients for the probabilities. | |
| Jun 7, 2019 at 8:24 | comment | added | Stefan Kahrs | The trees are only labelled with the function symbols. Two trees are the same if they have the same shape and the same labelling with function symbols. "calculate to floating point precision" is not applicable here, as we ran out of exponents, e.g. the one number I mentioned I computed was roughly 10^8000. | |
| Jun 7, 2019 at 8:06 | comment | added | Emil Jeřábek | In particular, the number of such trees of size $n$ with $n_0,n_1,n_2$ nodes of respective arities $0,1,2$ (which can only happen if $n=n_0+n_1+n_2=1+n_1+2n_2$) is $\frac1n\binom n{n_0,n_1,n_2}z^{n_0}u^{n_1}b^{n_2}$, since each string with the right number of occurrences of nullary, unary, and binary symbols has exactly one cyclic permutation that is a correct Polish notation for a tree. | |
| Jun 7, 2019 at 7:59 | comment | added | Emil Jeřábek | These are generalizations of Catalan numbers, and there should be explicitish formulas in terms of multinomial coefficients. | |
| Jun 7, 2019 at 4:15 | history | edited | user64494 | CC BY-SA 4.0 |
A typo in the title is corrected.
|
| Jun 6, 2019 at 18:31 | comment | added | F. C. | Search for "Boltzmann sampling" for some approximate algorithms. | |
| Jun 6, 2019 at 18:09 | comment | added | Brendan McKay | I didn't understand the problem in detail, but for practical use it might be sufficient to calculate the number to floating-point precision. | |
| Jun 6, 2019 at 16:50 | comment | added | Robert Israel | Are these labelled or unlabelled trees? The question is, what trees count as "the same" or "different"? | |
| Jun 6, 2019 at 16:05 | review | First posts | |||
| Jun 6, 2019 at 16:13 | |||||
| Jun 6, 2019 at 16:04 | history | asked | Stefan Kahrs | CC BY-SA 4.0 |