Opened 3 years ago

Closed 2 years ago

#19446 closed enhancement (fixed)

Hook statistics in binary Trees

Reported by: boussica Owned by: boussica
Priority: minor Milestone: sage-7.2
Component: combinatorics Keywords: binary trees, hook
Cc: Merged in:
Authors: Adrien Boussicault, Bérénice Delcroix-Oger, Patxi Laborde-Zubieta Reviewers: Kevin Dilks, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: d114661 (Commits) Commit: d114661139f46fa8e97f79a8c6176c535879e523
Dependencies: Stopgaps:

Description

We add a hook statistics on binary trees.

The hook of a vertex v is the union of {v}, its leftmost and· rightmost branches.

There is a unique way to partition the vertices in hooks. The number of hooks in such a partition is the hook number of the tree.

We can obtain this partition recursively by extracting the root's hook· and iterating the processus on each tree of the remaining forest.

Change History (26)

comment:1 Changed 3 years ago by boussica

  • Owner changed from (none) to boussica

comment:2 Changed 3 years ago by boussica

  • Authors changed from Adrien Boussicault to Adrien Boussicault, Bérénice Delcroix-Oger, Patxi Laborde-Zubieta

comment:3 Changed 3 years ago by boussica

  • Branch set to u/boussica/hook_statistics_in_binary_trees

comment:4 Changed 3 years ago by chapoton

  • Commit set to 6b6aa4748b85f4e05fbf207436726e498b5eeb72

A few remarks:

  • it seems better to use 'left' and 'right', rather than 0 and 1 for the side selection
  • syntax of INPUT and OUTPUT is wrong; must be
    INPUT:
    
    here
    

with just one colon, and a blank line just below the INPUT line


New commits:

6b6aa47Add implementation of Hook statistic

comment:5 Changed 3 years ago by git

  • Commit changed from 6b6aa4748b85f4e05fbf207436726e498b5eeb72 to 4ed1b4d305503b52840badb59fc6cc25ffd0dbaa

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

4ed1b4dUpdate documentation of hook_number() and comb()

comment:6 Changed 3 years ago by chapoton

rather use """ for the doc start and end (not ''')

maybe call the function comb_list (more explicit)

Last edited 3 years ago by chapoton (previous) (diff)

comment:7 Changed 3 years ago by git

  • Commit changed from 4ed1b4d305503b52840badb59fc6cc25ffd0dbaa to 13522dd011463d9847458ff908a3504a234faf5d

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

13522ddModify ''' in the documentation

comment:8 Changed 3 years ago by chapoton

If you want a review, you should set the status to "needs_review"

comment:9 Changed 3 years ago by oger

  • Branch changed from u/boussica/hook_statistics_in_binary_trees to u/oger/hook_statistics_in_binary_trees

comment:10 Changed 3 years ago by chapoton

  • Commit changed from 13522dd011463d9847458ff908a3504a234faf5d to 238b35298dae93ef5e2fb7365c65b9c9b25662a0

Salut, Adrien et Bérénice.

Quand on travaille à plusieurs sur les mêmes tickets, on peut utiliser comme nom de branche un truc du style public/hook_statistics_in_binary_trees pour ne pas avoir a changer le nom de la branche à chaque fois.


New commits:

238b352Add the twisting statistic

comment:11 Changed 3 years ago by chapoton

So you do not want this to be reviewed ??

Anyway, you can replace

if len(L)>0:

by

if len(L):

and also

tn[0]=tn[0]+1

by

tn[0] += 1

comment:12 Changed 2 years ago by chapoton

  • Milestone changed from sage-6.10 to sage-7.0

Hello, are you still not interested by a review ? Have you abandoned this ticket ?

comment:13 Changed 2 years ago by mantepse

I did not get the definition of hook upon first reading. Thus, here are some suggestions for the docstrings. A reference where one can find a definition would be good, too.

I'd like to submit this statistic to http://FindStat.org - would this be OK?

    Return the comb of a tree.

    There are two combs in a binary tree: a left comb and a right comb.
    Consider the vertices of the leftmost (resp. rightmost) branch of 
    the root, excluding the root itself.  The left (resp. right) comb 
    is the list of right (resp. left) subtree of each of these vertices.

    INPUT:

    - ``side`` -- (default: 'left') set to 'left' to obtain the left 
      comb, and to 'right' to obtain the right comb.

    OUTPUT:

    A list of binary trees.
    Return the number of hooks.

    The hook of a vertex v is the subtree that consists of {v}, the
    leftmost branch and the rightmost branch of v.

    The set of hooks partitions the binary tree.  The number of hooks
    in such a partition is the hook number of the tree.

    We can obtain this partition recursively by extracting the root's
    hook and repeating the process on each tree of the remaining
    forest.

comment:14 Changed 2 years ago by chapoton

  • Status changed from new to needs_review

ok, let me put that in needs_review, after a mail exchange with Adrien

comment:15 Changed 2 years ago by kdilks

Everything looks good to me (it seems a few people have already looked it over and made comments). The one thing I'd like to see (and might add myself) is ASCII art representations of the non-trivial examples, since they really help illustrate the definitions.

comment:16 Changed 2 years ago by kdilks

  • Branch changed from u/oger/hook_statistics_in_binary_trees to u/kdilks/hook_statistics_in_binary_trees

comment:17 Changed 2 years ago by kdilks

  • Commit changed from 238b35298dae93ef5e2fb7365c65b9c9b25662a0 to b28292079ba9bb92978b24498f6fe6b0a8909928
  • Reviewers set to Kevin Dilks

New commits:

6c3e0e8Merge branch 'u/oger/hook_statistics_in_binary_trees' of http://trac.sagemath.org/sage into hookstat19446
b282920Added ascii art to documentation

comment:18 Changed 2 years ago by kdilks

Somebody can set a positive review on my behalf once they've verified that everything is ok with my additions to the documentation.

comment:19 Changed 2 years ago by mantepse

Does anybody find my docstring proposals (from comment 13) helpful? If so, I'd add them.

comment:20 Changed 2 years ago by chapoton

  • Branch changed from u/kdilks/hook_statistics_in_binary_trees to public/19446
  • Commit changed from b28292079ba9bb92978b24498f6fe6b0a8909928 to cb93656f7f8b50a380a55b59b743dbfbaa6df99e

here is a new git branch with some little doc and code cleanups.

I am still not happy with the documentation, in particular

  • what is a "branch" ? it should be defined somewhere..

New commits:

ae98a59Merge branch 'u/kdilks/hook_statistics_in_binary_trees' of ssh://trac.sagemath.org:22/sage into tree_hook
cb93656trac #19446 a few doc and code cleanup changes

comment:21 Changed 2 years ago by git

  • Commit changed from cb93656f7f8b50a380a55b59b743dbfbaa6df99e to 8f0c777e13f768ae343816058e5c9a9a7d69e743

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

8f0c777I add some details one the documentation (especially the definition of a branch)

comment:22 Changed 2 years ago by chapoton

good, but the new text is not correctly aligned

comment:23 Changed 2 years ago by git

  • Commit changed from 8f0c777e13f768ae343816058e5c9a9a7d69e743 to c257d783d1ad63d4f513fc02ee2a614736afb407

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

c257d78Correction of spaces

comment:24 Changed 2 years ago by git

  • Commit changed from c257d783d1ad63d4f513fc02ee2a614736afb407 to d114661139f46fa8e97f79a8c6176c535879e523

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

58c5494Merge branch 'public/19446' of git://trac.sagemath.org/sage into 19446
d114661trac #19446 two details in doc of comb method of binary trees

comment:25 Changed 2 years ago by chapoton

  • Milestone changed from sage-7.0 to sage-7.2
  • Reviewers changed from Kevin Dilks to Kevin Dilks, Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, looks good to me.


New commits:

58c5494Merge branch 'public/19446' of git://trac.sagemath.org/sage into 19446
d114661trac #19446 two details in doc of comb method of binary trees

comment:26 Changed 2 years ago by vbraun

  • Branch changed from public/19446 to d114661139f46fa8e97f79a8c6176c535879e523
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.