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: sage-6.4
Component: combinatorics Keywords: random, combinatorics, binary trees
Cc: VivianePons, tscrim, darij, sage-combinat, 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:

Status badges

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 g.chatel

  • Branch set to public/combinat/binary-tree-random-17241
  • Commit set to d6a7243831e68f430fd5939a652960d448f1f2ff

New commits:

​d6a7243Implementation of the random_element method of BinaryTrees_size.

comment:2 Changed 6 years ago by g.chatel

  • Status changed from new to needs_review

comment:3 Changed 6 years ago by git

  • Commit changed from d6a7243831e68f430fd5939a652960d448f1f2ff to ff62d2658987f7f23a425e7ba09411f83ffb7a5a

Branch pushed to git repo; I updated commit sha1. New commits:

​ff62d26minor modifications

comment:4 Changed 6 years ago by darij

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 chapoton

NO ! no positive review, the doc is badly formatted !

comment:6 Changed 6 years ago by git

  • Commit changed from ff62d2658987f7f23a425e7ba09411f83ffb7a5a to cad5faac6eaff88b9c5be1121a3425eebd09940f

Branch pushed to git repo; I updated commit sha1. New commits:

​cad5faaFixing a format problem with the documentation.

comment:7 Changed 6 years ago by chapoton

  • 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 vbraun

  • Branch changed from public/combinat/binary-tree-random-17241 to cad5faac6eaff88b9c5be1121a3425eebd09940f
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.