summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorFrédéric Chapoton <chapoton@math.univ-lyon1.fr>2017-04-03 22:22:54 +0200
committerFrédéric Chapoton <chapoton@math.univ-lyon1.fr>2017-04-03 22:22:54 +0200
commit384b80ca08e4062643a2ea01adda27b1bfab4dce (patch)
treec4fc58ef997b78b28e91bbeb20e830dc4e5982f9
parentUpdated SageMath version to 8.0.beta0 (diff)
parenttrac 13987 some doc details (diff)
Merge branch 'public/combinat/13987-mary-trees' in 8.0.b0
-rw-r--r--src/sage/combinat/all.py6
-rw-r--r--src/sage/combinat/mary_tree.py950
2 files changed, 955 insertions, 1 deletions
diff --git a/src/sage/combinat/all.py b/src/sage/combinat/all.py
index c6bee3f..c8752b6 100644
--- a/src/sage/combinat/all.py
+++ b/src/sage/combinat/all.py
@@ -119,8 +119,12 @@ from .parking_functions import ParkingFunctions, ParkingFunction
# Trees and Tamari interval posets
from .ordered_tree import (OrderedTree, OrderedTrees,
LabelledOrderedTree, LabelledOrderedTrees)
+
+from .mary_tree import (MAryTree, MAryTrees,
+ LabelledMAryTree, LabelledMAryTrees)
+
from .binary_tree import (BinaryTree, BinaryTrees,
- LabelledBinaryTree, LabelledBinaryTrees)
+ LabelledBinaryTree, LabelledBinaryTrees)
lazy_import('sage.combinat.interval_posets', ['TamariIntervalPoset', 'TamariIntervalPosets'])
from .rooted_tree import (RootedTree, RootedTrees,
diff --git a/src/sage/combinat/mary_tree.py b/src/sage/combinat/mary_tree.py
new file mode 100644
index 00000000..42e4ba5
--- /dev/null
+++ b/src/sage/combinat/mary_tree.py
@@ -0,0 +1,950 @@
+r"""
+`m`-ary trees
+
+This module deals with `m`-ary trees as mathematical (in particular immmutable)
+objects.
+
+This is different from rooted trees as we want to fix the number of subtrees.
+"""
+#*****************************************************************************
+# Copyright (C) 2010 Florent Hivert <Florent.Hivert@univ-rouen.fr>,
+#
+# Distributed under the terms of the GNU General Public License (GPL)
+# as published by the Free Software Foundation; either version 2 of
+# the License, or (at your option) any later version.
+# http://www.gnu.org/licenses/
+#*****************************************************************************
+from six import add_metaclass
+
+from sage.structure.list_clone import ClonableArray
+from sage.combinat.abstract_tree import (AbstractClonableTree,
+ AbstractLabelledClonableTree)
+from sage.combinat.ordered_tree import LabelledOrderedTrees
+from sage.rings.integer import Integer
+from sage.misc.inherit_comparison import InheritComparisonClasscallMetaclass
+from sage.misc.classcall_metaclass import ClasscallMetaclass
+from sage.misc.lazy_attribute import lazy_attribute
+from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets
+from sage.structure.parent import Parent
+from sage.structure.unique_representation import UniqueRepresentation
+from sage.arith.all import binomial
+from sage.sets.non_negative_integers import NonNegativeIntegers
+from sage.sets.disjoint_union_enumerated_sets import DisjointUnionEnumeratedSets
+from sage.sets.family import Family
+from sage.misc.cachefunc import cached_method
+
+
+@add_metaclass(InheritComparisonClasscallMetaclass)
+class MAryTree(AbstractClonableTree, ClonableArray):
+ r"""
+ The class of `m`-ary trees
+
+ INPUT:
+
+ - `m` -- the arity
+
+ - ``children`` -- ``None`` (default) or a list, tuple or iterable of
+ length `m` of `m`-ary trees or convertible objects.
+
+ - ``check`` -- (default to ``True``) whether check for `m`-arity should be
+ performed or not.
+
+ EXAMPLES::
+
+ sage: MAryTree(3)
+ .
+ sage: MAryTree(3, [])
+ [., ., .]
+ sage: MAryTree(3, [None, [], None])
+ [., [., ., .], .]
+ sage: MAryTree(3, [[], None, None])
+ [[., ., .], ., .]
+ sage: MAryTree(3, [[], None])
+ Traceback (most recent call last):
+ ...
+ TypeError: This is not a 3-ary tree
+ """
+ @staticmethod
+ def __classcall_private__(cls, *args, **opts):
+ r"""
+ Ensure that `m`-ary trees created by the enumerated sets and directly
+ are the same and that they are instances of :class:`MAryTree`
+
+ TESTS::
+
+ sage: from sage.combinat.mary_tree import MAryTrees_all
+ sage: issubclass(MAryTrees_all(3).element_class, MAryTree)
+ True
+ sage: t0 = MAryTree(3, [[], None, []])
+ sage: t0.parent()
+ 3-ary trees
+ sage: type(t0)
+ <class 'sage.combinat.mary_tree.MAryTrees_all_with_category.element_class'>
+ sage: t1 = MAryTrees(3)([[], None, []])
+ sage: t1.parent() is t0.parent()
+ True
+ sage: t1 = MAryTrees(3, 3)([[], None, []])
+ sage: t1.parent() is t0.parent()
+ True
+ sage: type(t1) is type(t0)
+ True
+ """
+ m = args[0]
+ parent = cls._auto_parent(m)
+ args = args[1:]
+ return parent.element_class(parent, *args, **opts)
+
+ @staticmethod
+ def _auto_parent(m):
+ """
+ The automatic parent of the element of this class depending of
+ the arity
+
+ When calling the constructor of an element of this class, one needs a
+ parent. This class attribute specifies which parent is used.
+
+ INPUT:
+
+ - `m` -- the arity of the tree
+
+ EXAMPLES::
+
+ sage: MAryTree._auto_parent(3)
+