Combinatorial m-ary trees

[VivianePons]

In the same manner as #8703 we want to implement trees with a fixed number of subtrees (equivalent of binary trees but with m subtrees). Especially to use them in the context of the m-Tamari lattices.

This ticket depends on #8703 as we use the implementation of OrderedTrees.

Related:

• generate k-trees up to symmetry #11369: generate k-trees up to symmetry
• Implement k-ary trees #19479: Implement k-ary trees

CC: @hivert @sagetrac-sage-combinat @tscrim @darijgr

Component: combinatorics

Keywords: trees

Author: Viviane Pons

Branch/Commit: public/new-13987 @ a2d92f4

Reviewer: Darij Grinberg

Issue created by migration from https://trac.sagemath.org/ticket/13987

[VivianePons]

Dependencies: #8703

[VivianePons]

Commit: e772581

[VivianePons]

New commits:

[changeset:e772581]

#N: a patch to implement m-ary trees

[VivianePons]

Branch: public/combinat/13987-mary-trees

[sagetrac-git]

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

34daa2f

Merge branch 'develop' into mary-trees

[sagetrac-git]

Changed commit from e772581 to 34daa2f

[sagetrac-git]

Changed commit from 34daa2f to 0334ad2

[sagetrac-git]

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

0334ad2

Merge branch 'public/combinat/13987-mary-trees' into 7.3.b3

[sagetrac-git]

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

21ea566	Merge branch 'public/combinat/13987-mary-trees' in 7.3.b6
aac90aa	trac 13987 refreshed branch

[sagetrac-git]

Changed commit from 0334ad2 to aac90aa

[sagetrac-git]

Changed commit from aac90aa to 847d49a

[sagetrac-git]

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

4cf00a2	Merge branch 'public/combinat/13987-mary-trees' in 7.5.b4
847d49a	trac 13987 some details, no more xrange

[mkoeppe]

comment:47

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[sagetrac-git]

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

2818096	Merge branch 'public/new-13987' in 9.2.b5
a2d92f4	fixes for python3 and dropped SearchForest

[sagetrac-git]

Changed commit from eb12c03 to a2d92f4

[mkoeppe]

comment:49

What's the status of the review on this ticket?

[darijgr]

comment:50

I don't remember more than is said in the comments above, and I'm not going to have time for this in the foreseeable time... sorry, not very useful I know.

[mkoeppe]

comment:52

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:53

Setting a new milestone for this ticket based on a cursory review.

[kevindilks]

comment:54

I'd like to try and help get this finished, though I'm not sure I'm qualified to be final judge and jury on the OOP/MRO aspects. At the very least, I can implement Travis's suggestion of removing LabelledMAryTrees.__call__ , and try to reverse the order of inheritance for class MAryTrees_all(DisjointUnionEnumeratedSets, MAryTrees) and remove the ```call`` and make sure nothing breaks.

In terms of m=2, people seem fine with having conversion for now, and having inheritance be part of a later ticket to get this finished.

I can implement Travis's suggestion that the documentation being clearer about these being ordered/plane trees.

In terms of check only checking the outer layer, I'm pretty sure this should be fine, and it will recursively check the entire tree. But I can try and make a test case to be sure.

I'll make a thorough pass in the next day or two to test things out, check doc and examples for clarity to somebody that may not be as familiar with m-ary trees, and make sure the doc compiles properly. One thing that's more a note to self to fix later when I do this is that enumerated m-ary trees of a given size is still labeled as 'enumerated set of binary trees of a given size' in the code.

Also reminder to self to check (1) as part of comment:37.

[kevindilks]

comment:55

In terms of class MAryTrees_all(DisjointUnionEnumeratedSets, MAryTrees)versus class MAryTrees_all(MAryTrees, DisjointUnionEnumeratedSets) , the way it is now matches what is done in binary trees.

I can't manage to track down exactly what's happening, but as the doc indicates, the __call__ methods are necessary to make sure that empty input is treated as None instead of getting passed as 0. Maybe something inherited from OrderedTrees and their assumption that there are no empty trees (and thus OrderedTrees()() == OrderedTrees()([])? Switching the MRO above did not resolve the issue.

This fix/hack is also implemented in BinaryTrees, though only for BinaryTrees_all. So BinaryTrees()() == BinaryTrees()(None) == ., but in BinaryTrees_size, BinaryTrees(0)() gives an error about the int 0 not being callable, whereas BinaryTrees(0)(None) == .

I would be of the opinion that if the way things done here is the way they've been forever in BinaryTrees, then they shouldn't be holding back this ticket from getting a positive review.

[mkoeppe]

comment:57

Stalled in needs_review or needs_info; likely won't make it into Sage 9.5.