Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" Composition Tableaux
AUTHORS:
- Chris Berg, Jeff Ferreira (2012-9): Initial version """ from six.moves import range from six import add_metaclass
from sage.sets.disjoint_union_enumerated_sets import DisjointUnionEnumeratedSets from sage.sets.non_negative_integers import NonNegativeIntegers from sage.sets.family import Family from sage.misc.classcall_metaclass import ClasscallMetaclass from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets from sage.structure.parent import Parent from sage.structure.unique_representation import UniqueRepresentation from sage.combinat.composition import Composition, Compositions from sage.combinat.partition import Partition from sage.combinat.combinat import CombinatorialElement from sage.rings.integer import Integer from sage.combinat.backtrack import GenericBacktracker import copy
@add_metaclass(ClasscallMetaclass) class CompositionTableau(CombinatorialElement): r""" A composition tableau.
A *composition tableau* `t` of shape `I = (I_1, \ldots, I_{\ell})` is an array of boxes in rows, `I_i` boxes in row `i`, filled with positive integers such that:
1) the entries in the rows of `t` weakly decrease from left to right, 2) the left-most column of `t` strictly increase from top to bottom. 3) Add zero entries to the rows of `t` until the resulting array is rectangular of shape `\ell \times m`. For `1 \leq i < j \leq \ell, 2 \leq k \leq m` and `(t(j,k) \neq 0`, and also if `t(j,k) \geq t(i,k))` implies `t(j,k) > t(i,k-1).`
INPUT:
- ``t`` -- A list of lists
EXAMPLES::
sage: CompositionTableau([[1],[2,2]]) [[1], [2, 2]] sage: CompositionTableau([[1],[3,2],[4,4]]) [[1], [3, 2], [4, 4]] sage: CompositionTableau([]) [] """ @staticmethod def __classcall_private__(self, t): r""" This ensures that a composition tableau is only ever constructed as an ``element_class`` call of an appropriate parent.
TESTS::
sage: t = CompositionTableau([[1],[2,2]]) sage: TestSuite(t).run()
sage: t.parent() Composition Tableaux sage: t.category() Category of elements of Composition Tableaux """ return t
def __init__(self, parent, t): r""" Initialize a composition tableau.
TESTS::
sage: t = CompositionTableaux()([[1],[2,2]]) sage: s = CompositionTableaux(3)([[1],[2,2]]) sage: s==t True sage: t.parent() Composition Tableaux sage: s.parent() Composition Tableaux of size 3 and maximum entry 3 sage: r = CompositionTableaux()(s) sage: r.parent() Composition Tableaux """
# CombinatorialObject verifies that t is a list # We must verify t is a list of lists raise ValueError("A composition tableau must be a list of lists.")
raise ValueError("A composition tableau must be a list of non-empty lists.")
# Verify rows weakly decrease from left to right raise ValueError("Rows must weakly decrease from left to right.")
# Verify leftmost column strictly increases from top to bottom raise ValueError("Leftmost column must strictly increase from top to bottom.")
# Verify triple condition raise ValueError("Triple condition must be satisfied.")
def _repr_diagram(self): r""" Return a string representation of ``self`` as an array.
EXAMPLES::
sage: t = CompositionTableau([[1],[3,2],[4,4]]) sage: print(t._repr_diagram()) 1 3 2 4 4 """
def __call__(self, *cell): r""" Return the value in the corresponding cell of ``self``.
EXAMPLES::
sage: t = CompositionTableau([[1],[3,2],[4,4]]) sage: t(1,1) 2 sage: t(2,0) 4 sage: t(2,2) Traceback (most recent call last): ... IndexError: The cell (2,2) is not contained in [[1], [3, 2], [4, 4]] """ except ValueError: i,j = cell[0]
def pp(self): r""" Return a pretty print string of ``self``.
EXAMPLES::
sage: CompositionTableau([[1],[3,2],[4,4]]).pp() 1 3 2 4 4 """
def size(self): r""" Return the number of boxes in ``self``.
EXAMPLES::
sage: CompositionTableau([[1],[3,2],[4,4]]).size() 5 """
def weight(self): r""" Return a composition where entry `i` is the number of times that `i` appears in ``self``.
EXAMPLES::
sage: CompositionTableau([[1],[3,2],[4,4]]).weight() [1, 1, 1, 2, 0] """
def descent_set(self): r""" Return the set of all `i` that do *not* have `i+1` appearing strictly to the left of `i` in ``self``.
EXAMPLES::
sage: CompositionTableau([[1],[3,2],[4,4]]).descent_set() [1, 3] """
def descent_composition(self): r""" Return the composition corresponding to the set of all `i` that do not have `i+1` appearing strictly to the left of `i` in ``self``.
EXAMPLES::
sage: CompositionTableau([[1],[3,2],[4,4]]).descent_composition() [1, 2, 2] """
def shape_composition(self): r""" Return a Composition object which is the shape of ``self``.
EXAMPLES::
sage: CompositionTableau([[1,1],[3,2],[4,4,3]]).shape_composition() [2, 2, 3] sage: CompositionTableau([[2,1],[3],[4]]).shape_composition() [2, 1, 1] """
def shape_partition(self): r""" Return a partition which is the shape of ``self`` sorted into weakly decreasing order.
EXAMPLES::
sage: CompositionTableau([[1,1],[3,2],[4,4,3]]).shape_partition() [3, 2, 2] sage: CompositionTableau([[2,1],[3],[4]]).shape_partition() [2, 1, 1] """
def is_standard(self): r""" Return ``True`` if ``self`` is a standard composition tableau and ``False`` otherwise.
EXAMPLES::
sage: CompositionTableau([[1,1],[3,2],[4,4,3]]).is_standard() False sage: CompositionTableau([[2,1],[3],[4]]).is_standard() True """
class CompositionTableaux(UniqueRepresentation, Parent): r""" Composition tableaux.
INPUT:
Keyword arguments:
- ``size`` -- the size of the composition tableaux - ``shape`` -- the shape of the composition tableaux - ``max_entry`` -- the maximum entry for the composition tableaux
Positional arguments:
- The first argument is interpreted as ``size`` or ``shape`` depending on whether it is an integer or a composition.
EXAMPLES::
sage: CT = CompositionTableaux(3); CT Composition Tableaux of size 3 and maximum entry 3 sage: list(CT) [[[1], [2], [3]], [[1], [2, 2]], [[1], [3, 2]], [[1], [3, 3]], [[2], [3, 3]], [[1, 1], [2]], [[1, 1], [3]], [[2, 1], [3]], [[2, 2], [3]], [[1, 1, 1]], [[2, 1, 1]], [[2, 2, 1]], [[2, 2, 2]], [[3, 1, 1]], [[3, 2, 1]], [[3, 2, 2]], [[3, 3, 1]], [[3, 3, 2]], [[3, 3, 3]]]
sage: CT = CompositionTableaux([1,2,1]); CT Composition tableaux of shape [1, 2, 1] and maximum entry 4 sage: list(CT) [[[1], [2, 2], [3]], [[1], [2, 2], [4]], [[1], [3, 2], [4]], [[1], [3, 3], [4]], [[2], [3, 3], [4]]]
sage: CT = CompositionTableaux(shape=[1,2,1],max_entry=3); CT Composition tableaux of shape [1, 2, 1] and maximum entry 3 sage: list(CT) [[[1], [2, 2], [3]]]
sage: CT = CompositionTableaux(2,max_entry=3); CT Composition Tableaux of size 2 and maximum entry 3 sage: list(CT) [[[1], [2]], [[1], [3]], [[2], [3]], [[1, 1]], [[2, 1]], [[2, 2]], [[3, 1]], [[3, 2]], [[3, 3]]]
sage: CT = CompositionTableaux(0); CT Composition Tableaux of size 0 and maximum entry 0 sage: list(CT) [[]] """ @staticmethod def __classcall_private__(cls, *args, **kwargs): r""" This is a factory class which returns the appropriate parent based on arguments. See the documentation for :class:`CompositionTableaux` for more information.
TESTS::
sage: CT = CompositionTableaux(3); CT Composition Tableaux of size 3 and maximum entry 3 sage: CT = CompositionTableaux(size=3); CT Composition Tableaux of size 3 and maximum entry 3 sage: CT = CompositionTableaux([1,2]); CT Composition tableaux of shape [1, 2] and maximum entry 3 sage: CT = CompositionTableaux(shape=[1,2]); CT Composition tableaux of shape [1, 2] and maximum entry 3 sage: CT = CompositionTableaux(shape=[]); CT Composition tableaux of shape [] and maximum entry 0 sage: CT = CompositionTableaux(0); CT Composition Tableaux of size 0 and maximum entry 0 sage: CT = CompositionTableaux(max_entry=3); CT Composition tableaux with maximum entry 3 sage: CT = CompositionTableaux([1,2],max_entry=3); CT Composition tableaux of shape [1, 2] and maximum entry 3 sage: CT = CompositionTableaux(size=2,shape=[1,2]); CT Traceback (most recent call last): ... ValueError: size and shape are different sizes """ # Process keyword arguments first
# Process positional arguments # The first arg could be either a size or a shape raise ValueError("size was specified more than once") else: else: raise ValueError("the shape was specified more than once")
# Consistency checks raise ValueError("size must be an integer") raise ValueError("size must be non-negative")
# use in (and not isinstance) below so that lists can be used as # shorthand raise ValueError("shape must be a composition") raise ValueError("shape must have non-zero parts")
raise ValueError("max_entry must be an integer") raise ValueError("max_entry must be positive")
# Dispatch to appropriate class
def __init__(self, **kwds): r""" Initialize ``self``.
TESTS::
sage: CT = CompositionTableaux() sage: TestSuite(CT).run() """ else: self.max_entry = None
Element = CompositionTableau
def _element_constructor_(self, t): r""" Construct an object from ``t`` as an element of ``self``, if possible.
INPUT:
- ``t`` -- data which can be interpreted as a composition tableau
OUTPUT:
- The corresponding CompositionTableau object
TESTS::
sage: CT = CompositionTableaux(3) sage: CT([[1],[2,2]]).parent() is CT True sage: CT([[1],[1,2]]) Traceback (most recent call last): ... ValueError: [[1], [1, 2]] is not an element of Composition Tableaux of size 3 and maximum entry 3. """
def __contains__(self, T): r""" Return ``True`` if ``T`` can be interpreted as :class:`CompositionTableau`.
TESTS::
sage: [[1],[2,2]] in CompositionTableaux(3) True sage: [[1],[2,2]] in CompositionTableaux(shape=[1,2]) True sage: CompositionTableau([[1],[2,2]]) in CompositionTableaux() True sage: [[1],[2,2],[2]] in CompositionTableaux() False """
# leftmost column of T strictly increases from top to bottom # rows of T weakly decrease from left to right return False # for 1 <= i < j <= len(comp), for 2 <= k <= m, # T[j,k] \neq 0 and T[j,k] >= T[i,k] ==> T[j,k] > T[i,k-1]
class CompositionTableaux_all(CompositionTableaux, DisjointUnionEnumeratedSets): r""" All composition tableaux. """ def __init__(self, max_entry=None): r""" Initialize ``self``.
TESTS::
sage: CT = CompositionTableaux() sage: TestSuite(CT).run() """ Family(NonNegativeIntegers(), CT_n), facade=True, keepkey = False)
def _repr_(self): r""" TESTS::
sage: CompositionTableaux(3) Composition Tableaux of size 3 and maximum entry 3
sage: CompositionTableaux() Composition Tableaux """
def an_element(self): r""" Return a particular element of ``self``.
EXAMPLES::
sage: CT = CompositionTableaux() sage: CT.an_element() [[1, 1], [2]] """
class CompositionTableaux_size(CompositionTableaux): r""" Composition tableaux of a fixed size `n`.
INPUT:
- ``n`` -- a nonnegative integer. - ``max_entry`` -- a nonnegative integer. This keyword argument defaults to ``n``.
OUTPUT:
- The class of composition tableaux of size ``n``. """ def __init__(self, n, max_entry=None): r""" Initializes the class of composition tableaux of size ``n``.
TESTS::
sage: CT = CompositionTableaux(4) sage: TestSuite(CT).run() """ category=FiniteEnumeratedSets())
def __contains__(self,x): r""" TESTS::
sage: [[1],[2,2]] in CompositionTableaux(3) True sage: [[1],[2,2]] in CompositionTableaux(4) False """
def __iter__(self): r""" EXAMPLES::
sage: [t for t in CompositionTableaux(3)] [[[1], [2], [3]], [[1], [2, 2]], [[1], [3, 2]], [[1], [3, 3]], [[2], [3, 3]], [[1, 1], [2]], [[1, 1], [3]], [[2, 1], [3]], [[2, 2], [3]], [[1, 1, 1]], [[2, 1, 1]], [[2, 2, 1]], [[2, 2, 2]], [[3, 1, 1]], [[3, 2, 1]], [[3, 2, 2]], [[3, 3, 1]], [[3, 3, 2]], [[3, 3, 3]]]
sage: CompositionTableaux(3)[0].parent() is CompositionTableaux(3) True """
def _repr_(self): r""" TESTS::
sage: CompositionTableaux(3) Composition Tableaux of size 3 and maximum entry 3 """
def _an_element_(self): r""" Return a particular element of ``self``.
EXAMPLES::
sage: CT = CompositionTableaux(4) sage: CT.an_element() [[1, 1, 1], [2]] sage: CompositionTableaux(0).an_element() [] sage: CompositionTableaux(1).an_element() [[1]] """
class CompositionTableaux_shape(CompositionTableaux): r""" Composition tableaux of a fixed shape ``comp`` with a given max entry.
INPUT:
- ``comp`` -- a composition. - ``max_entry`` -- a nonnegative integer. This keyword argument defaults to the size of ``comp``. """ def __init__(self, comp, max_entry=None): """ Initialize ``sefl``.
TESTS::
sage: CT = CompositionTableaux([1,2]) sage: TestSuite(CT).run()
sage: CT = CompositionTableaux([1,2], max_entry=4) sage: TestSuite(CT).run() """ category = FiniteEnumeratedSets())
def __iter__(self): r""" An iterator for composition tableaux of a given shape.
EXAMPLES::
sage: [t for t in CompositionTableaux([1,2])] [[[1], [2, 2]], [[1], [3, 2]], [[1], [3, 3]], [[2], [3, 3]]] sage: [t for t in CompositionTableaux([1,2],max_entry=4)] [[[1], [2, 2]], [[1], [3, 2]], [[1], [3, 3]], [[1], [4, 2]], [[1], [4, 3]], [[1], [4, 4]], [[2], [3, 3]], [[2], [4, 3]], [[2], [4, 4]], [[3], [4, 4]]] """ else:
def __contains__(self, x): r""" TESTS::
sage: [[2],[4,3]] in CompositionTableaux([1,2]) True sage: [[2],[3,2]] in CompositionTableaux([1,2]) False """
def _repr_(self): r""" TESTS::
sage: CompositionTableaux([1,2,1]) Composition tableaux of shape [1, 2, 1] and maximum entry 4 sage: CompositionTableaux([1,2,1],max_entry=3) Composition tableaux of shape [1, 2, 1] and maximum entry 3 """
def an_element(self): r""" Return a particular element of :class:`CompositionTableaux_shape`.
EXAMPLES::
sage: CT = CompositionTableaux([1,2,1]) sage: CT.an_element() [[1], [2, 2], [3]] """ return self.element_class(self, [])
class CompositionTableauxBacktracker(GenericBacktracker): r""" A backtracker class for generating sets of composition tableaux. """ def __init__(self, shape, max_entry=None): """ EXAMPLES::
sage: from sage.combinat.composition_tableau import CompositionTableauxBacktracker sage: n = CompositionTableauxBacktracker([1,3,2]) sage: n._ending_position (2, 1) sage: n._initial_state (0, 0) """
# The ending position will be at the lowest box which is farthest right
# Get the highest box that is farthest left
def _rec(self, obj, state): r""" EXAMPLES::
sage: from sage.combinat.composition_tableau import CompositionTableauxBacktracker sage: n = CompositionTableauxBacktracker([1,3,2]) sage: obj = [ [None], [None, None, None], [None, None] ] sage: list(n._rec(obj, n._initial_state)) [([[1], [None, None, None], [None, None]], (1, 0), False), ([[2], [None, None, None], [None, None]], (1, 0), False), ([[3], [None, None, None], [None, None]], (1, 0), False), ([[4], [None, None, None], [None, None]], (1, 0), False), ([[5], [None, None, None], [None, None]], (1, 0), False), ([[6], [None, None, None], [None, None]], (1, 0), False)] """ #Append zeros to a copy of obj
#We need to set the i,j^th entry.
#Get the next state
#We check to make sure that k does not violate the rule weak decrease in rows
#We check to make sure that k does not violate strict increase in first column
#We check to make sure that k does not violate the Triple Rule
#Fill in the in the i,j box with k
#Yield the object
def get_next_pos(self, ii, jj): r""" EXAMPLES::
sage: from sage.combinat.composition_tableau import CompositionTableauxBacktracker sage: T = CompositionTableau([[2,1],[5,4,3,2],[6],[7,7,6]]) sage: n = CompositionTableauxBacktracker(T.shape_composition()) sage: n.get_next_pos(1,1) (1, 2) """
|