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
""" Species structures
We will illustrate the use of the structure classes using the "balls and bars" model for integer compositions. An integer composition of 6 such as [2, 1, 3] can be represented in this model as 'oooooo' where the 6 o's correspond to the balls and the 2 's correspond to the bars. If BB is our species for this model, the it satisfies the following recursive definition:
BB = o + o\*BB + o\*|\*BB
Here we define this species using the default structures::
sage: ball = species.SingletonSpecies(); o = var('o') sage: bar = species.EmptySetSpecies() sage: BB = CombinatorialSpecies() sage: BB.define(ball + ball*BB + ball*bar*BB) sage: BB.isotypes([o]*3).list() [o*(o*o), o*((o*{})*o), (o*{})*(o*o), (o*{})*((o*{})*o)]
If we ignore the parentheses, we can read off that the integer compositions are [3], [2, 1], [1, 2], and [1, 1, 1]. """ #***************************************************************************** # Copyright (C) 2008 Mike Hansen <mhansen@gmail.com>, # # 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.combinat.combinat import CombinatorialClass, CombinatorialObject from sage.rings.integer import Integer from copy import copy
class GenericSpeciesStructure(CombinatorialObject): def __init__(self, parent, labels, list): """ This is a base class from which the classes for the structures inherit.
EXAMPLES::
sage: from sage.combinat.species.structure import GenericSpeciesStructure sage: a = GenericSpeciesStructure(None, [2,3,4], [1,2,3]) sage: a [2, 3, 4] sage: a.parent() is None True sage: a == loads(dumps(a)) True """
def parent(self): """ Returns the species that this structure is associated with.
EXAMPLES::
sage: L = species.LinearOrderSpecies() sage: a,b = L.structures([1,2]) sage: a.parent() Linear order species """ except AttributeError: raise NotImplementedError
def __repr__(self): """ EXAMPLES::
sage: from sage.combinat.species.structure import GenericSpeciesStructure sage: a = GenericSpeciesStructure(None, [2,3,4], [1,2,3]) sage: a [2, 3, 4] """
def __eq__(self, other): """ Check whether ``self`` is equal to ``other``.
EXAMPLES::
sage: T = species.BinaryTreeSpecies() sage: t = T.structures([1,2,3])[0]; t 1*(2*3) sage: t[0], t[1][0] (1, 2) sage: t[0] == t[1][0] False """ return False
def __ne__(self, other): """ Check whether ``self`` is not equal to ``other``.
EXAMPLES::
sage: T = species.BinaryTreeSpecies() sage: t = T.structures([1,2,3])[0]; t 1*(2*3) sage: t[0], t[1][0] (1, 2) sage: t[0] != t[1][0] True """
def labels(self): """ Returns the labels used for this structure.
.. note::
This includes labels which may not "appear" in this particular structure.
EXAMPLES::
sage: P = species.SubsetSpecies() sage: s = P.structures(["a", "b", "c"]).random_element() sage: s.labels() ['a', 'b', 'c'] """
def change_labels(self, labels): """ Return a relabelled structure.
INPUT:
- ``labels``, a list of labels.
OUTPUT:
A structure with the i-th label of self replaced with the i-th label of the list.
EXAMPLES::
sage: P = species.SubsetSpecies() sage: S = P.structures(["a", "b", "c"]) sage: [s.change_labels([1,2,3]) for s in S] [{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}] """
def _relabel(self, i): """ EXAMPLES::
sage: from sage.combinat.species.structure import GenericSpeciesStructure sage: a = GenericSpeciesStructure(None, [2,3,4], [1,2,3]) sage: a._relabel(1) 2 sage: a._relabel([1,2,3]) [1, 2, 3] """ else:
def is_isomorphic(self, x): """ EXAMPLES::
sage: S = species.SetSpecies() sage: a = S.structures([1,2,3]).random_element(); a {1, 2, 3} sage: b = S.structures(['a','b','c']).random_element(); b {'a', 'b', 'c'} sage: a.is_isomorphic(b) True """ return False return False
#We don't care about the labels for isomorphism testing else: return False
#For backward compatibility. This should be removed in the near #future since I doubt that there is any code that depends directly on #SpeciesStructure. SpeciesStructure = GenericSpeciesStructure
class SpeciesStructureWrapper(GenericSpeciesStructure): def __init__(self, parent, s, **options): """ This is a class for the structures of species such as the sum species that do not provide "additional" structure. For example, if you have the sum `C` of species `A` and `B`, then a structure of `C` will either be either something from `A` or `B`. Instead of just returning one of these directly, a "wrapper" is put around them so that they have their parent is `C` rather than `A` or `B`::
sage: X = species.SingletonSpecies() sage: X2 = X+X sage: s = X2.structures([1]).random_element(); s 1 sage: s.parent() Sum of (Singleton species) and (Singleton species) sage: from sage.combinat.species.structure import SpeciesStructureWrapper sage: issubclass(type(s), SpeciesStructureWrapper) True
EXAMPLES::
sage: E = species.SetSpecies(); B = E+E sage: s = B.structures([1,2,3]).random_element() sage: s.parent() Sum of (Set species) and (Set species) sage: s == loads(dumps(s)) True """
def __getattr__(self, attr): """ EXAMPLES::
sage: E = species.SetSpecies(); B = E+E sage: s = B.structures([1,2,3]).random_element() sage: s {1, 2, 3} """
def __repr__(self): """ Returns the repr of the object which this one wraps.
EXAMPLES::
sage: E = species.SetSpecies() sage: s = (E+E).structures([1,2,3]).random_element(); s {1, 2, 3} """
def transport(self, perm): """ EXAMPLES::
sage: P = species.PartitionSpecies() sage: s = (P+P).structures([1,2,3]).random_element(); s {{1, 3}, {2}} sage: s.transport(PermutationGroupElement((2,3))) {{1, 2}, {3}} """
def canonical_label(self): """ EXAMPLES::
sage: P = species.PartitionSpecies() sage: s = (P+P).structures([1,2,3]).random_element(); s {{1, 3}, {2}} sage: s.canonical_label() {{1, 2}, {3}} """
def change_labels(self, labels): """ Return a relabelled structure.
INPUT:
- ``labels``, a list of labels.
OUTPUT:
A structure with the i-th label of self replaced with the i-th label of the list.
EXAMPLES::
sage: X = species.SingletonSpecies() sage: X2 = X+X sage: s = X2.structures([1]).random_element(); s 1 sage: s.change_labels(['a']) 'a' """
##############################################################
class SpeciesWrapper(CombinatorialClass): def __init__(self, species, labels, iterator, generating_series, name, structure_class): """ This is a abstract base class for the set of structures of a species as well as the set of isotypes of the species.
.. note::
One typically does not use :class:`SpeciesWrapper` directly, but instead instantiates one of its subclasses: :class:`StructuresWrapper` or :class:`IsotypesWrapper`.
EXAMPLES::
sage: from sage.combinat.species.structure import SpeciesWrapper sage: F = species.SetSpecies() sage: S = SpeciesWrapper(F, [1,2,3], "_structures", "generating_series", 'Structures', None) sage: S Structures for Set species with labels [1, 2, 3] sage: S.list() [{1, 2, 3}] sage: S.cardinality() 1 """
def labels(self): """ Returns the labels used on these structures. If `X` is the species, then :meth:`labels` returns the preimage of these structures under the functor `X`.
EXAMPLES::
sage: F = species.SetSpecies() sage: F.structures([1,2,3]).labels() [1, 2, 3] """
def __iter__(self): """ EXAMPLES::
sage: F = species.SetSpecies() sage: F.structures([1,2,3]).list() [{1, 2, 3}] """ #If the min and max are set, then we want to make sure #that the iterator respects those bounds. len(self._labels) < self._species._min):
len(self._labels) >= self._species._max): return iter([])
#We check to see if the
def cardinality(self): """ Returns the number of structures in this set.
EXAMPLES::
sage: F = species.SetSpecies() sage: F.structures([1,2,3]).cardinality() 1 """
class StructuresWrapper(SpeciesWrapper): def __init__(self, species, labels, structure_class): """ A base class for the set of structures of a species with given set of labels. An object of this type is returned when you call the :meth:`structures` method of a species.
EXAMPLES::
sage: F = species.SetSpecies() sage: S = F.structures([1,2,3]) sage: S == loads(dumps(S)) True """ "_structures", "generating_series", "Structures", structure_class)
class IsotypesWrapper(SpeciesWrapper): def __init__(self, species, labels, structure_class): """ A base class for the set of isotypes of a species with given set of labels. An object of this type is returned when you call the :meth:`isotypes` method of a species.
EXAMPLES::
sage: F = species.SetSpecies() sage: S = F.isotypes([1,2,3]) sage: S == loads(dumps(S)) True """ "_isotypes", "isotype_generating_series", "Isomorphism types", structure_class)
class SimpleStructuresWrapper(SpeciesWrapper): def __init__(self, species, labels, structure_class): """ .. warning::
This is deprecated and currently not used for anything.
EXAMPLES::
sage: F = species.SetSpecies() sage: S = F.structures([1,2,3]) sage: S == loads(dumps(S)) True """ SpeciesWrapper.__init__(self, species, labels, "_simple_structures_selector", "generating_series", "Simple structures", structure_class)
class SimpleIsotypesWrapper(SpeciesWrapper): def __init__(self, species, labels, structure_class): """ .. warning::
This is deprecated and currently not used for anything.
EXAMPLES::
sage: F = species.SetSpecies() sage: S = F.structures([1,2,3]) sage: S == loads(dumps(S)) True """ SpeciesWrapper.__init__(self, species, labels, "_simple_isotypes_selector", "isotype_generating_series", "Simple isomorphism types", structure_class) |