Opened 6 years ago
Closed 6 years ago
#17241 closed enhancement (fixed)
Uniform random generation of BinaryTree of a given size
Reported by:  g.chatel  Owned by:  gchatel 

Priority:  major  Milestone:  sage6.4 
Component:  combinatorics  Keywords:  random, combinatorics, binary trees 
Cc:  VivianePons, tscrim, darij, sagecombinat, nthiery, chapoton  Merged in:  
Authors:  Grégory Châtel  Reviewers:  Darij Grinberg, Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  cad5faa (Commits, GitHub, GitLab)  Commit:  cad5faac6eaff88b9c5be1121a3425eebd09940f 
Dependencies:  Stopgaps: 
Description
I am overwritting the default random_element method of the BinaryTree_size class to implement an efficient way to compute a random binary tree.
As explained in the documentation, we use the fact that binary trees are in bijection with Dyck words.
Change History (8)
comment:1 Changed 6 years ago by
 Branch set to public/combinat/binarytreerandom17241
 Commit set to d6a7243831e68f430fd5939a652960d448f1f2ff
comment:2 Changed 6 years ago by
 Status changed from new to needs_review
comment:3 Changed 6 years ago by
 Commit changed from d6a7243831e68f430fd5939a652960d448f1f2ff to ff62d2658987f7f23a425e7ba09411f83ffb7a5a
Branch pushed to git repo; I updated commit sha1. New commits:
ff62d26  minor modifications

comment:4 Changed 6 years ago by
Made a little change (once again, please use specific classes rather than generic factories/dispatchers when possible), otherwise looks good to me. If you are fine with this, please set it to positive_review.
comment:5 Changed 6 years ago by
NO ! no positive review, the doc is badly formatted !
comment:6 Changed 6 years ago by
 Commit changed from ff62d2658987f7f23a425e7ba09411f83ffb7a5a to cad5faac6eaff88b9c5be1121a3425eebd09940f
Branch pushed to git repo; I updated commit sha1. New commits:
cad5faa  Fixing a format problem with the documentation.

comment:7 Changed 6 years ago by
 Reviewers set to Darij Grinberg, Frédéric Chapoton
 Status changed from needs_review to positive_review
Looks good to me. Bienvenue à bord.
comment:8 Changed 6 years ago by
 Branch changed from public/combinat/binarytreerandom17241 to cad5faac6eaff88b9c5be1121a3425eebd09940f
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Implementation of the random_element method of BinaryTrees_size.