#14498: trees and binary trees
----------------------------------------------+----------------------------
Reporter: elixyre | Owner: sage-
Type: enhancement | combinat
Priority: major | Status: needs_review
Component: combinatorics | Milestone: sage-5.13
Keywords: trees, binary trees, latex | Resolution:
Authors: Jean-Baptiste Priez | Merged in:
Report Upstream: N/A | Reviewers:
Branch: | Work issues:
Dependencies: #8703, #14784 | Commit:
| Stopgaps:
----------------------------------------------+----------------------------
Comment (by darij):
I have posted a new version of [attachment:trac_14498-tree-imps-
dg.patch]. Unfortunately a lot more is needed for a review, but I think
this is a step forward. The following issues have been fixed:
* The issues discussed in #14564 (leaves vs. leaves-and-nodes
inconsistencies, and border cases) have been fixed.\\
* The implementation and the documentation of the q-hook-length formula
has been revamped (even the name is now different).\\
* Various documentation has been rewritten.
Things that remain to be done:
* Frederic suggested on #14564 that the docstring for {{{is_full}}} is
wrong, but I don't understand in what way.\\
* {{{BinaryTree()}}} is a functioning shortcut for {{{BinaryTree(None)}}},
but {{{LabelledBinaryTree()}}} is not a functioning shortcut for
{{{LabelledBinaryTree(None)}}}. Should this be fixed? Using init_extra?\\
* It is not obvious to me that the {{{tamari_succ}}} and {{{tamari_prec}}}
methods actually compute the successors resp. predecessors in the Tamari
order. Is there a proof somewhere in the literature? It's clear that every
successor of a tree t in the Tamari poset is obtained by a right rotation,
but is it clear that every right rotate is actually a successor?\\
* The {{{over}}} method defines the "over" operation. As I wrote in the
docstring: " Fix this doc and figure out which of the different
(inconsistent?) notations to follow. I don't see the "over" operation
defined in [LodayRonco]_, although [HNT05]_ pretends that it is defined
there. In [HNT05]_ the definition is somewhat vague about the order of the
operads. Loday and Ronco seem to define "over" on page 2 of "Order
structure on the algebra of permutations and of planar binary trees", but
with a different choice of left/right."\\
* The docstring of the class {{{LabelledBinaryTree}}} could be less
barren; in particular it could explain how to initialize these.\\
* The {{{binary_search_insert}}} docstring might use a definition of
binary search insertion, given that most sources only do it in the
standard (i. e., no two equal labels) case.\\
I fear I won't come back to this patch very soon, so everyone who feels
like improving these is invited to do so.
For the patchbot:
apply trac_14498-algorithms_trees-rebased.patch trac_14498-tree-imps-
dg.patch
--
Ticket URL: <http://trac.sagemath.org/ticket/14498#comment:31>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
