core.py

"""
Cores

A `k`-core is a partition from which no rim hook of size `k` can be removed.
Alternatively, a `k`-core is an integer partition such that the Ferrers
diagram for the partition contains no cells with a hook of size (a
multiple of) `k`.

Authors:

- Anne Schilling and Mike Zabrocki (2011): initial version
- Travis Scrimshaw (2012): Added latex output for Core class
"""
#*****************************************************************************
#       Copyright (C) 2011 Anne Schilling <anne at math.ucdavis.edu>
#                          Mike Zabrocki  <zabrocki at mathstat.yorku.ca>
#
#  Distributed under the terms of the GNU General Public License (GPL)
#
#    This code is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
#    General Public License for more details.
#
#  The full text of the GPL is available at:
#
#                  http://www.gnu.org/licenses/
#****************************************************************************

from sage.misc.classcall_metaclass import ClasscallMetaclass
from sage.structure.unique_representation import UniqueRepresentation
from sage.structure.parent import Parent
from sage.structure.element import Element
from sage.combinat.partition import Partitions, Partition
from sage.combinat.combinat import CombinatorialObject
from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets
from sage.functions.other import floor
from sage.combinat.combinatorial_map import combinatorial_map

class Core(CombinatorialObject, Element):
    r"""
    A `k`-core is an integer partition from which no rim hook of size `k`
    can be removed.

    EXAMPLES::

        sage: c = Core([2,1],4); c
        [2, 1]
        sage: c = Core([3,1],4); c
        Traceback (most recent call last):
        ...
        ValueError: [3, 1] is not a 4-core
    """

    __metaclass__ = ClasscallMetaclass

    @staticmethod
    def __classcall_private__(cls, part, k):
        r"""
        Implements the shortcut ``Core(part, k)`` to ``Cores(k,l)(part)``
        where `l` is the length of the core.

        TESTS::

            sage: c = Core([2,1],4); c
            [2, 1]
            sage: c.parent()
            4-Cores of length 3
            sage: type(c)
            <class 'sage.combinat.core.Cores_length_with_category.element_class'>

            sage: Core([2,1],3)
            Traceback (most recent call last):
            ...
            ValueError: [2, 1] is not a 3-core
        """
        if isinstance(part, cls):
            return part
        part = Partition(part)
        if not part.is_core(k):
            raise ValueError("%s is not a %s-core"%(part, k))
        l = sum(part.k_boundary(k).row_lengths())
        return Cores(k, l)(part)

    def __init__(self, parent, core):
        """
        TESTS::

            sage: C = Cores(4,3)
            sage: c = C([2,1]); c
            [2, 1]
            sage: type(c)
            <class 'sage.combinat.core.Cores_length_with_category.element_class'>
            sage: c.parent()
            4-Cores of length 3
            sage: TestSuite(c).run()

            sage: C = Cores(3,3)
            sage: C([2,1])
            Traceback (most recent call last):
            ...
            ValueError: [2, 1] is not a 3-core
        """
        k = parent.k
        part = Partition(core)
        if not part.is_core(k):
            raise ValueError("%s is not a %s-core"%(part, k))
        CombinatorialObject.__init__(self, core)
        Element.__init__(self, parent)

    def _latex_(self):
        """
        Outputs the LaTeX representation of this core as a partition. See the
        ``_latex_()`` method of :class:`Partition`.

        EXAMPLES::

            sage: c = Core([2,1],4)
            sage: latex(c)
            {\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}}
            \raisebox{-.6ex}{$\begin{array}[b]{*{2}c}\cline{1-2}
            \lr{\phantom{x}}&\lr{\phantom{x}}\\\cline{1-2}
            \lr{\phantom{x}}\\\cline{1-1}
            \end{array}$}
            }
        """
        return self.to_partition()._latex_()

    def k(self):
        r"""
        Returns `k` of the `k`-core ``self``.

        EXAMPLES::

            sage: c = Core([2,1],4)
            sage: c.k()
            4
        """
        return self.parent().k

    @combinatorial_map(name="to partition")
    def to_partition(self):
        r"""
        Turns the core ``self`` into the partition identical to ``self``.

        EXAMPLES::

            sage: mu = Core([2,1,1],3)
            sage: mu.to_partition()
            [2, 1, 1]
        """
        return Partition(self)

    @combinatorial_map(name="to bounded partition")
    def to_bounded_partition(self):
        r"""
        Bijection between `k`-cores and `(k-1)`-bounded partitions.

        Maps the `k`-core ``self`` to the corresponding `(k-1)`-bounded partition.
        This bijection is achieved by deleting all cells in ``self`` of hook length
        greater than `k`.

        EXAMPLES::

            sage: gamma = Core([9,5,3,2,1,1], 5)
            sage: gamma.to_bounded_partition()
            [4, 3, 2, 2, 1, 1]
        """
        k_boundary = self.to_partition().k_boundary(self.k())
        return Partition(k_boundary.row_lengths())

    def size(self):
        r"""
        Returns the size of ``self`` as a partition.

        EXAMPLES::

            sage: Core([2,1],4).size()
            3
            sage: Core([4,2],3).size()
            6
        """
        return self.to_partition().size()

    def length(self):
        r"""
        Returns the length of ``self``.

        The length of a `k`-core is the size of the corresponding `(k-1)`-bounded partition
        which agrees with the length of the corresponding Grassmannian element,
        see :meth:`to_grassmannian`.

        EXAMPLES::

            sage: c = Core([4,2],3); c.length()
            4
            sage: c.to_grassmannian().length()
            4

            sage: Core([9,5,3,2,1,1], 5).length()
            13
        """
        return self.to_bounded_partition().size()

    def to_grassmannian(self):
        r"""
        Bijection between `k`-cores and Grassmannian elements in the affine Weyl group of type `A_{k-1}^{(1)}`.

        For further details, see the documentation of the method
        :meth:`~sage.combinat.partition.Partition.from_kbounded_to_reduced_word` and
        :meth:`~sage.combinat.partition.Partition.from_kbounded_to_grassmannian`.

        EXAMPLES::

            sage: c = Core([3,1,1],3)
            sage: w = c.to_grassmannian(); w
            [-1  1  1]
            [-2  2  1]
            [-2  1  2]
            sage: c.parent()
            3-Cores of length 4
            sage: w.parent()
            Weyl Group of type ['A', 2, 1] (as a matrix group acting on the root space)

            sage: c = Core([],3)
            sage: c.to_grassmannian()
            [1 0 0]
            [0 1 0]
            [0 0 1]
        """
        return self.to_bounded_partition().from_kbounded_to_grassmannian(self.k()-1)

    def affine_symmetric_group_simple_action(self, i):
        r"""
        Returns the action of the simple transposition `s_i` of the affine symmetric group on ``self``.

        This gives the action of the affine symmetric group of type `A_k^{(1)}` on the `k`-core
        ``self``. If ``self`` has outside (resp. inside) corners of content `i` modulo `k`, then
        these corners are added (resp. removed). Otherwise the action is trivial.

        EXAMPLES::

            sage: c = Core([4,2],3)
            sage: c.affine_symmetric_group_simple_action(0)
            [3, 1]
            sage: c.affine_symmetric_group_simple_action(1)
            [5, 3, 1]
            sage: c.affine_symmetric_group_simple_action(2)
            [4, 2]

        This action corresponds to the left action by the `i`-th simple reflection in the affine
        symmetric group::

            sage: c = Core([4,2],3)
            sage: W = c.to_grassmannian().parent()
            sage: i=0
            sage: c.affine_symmetric_group_simple_action(i).to_grassmannian() == W.simple_reflection(i)*c.to_grassmannian()
            True
            sage: i=1
            sage: c.affine_symmetric_group_simple_action(i).to_grassmannian() == W.simple_reflection(i)*c.to_grassmannian()
            True
        """
        mu = self.to_partition()
        corners = mu.outside_corners()
        corners = [ p for p in corners if mu.content(p[0],p[1])%self.k()==i ]
        if corners == []:
            corners = mu.corners()
            corners = [ p for p in corners if mu.content(p[0],p[1])%self.k()==i ]
            if corners == []:
                return self
            for p in corners:
                mu = mu.remove_cell(p[0])
        else:
            for p in corners:
                mu = mu.add_cell(p[0])
        return Core(mu, self.k())

    def affine_symmetric_group_action(self, w, transposition = False):
        r"""
        Returns the (left) action of the affine symmetric group on ``self``.

        INPUT:

        - ``w`` is a tupe of integers `[w_1,\ldots,w_m]` with `0\le w_j<k`.
          If transposition is set to be True, then `w = [w_0,w_1]` is
          interpreted as a transposition `t_{w_0, w_1}`
          (see :meth:`_transposition_to_reduced_word`).

        The output is the (left) action of the product of the corresponding simple transpositions
        on ``self``, that is `s_{w_1} \cdots s_{w_m}(self)`. See :meth:`affine_symmetric_group_simple_action`.

        EXAMPLES::

            sage: c = Core([4,2],3)
            sage: c.affine_symmetric_group_action([0,1,0,2,1])
            [8, 6, 4, 2]
            sage: c.affine_symmetric_group_action([0,2], transposition=True)
            [4, 2, 1, 1]

            sage: c = Core([11,8,5,5,3,3,1,1,1],4)
            sage: c.affine_symmetric_group_action([2,5],transposition=True)
            [11, 8, 7, 6, 5, 4, 3, 2, 1]
        """
        c = self
        if transposition:
            w = self._transposition_to_reduced_word(w)
        w.reverse()
        for i in w:
            c = c.affine_symmetric_group_simple_action(i)
        return c

    def _transposition_to_reduced_word(self, t):
        r"""
        Converts the transposition `t = [r,s]` to a reduced word.

        INPUT:

        - a tuple `[r,s]` such that `r` and `s` are not equivalent mod `k`

        OUTPUT:

        - a list of integers in `\{0,1,\ldots,k-1\}` representing a reduced word for the transposition `t`

        EXAMPLE::

            sage: c = Core([],4)
            sage: c._transposition_to_reduced_word([2, 5])
            [2, 3, 0, 3, 2]
            sage: c._transposition_to_reduced_word([2, 5]) == c._transposition_to_reduced_word([5,2])
            True
            sage: c._transposition_to_reduced_word([2, 2])
            Traceback (most recent call last):
            ...
            ValueError: t_0 and t_1 cannot be equal mod k

            sage: c = Core([],30)
            sage: c._transposition_to_reduced_word([4, 12])
            [4, 5, 6, 7, 8, 9, 10, 11, 10, 9, 8, 7, 6, 5, 4]

            sage: c = Core([],3)
            sage: c._transposition_to_reduced_word([4, 12])
            [1, 2, 0, 1, 2, 0, 2, 1, 0, 2, 1]
        """
        k = self.k()
        if (t[0]-t[1])%k == 0:
            raise ValueError("t_0 and t_1 cannot be equal mod k")
        if t[0] > t[1]:
            return self._transposition_to_reduced_word([t[1],t[0]])
        else:
            return [i%k for i in range(t[0],t[1]-floor((t[1]-t[0])/k))] + [(t[1]-floor((t[1]-t[0])/k)-2-i)%(k) for i in
                                                                           range(t[1]-floor((t[1]-t[0])/k)-t[0]-1)]

    def weak_le(self, other):
        r"""
        Weak order comparison on cores.

        INPUT:

        - ``other`` -- another `k`-core

        OUTPUT: a boolean

        Returns whether ``self`` <= ``other`` in weak order.

        EXAMPLES::

            sage: c = Core([4,2],3)
            sage: x = Core([5,3,1],3)
            sage: c.weak_le(x)
            True
            sage: c.weak_le([5,3,1])
            True

            sage: x = Core([4,2,2,1,1],3)
            sage: c.weak_le(x)
            False

            sage: x = Core([5,3,1],6)
            sage: c.weak_le(x)
            Traceback (most recent call last):
            ...
            ValueError: The two cores do not have the same k
        """
        if type(self) == type(other):
            if self.k() != other.k():
                raise ValueError("The two cores do not have the same k")
        else:
            other = Core(other, self.k())
        w = self.to_grassmannian()
        v = other.to_grassmannian()
        return w.weak_le(v, side='left')

    def weak_covers(self):
        r"""
        Returns a list of all elements that cover ``self`` in weak order.

        EXAMPLES::

            sage: c = Core([1],3)
            sage: c.weak_covers()
            [[2], [1, 1]]

            sage: c = Core([4,2],3)
            sage: c.weak_covers()
            [[5, 3, 1]]
        """
        w = self.to_grassmannian()
        S = w.upper_covers(side='left')
        S = [x for x in S if x.is_affine_grassmannian()]
        return [ x.affine_grassmannian_to_core() for x in set(S) ]

    def strong_le(self, other):
        r"""
        Strong order (Bruhat) comparison on cores.

        INPUT:

        - ``other`` -- another `k`-core

        OUTPUT: a boolean

        Returns whether ``self`` <= ``other`` in Bruhat (or strong) order.

        EXAMPLES::

            sage: c = Core([4,2],3)
            sage: x = Core([4,2,2,1,1],3)
            sage: c.strong_le(x)
            True
            sage: c.strong_le([4,2,2,1,1])
            True

            sage: x = Core([4,1],4)
            sage: c.strong_le(x)
            Traceback (most recent call last):
            ...
            ValueError: The two cores do not have the same k
        """
        if type(self) == type(other):
            if self.k()!=other.k():
                raise ValueError("The two cores do not have the same k")
        else:
            other = Core(other, self.k())
        return other.contains(self)

    def contains(self, other):
        r"""
        Checks whether ``self`` contains ``other``.

        INPUT:

        - ``other`` -- another `k`-core or a list

        OUTPUT: a boolean

        Returns ``True`` if the Ferrers diagram of ``self`` contains the
        Ferrers diagram of other.

        EXAMPLES::

            sage: c = Core([4,2],3)
            sage: x = Core([4,2,2,1,1],3)
            sage: x.contains(c)
            True
            sage: c.contains(x)
            False
        """
        la = self.to_partition()
        mu = Core(other, self.k()).to_partition()
        return la.contains(mu)

    def strong_covers(self):
        r"""
        Returns a list of all elements that cover ``self`` in strong order.

        EXAMPLES::

            sage: c = Core([1],3)
            sage: c.strong_covers()
            [[2], [1, 1]]
            sage: c = Core([4,2],3)
            sage: c.strong_covers()
            [[5, 3, 1], [4, 2, 1, 1]]
        """
        S = Cores(self.k(), length=self.length()+1)
        return [ ga for ga in S if ga.contains(self) ]

    def strong_down_list(self):
        r"""
        Returns a list of all elements that are covered by ``self`` in strong order.

        EXAMPLES::

            sage: c = Core([1],3)
            sage: c.strong_down_list()
            [[]]
            sage: c = Core([5,3,1],3)
            sage: c.strong_down_list()
            [[4, 2], [3, 1, 1]]
        """
        if self==[]:
            return []
        return [ga for ga in Cores(self.k(), length=self.length()-1) if self.contains(ga)]

def Cores(k, length = None, **kwargs):
    r"""
    A `k`-core is a partition from which no rim hook of size `k` can be removed.
    Alternatively, a `k`-core is an integer partition such that the Ferrers
    diagram for the partition contains no cells with a hook of size (a multiple of) `k`.

    The `k`-cores generally have two notions of size which are
    useful for different applications. One is the number of cells in the
    Ferrers diagram with hook less than `k`, the other is the total
    number of cells of the Ferrers diagram.  In the implementation in
    Sage, the first of notion is referred to as the ``length`` of the `k`-core
    and the second is the ``size`` of the `k`-core.  The class
    of Cores requires that either the size or the length of the elements in
    the class is specified.

    EXAMPLES:

    We create the set of the `4`-cores of length `6`. Here the length of a `k`-core is the size
    of the corresponding `(k-1)`-bounded partition, see also :meth:`~sage.combinat.core.Core.length`::

        sage: C = Cores(4, 6); C
        4-Cores of length 6
        sage: C.list()
        [[6, 3], [5, 2, 1], [4, 1, 1, 1], [4, 2, 2], [3, 3, 1, 1], [3, 2, 1, 1, 1], [2, 2, 2, 1, 1, 1]]
        sage: C.cardinality()
        7
        sage: C.an_element()
        [6, 3]

    We may also list the set of `4`-cores of size `6`, where the size is the number of boxes in the
    core, see also :meth:`~sage.combinat.core.Core.size`::

        sage: C = Cores(4, size=6); C
        4-Cores of size 6
        sage: C.list()
        [[4, 1, 1], [3, 2, 1], [3, 1, 1, 1]]
        sage: C.cardinality()
        3
        sage: C.an_element()
        [4, 1, 1]
    """
    if length is None and 'size' in kwargs:
        return Cores_size(k,kwargs['size'])
    elif length is not None:
        return Cores_length(k,length)
    else:
        raise ValueError("You need to either specify the length or size of the cores considered!")

class Cores_length(UniqueRepresentation, Parent):
    r"""
    The class of `k`-cores of length `n`.
    """

    def __init__(self, k, n):
        """
        TESTS::

            sage: C = Cores(3, 4)
            sage: TestSuite(C).run()

        """
        self.k = k
        self.n = n
        Parent.__init__(self, category = FiniteEnumeratedSets())

    def _repr_(self):
        """
        TESTS::

            sage: repr(Cores(4, 3))  #indirect doctest
            '4-Cores of length 3'
        """
        return "%s-Cores of length %s"%(self.k,self.n)

    def list(self):
        r"""
        Returns the list of all `k`-cores of length `n`.

        EXAMPLES::

            sage: C = Cores(3,4)
            sage: C.list()
            [[4, 2], [3, 1, 1], [2, 2, 1, 1]]
        """
        return [la.to_core(self.k-1) for la in Partitions(self.n, max_part=self.k-1)]

    def from_partition(self, part):
        r"""
        Converts the partition ``part`` into a core (as the identity map).

        This is the inverse method to :meth:`~sage.combinat.core.Core.to_partition`.

        EXAMPLES::

            sage: C = Cores(3,4)
            sage: c = C.from_partition([4,2]); c
            [4, 2]

            sage: mu = Partition([2,1,1])
            sage: C = Cores(3,3)
            sage: C.from_partition(mu).to_partition() == mu
            True

            sage: mu = Partition([])
            sage: C = Cores(3,0)
            sage: C.from_partition(mu).to_partition() == mu
            True
        """
        return Core(part, self.k)

    Element = Core


class Cores_size(UniqueRepresentation, Parent):
    r"""
    The class of `k`-cores of size `n`.
    """

    def __init__(self, k, n):
        """
        TESTS::

            sage: C = Cores(3, size = 4)
            sage: TestSuite(C).run()
        """
        self.k = k
        self.n = n
        Parent.__init__(self, category = FiniteEnumeratedSets())

    def _repr_(self):
        """
        TESTS::

            sage: repr(Cores(4, size = 3))  #indirect doctest
            '4-Cores of size 3'
        """
        return "%s-Cores of size %s"%(self.k,self.n)

    def list(self):
        r"""
        Returns the list of all `k`-cores of size `n`.

        EXAMPLES::

            sage: C = Cores(3, size = 4)
            sage: C.list()
            [[3, 1], [2, 1, 1]]
        """
        k_cores = filter(lambda x: x.is_core(self.k), Partitions(self.n))
        return [ Core(x, self.k) for x in k_cores ]

    def from_partition(self, part):
        r"""
        Converts the partition ``part`` into a core (as the identity map).

        This is the inverse method to :meth:`to_partition`.

        EXAMPLES::

            sage: C = Cores(3,size=4)
            sage: c = C.from_partition([2,1,1]); c
            [2, 1, 1]

            sage: mu = Partition([2,1,1])
            sage: C = Cores(3,size=4)
            sage: C.from_partition(mu).to_partition() == mu
            True

            sage: mu = Partition([])
            sage: C = Cores(3,size=0)
            sage: C.from_partition(mu).to_partition() == mu
            True
        """
        return Core(part, self.k)

    Element = Core