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""" Integer vectors modulo the action of a permutation group """ #***************************************************************************** # Copyright (C) 2010-12 Nicolas Borie <nicolas.borie at math dot u-psud.fr> # # Distributed under the terms of the GNU General Public License (GPL) # # The full text of the GPL is available at: # http://www.gnu.org/licenses/ #***************************************************************************** from __future__ import print_function
from sage.structure.unique_representation import UniqueRepresentation from sage.rings.semirings.all import NN
from sage.categories.infinite_enumerated_sets import InfiniteEnumeratedSets from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets
from sage.structure.list_clone import ClonableIntArray from sage.combinat.backtrack import SearchForest
from sage.combinat.enumeration_mod_permgroup import is_canonical, orbit, canonical_children, canonical_representative_of_orbit_of
from sage.combinat.integer_vector import IntegerVectors
class IntegerVectorsModPermutationGroup(UniqueRepresentation): r""" Returns an enumerated set containing integer vectors which are maximal in their orbit under the action of the permutation group ``G`` for the lexicographic order.
In Sage, a permutation group `G` is viewed as a subgroup of the symmetric group `S_n` of degree `n` and `n` is said to be the degree of `G`. Any integer vector `v` is said to be canonical if it is maximal in its orbit under the action of `G`. `v` is canonical if and only if
.. MATH::
v = \max_{\text{lex order}} \{g \cdot v | g \in G \}
The action of `G` is on position. This means for example that the simple transposition `s_1 = (1, 2)` swaps the first and the second entries of any integer vector `v = [a_1, a_2, a_3, \dots , a_n]`
.. MATH::
s_1 \cdot v = [a_2, a_1, a_3, \dots , a_n]
This functions returns a parent which contains a single integer vector by orbit under the action of the permutation group `G`. The approach chosen here is to keep the maximal integer vector for the lexicographic order in each orbit. Such maximal vector will be called canonical integer vector under the action of the permutation group `G`.
INPUT:
- ``G`` - a permutation group - ``sum`` - (default: None) - a nonnegative integer - ``max_part`` - (default: None) - a nonnegative integer setting the maximum of entries of elements - ``sgs`` - (default: None) - a strong generating system of the group `G`. If you do not provide it, it will be calculated at the creation of the parent
OUTPUT:
- If ``sum`` and ``max_part`` are None, it returns the infinite enumerated set of all integer vectors (list of integers) maximal in their orbit for the lexicographic order.
- If ``sum`` is an integer, it returns a finite enumerated set containing all integer vectors maximal in their orbit for the lexicographic order and whose entries sum to ``sum``.
EXAMPLES:
Here is the set enumerating integer vectors modulo the action of the cyclic group of `3` elements::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3)]])) sage: I.category() Category of infinite enumerated quotients of sets sage: I.cardinality() +Infinity sage: I.list() Traceback (most recent call last): ... NotImplementedError: cannot list an infinite set sage: p = iter(I) sage: for i in range(10): next(p) [0, 0, 0] [1, 0, 0] [2, 0, 0] [1, 1, 0] [3, 0, 0] [2, 1, 0] [2, 0, 1] [1, 1, 1] [4, 0, 0] [3, 1, 0]
The method :meth:`~sage.combinat.integer_vectors_mod_permgroup.IntegerVectorsModPermutationGroup_All.is_canonical` tests if any integer vector is maximal in its orbit. This method is also used in the containment test::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: I.is_canonical([5,2,0,4]) True sage: I.is_canonical([5,0,6,4]) False sage: I.is_canonical([1,1,1,1]) True sage: [2,3,1,0] in I False sage: [5,0,5,0] in I True sage: 'Bla' in I False sage: I.is_canonical('bla') Traceback (most recent call last): ... AssertionError: bla should be a list or a integer vector
If you give a value to the extra argument ``sum``, the set returned will be a finite set containing only canonical vectors whose entries sum to ``sum``.::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3)]]), sum=6) sage: I.cardinality() 10 sage: I.list() [[6, 0, 0], [5, 1, 0], [5, 0, 1], [4, 2, 0], [4, 1, 1], [4, 0, 2], [3, 3, 0], [3, 2, 1], [3, 1, 2], [2, 2, 2]] sage: I.category() Join of Category of finite enumerated sets and Category of subquotients of finite sets and Category of quotients of sets
To get the orbit of any integer vector `v` under the action of the group, use the method :meth:`~sage.combinat.integer_vectors_mod_permgroup.IntegerVectorsModPermutationGroup_All.orbit`; we convert the returned set of vectors into a list in increasing lexicographic order, to get a reproducible test::
sage: sorted(I.orbit([6,0,0])) [[0, 0, 6], [0, 6, 0], [6, 0, 0]] sage: sorted(I.orbit([5,1,0])) [[0, 5, 1], [1, 0, 5], [5, 1, 0]] sage: I.orbit([2,2,2]) {[2, 2, 2]}
TESTS:
Let us check that canonical integer vectors of the symmetric group are just sorted list of integers::
sage: I = IntegerVectorsModPermutationGroup(SymmetricGroup(5)) # long time sage: p = iter(I) # long time sage: for i in range(100): # long time ....: v = list(next(p)) ....: assert sorted(v, reverse=True) == v
We now check that there is as much of canonical vectors under the symmetric group `S_n` whose entries sum to `d` than partitions of `d` of at most `n` parts::
sage: I = IntegerVectorsModPermutationGroup(SymmetricGroup(5)) # long time sage: for i in range(10): # long time ....: d1 = I.subset(i).cardinality() ....: d2 = Partitions(i, max_length=5).cardinality() ....: print(d1) ....: assert d1 == d2 1 1 2 3 5 7 10 13 18 23
We present a last corner case: trivial groups. For the trivial group ``G`` acting on a list of length `n`, all integer vectors of length `n` are canonical::
sage: G = PermutationGroup([[(6,)]]) # long time sage: G.cardinality() # long time 1 sage: I = IntegerVectorsModPermutationGroup(G) # long time sage: for i in range(10): # long time ....: d1 = I.subset(i).cardinality() ....: d2 = IntegerVectors(i,6).cardinality() ....: print(d1) ....: assert d1 == d2 1 6 21 56 126 252 462 792 1287 2002 """ @staticmethod def __classcall__(cls, G, sum=None, max_part=None, sgs=None): r""" TESTS::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3)]])) sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3)]]), None) sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3)]]), 2) sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3)]]), -2) Traceback (most recent call last): ... ValueError: Value -2 in not in Non negative integer semiring. sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3)]]), 8, max_part=5) """ else:
class IntegerVectorsModPermutationGroup_All(UniqueRepresentation, SearchForest): r""" A class for integer vectors enumerated up to the action of a permutation group.
A Sage permutation group is viewed as a subgroup of the symmetric group `S_n` for a certain `n`. This group has a natural action by position on vectors of length `n`. This class implements a set which keeps a single vector for each orbit. We say that a vector is canonical if it is the maximum in its orbit under the action of the permutation group for the lexicographic order.
EXAMPLES::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: I Integer vectors of length 4 enumerated up to the action of Permutation Group with generators [(1,2,3,4)] sage: I.cardinality() +Infinity sage: TestSuite(I).run() sage: it = iter(I) sage: [next(it), next(it), next(it), next(it), next(it)] [[0, 0, 0, 0], [1, 0, 0, 0], [2, 0, 0, 0], [1, 1, 0, 0], [1, 0, 1, 0]] sage: x = next(it); x [3, 0, 0, 0] sage: I.first() [0, 0, 0, 0]
TESTS::
sage: TestSuite(I).run() """ def __init__(self, G, sgs=None): """ TESTS::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: I Integer vectors of length 4 enumerated up to the action of Permutation Group with generators [(1,2,3,4)] sage: I.category() Category of infinite enumerated quotients of sets sage: TestSuite(I).run() """
# self.sgs: strong_generating_system else: self._sgs = [list(x) for x in list(sgs)]
def _repr_(self): """ TESTS::
sage: IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3)]])) Integer vectors of length 3 enumerated up to the action of Permutation Group with generators [(1,2,3)] """
def ambient(self): r""" Return the ambient space from which ``self`` is a quotient.
EXAMPLES::
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: S.ambient() Integer vectors of length 4 """
def lift(self, elt): r""" Lift the element ``elt`` inside the ambient space from which ``self`` is a quotient.
EXAMPLES::
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: v = S.lift(S([4,3,0,1])); v [4, 3, 0, 1] sage: type(v) <... 'list'> """ # TODO: For now, Sage integer vectors are just python list. # Once Integer vectors will have an element class, update this # code properly
def retract(self, elt): r""" Return the canonical representative of the orbit of the integer ``elt`` under the action of the permutation group defining ``self``.
If the element ``elt`` is already maximal in its orbit for the lexicographic order, ``elt`` is thus the good representative for its orbit.
EXAMPLES::
sage: [0,0,0,0] in IntegerVectors(0,4) True sage: [1,0,0,0] in IntegerVectors(1,4) True sage: [0,1,0,0] in IntegerVectors(1,4) True sage: [1,0,1,0] in IntegerVectors(2,4) True sage: [0,1,0,1] in IntegerVectors(2,4) True sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: S.retract([0,0,0,0]) [0, 0, 0, 0] sage: S.retract([1,0,0,0]) [1, 0, 0, 0] sage: S.retract([0,1,0,0]) [1, 0, 0, 0] sage: S.retract([1,0,1,0]) [1, 0, 1, 0] sage: S.retract([0,1,0,1]) [1, 0, 1, 0] """ # TODO: Once Sage integer vector will have a data structure # based on ClonableIntArray, remove the conversion intarray
def roots(self): r""" Returns the root of generation of ``self``. This method is required to build the tree structure of ``self`` which inherits from the class :class:`~sage.combinat.backtrack.SearchForest`.
EXAMPLES::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: I.roots() [[0, 0, 0, 0]] """
def children(self, x): r""" Returns the list of children of the element ``x``. This method is required to build the tree structure of ``self`` which inherits from the class :class:`~sage.combinat.backtrack.SearchForest`.
EXAMPLES::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: I.children(I([2,1,0,0], check=False)) [[2, 2, 0, 0], [2, 1, 1, 0], [2, 1, 0, 1]] """
def permutation_group(self): r""" Returns the permutation group given to define ``self``.
EXAMPLES::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: I.permutation_group() Permutation Group with generators [(1,2,3,4)] """
def is_canonical(self, v, check=True): r""" Returns ``True`` if the integer list ``v`` is maximal in its orbit under the action of the permutation group given to define ``self``. Such integer vectors are said to be canonical. A vector `v` is canonical if and only if
.. MATH::
v = \max_{\text{lex order}} \{g \cdot v | g \in G \}
EXAMPLES::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: I.is_canonical([4,3,2,1]) True sage: I.is_canonical([4,0,0,1]) True sage: I.is_canonical([4,0,3,3]) True sage: I.is_canonical([4,0,4,4]) False """
def __contains__(self, v): """ EXAMPLES::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: [2,2,0,0] in I True sage: [2,0,1,0] in I True sage: [2,0,0,1] in I True sage: [2,0,0,2] in I False sage: [2,0,0,2,12] in I False """
def __call__(self, v, check=True): r""" Returns an element of ``self`` constructed from ``v`` if possible.
TESTS::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: I([3,2,1,0]) [3, 2, 1, 0] """ else: raise ValueError('%s should be a Python list of integer'%(v))
def orbit(self, v): r""" Returns the orbit of the integer vector ``v`` under the action of the permutation group defining ``self``. The result is a set.
EXAMPLES:
In order to get reproducible doctests, we convert the returned sets into lists in increasing lexicographic order::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: sorted(I.orbit([2,2,0,0])) [[0, 0, 2, 2], [0, 2, 2, 0], [2, 0, 0, 2], [2, 2, 0, 0]] sage: sorted(I.orbit([2,1,0,0])) [[0, 0, 2, 1], [0, 2, 1, 0], [1, 0, 0, 2], [2, 1, 0, 0]] sage: sorted(I.orbit([2,0,1,0])) [[0, 1, 0, 2], [0, 2, 0, 1], [1, 0, 2, 0], [2, 0, 1, 0]] sage: sorted(I.orbit([2,0,2,0])) [[0, 2, 0, 2], [2, 0, 2, 0]] sage: I.orbit([1,1,1,1]) {[1, 1, 1, 1]} """ return orbit(self._sgs, v) raise TypeError
def subset(self, sum=None, max_part=None): r""" Returns the subset of ``self`` containing integer vectors whose entries sum to ``sum``.
EXAMPLES::
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: S.subset(4) Integer vectors of length 4 and of sum 4 enumerated up to the action of Permutation Group with generators [(1,2,3,4)] """
class Element(ClonableIntArray): r""" Element class for the set of integer vectors of given sum enumerated modulo the action of a permutation group. These vector are clonable lists of integers which must check conditions comming form the parent appearing in the method :meth:`~sage.structure.list_clone.ClonableIntArray.check`.
TESTS::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: v = I.element_class(I, [4,3,2,1]); v [4, 3, 2, 1] sage: TestSuite(v).run() sage: I.element_class(I, [4,3,2,5]) Traceback (most recent call last): ... AssertionError """ def check(self): r""" Checks that ``self`` verify the invariants needed for living in ``self.parent()``.
EXAMPLES::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: v = I.an_element() sage: v.check() sage: w = I([0,4,0,0], check=False); w [0, 4, 0, 0] sage: w.check() Traceback (most recent call last): ... AssertionError """
class IntegerVectorsModPermutationGroup_with_constraints(UniqueRepresentation, SearchForest): r""" This class models finite enumerated sets of integer vectors with constraint enumerated up to the action of a permutation group. Integer vectors are enumerated modulo the action of the permutation group. To implement that, we keep a single integer vector by orbit under the action of the permutation group. Elements chosen are vectors maximal in their orbit for the lexicographic order.
For more information see :class:`IntegerVectorsModPermutationGroup`.
EXAMPLES::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), max_part=1) sage: I.list() [[0, 0, 0, 0], [1, 0, 0, 0], [1, 1, 0, 0], [1, 0, 1, 0], [1, 1, 1, 0], [1, 1, 1, 1]] sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), sum=6, max_part=4) sage: I.list() [[4, 2, 0, 0], [4, 1, 1, 0], [4, 1, 0, 1], [4, 0, 2, 0], [4, 0, 1, 1], [4, 0, 0, 2], [3, 3, 0, 0], [3, 2, 1, 0], [3, 2, 0, 1], [3, 1, 2, 0], [3, 1, 1, 1], [3, 1, 0, 2], [3, 0, 3, 0], [3, 0, 2, 1], [3, 0, 1, 2], [2, 2, 2, 0], [2, 2, 1, 1], [2, 1, 2, 1]]
Here is the enumeration of unlabeled graphs over 5 vertices::
sage: G = IntegerVectorsModPermutationGroup(TransitiveGroup(10,12), max_part=1) # optional - database_gap sage: G.cardinality() # optional - database_gap 34
TESTS::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]),4) sage: TestSuite(I).run() """ def __init__(self, G, d, max_part, sgs=None): r""" TESTS::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), 6, max_part=4) """ else:
# self.sgs: strong_generating_system else: self._sgs = [list(x) for x in list(sgs)]
def _repr_(self): r""" TESTS::
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])); S Integer vectors of length 4 enumerated up to the action of Permutation Group with generators [(1,2,3,4)] sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), 6); S Integer vectors of length 4 and of sum 6 enumerated up to the action of Permutation Group with generators [(1,2,3,4)] sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), 6, max_part=4); S Vectors of length 4 and of sum 6 whose entries is in {0, ..., 4} enumerated up to the action of Permutation Group with generators [(1,2,3,4)] sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), max_part=4); S Integer vectors of length 4 whose entries is in {0, ..., 4} enumerated up to the action of Permutation Group with generators [(1,2,3,4)] """ else: else:
def roots(self): r""" Returns the root of generation of ``self``.This method is required to build the tree structure of ``self`` which inherits from the class :class:`~sage.combinat.backtrack.SearchForest`.
EXAMPLES::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: I.roots() [[0, 0, 0, 0]] """
def children(self, x): r""" Returns the list of children of the element ``x``. This method is required to build the tree structure of ``self`` which inherits from the class :class:`~sage.combinat.backtrack.SearchForest`.
EXAMPLES::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]])) sage: I.children(I([2,1,0,0], check=False)) [[2, 2, 0, 0], [2, 1, 1, 0], [2, 1, 0, 1]] """
def permutation_group(self): r""" Returns the permutation group given to define ``self``.
EXAMPLES::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3)]]), 5) sage: I.permutation_group() Permutation Group with generators [(1,2,3)] """
def __contains__(self, v): r""" TESTS::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]),6) sage: [6,0,0,0] in I True sage: [5,0,1,0] in I True sage: [0,5,1,0] in I False sage: [3,0,1,3] in I False sage: [3,3,1,0] in I False """
def __call__(self, v, check=True): r""" Make `v` an element living in ``self``.
TESTS::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), 4) sage: v = I([2,1,0,1]); v [2, 1, 0, 1] sage: v.parent() Integer vectors of length 4 and of sum 4 enumerated up to the action of Permutation Group with generators [(1,2,3,4)] """ else: raise ValueError('%s should be a Python list of integer'%(v))
def __iter__(self): r""" TESTS::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]),4) sage: for i in I: i [4, 0, 0, 0] [3, 1, 0, 0] [3, 0, 1, 0] [3, 0, 0, 1] [2, 2, 0, 0] [2, 1, 1, 0] [2, 1, 0, 1] [2, 0, 2, 0] [2, 0, 1, 1] [1, 1, 1, 1] sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), sum=7, max_part=3) sage: for i in I: i [3, 3, 1, 0] [3, 3, 0, 1] [3, 2, 2, 0] [3, 2, 1, 1] [3, 2, 0, 2] [3, 1, 3, 0] [3, 1, 2, 1] [3, 1, 1, 2] [3, 0, 2, 2] [2, 2, 2, 1] """ else: lambda x : [self(y, check=False) for y in canonical_children(self._sgs, x, self._max_part)], algorithm = 'breadth') else:
def is_canonical(self, v, check=True): r""" Returns ``True`` if the integer list ``v`` is maximal in its orbit under the action of the permutation group given to define ``self``. Such integer vectors are said to be canonical. A vector `v` is canonical if and only if
.. MATH::
v = \max_{\text{lex order}} \{g \cdot v | g \in G \}
EXAMPLES::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), max_part=3) sage: I.is_canonical([3,0,0,0]) True sage: I.is_canonical([1,0,2,0]) False sage: I.is_canonical([2,0,1,0]) True """
def ambient(self): r""" Return the ambient space from which ``self`` is a quotient.
EXAMPLES::
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), 6); S.ambient() Integer vectors that sum to 6 sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), 6, max_part=12); S.ambient() Integer vectors that sum to 6 with constraints: max_part=12 sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), max_part=12); S.ambient() Integer vectors with constraints: max_part=12 """ else: else:
def lift(self, elt): r""" Lift the element ``elt`` inside the ambient space from which ``self`` is a quotient.
EXAMPLES::
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), max_part=1) sage: v = S.lift([1,0,1,0]); v [1, 0, 1, 0] sage: v in IntegerVectors(2,4,max_part=1) True sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), sum=6) sage: v = S.lift(S.list()[5]); v [4, 1, 1, 0] sage: v in IntegerVectors(n=6) True """ # TODO: For now, Sage integer vectors are just python list. # Once Integer vectors will have an element class, update this # code properly
def retract(self, elt): r""" Return the canonical representative of the orbit of the integer ``elt`` under the action of the permutation group defining ``self``.
If the element ``elt`` is already maximal in its orbits for the lexicographic order, ``elt`` is thus the good representative for its orbit.
EXAMPLES::
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), sum=2, max_part=1) sage: S.retract([1,1,0,0]) [1, 1, 0, 0] sage: S.retract([1,0,1,0]) [1, 0, 1, 0] sage: S.retract([1,0,0,1]) [1, 1, 0, 0] sage: S.retract([0,1,1,0]) [1, 1, 0, 0] sage: S.retract([0,1,0,1]) [1, 0, 1, 0] sage: S.retract([0,0,1,1]) [1, 1, 0, 0] """ # TODO: Once Sage integer vector will have a data structure # based on ClonableIntArray, remove the conversion intarray
def an_element(self): r""" Returns an element of ``self`` or raises an EmptySetError when ``self`` is empty.
EXAMPLES::
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), sum=0, max_part=1); S.an_element() [0, 0, 0, 0] sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), sum=1, max_part=1); S.an_element() [1, 0, 0, 0] sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), sum=2, max_part=1); S.an_element() [1, 1, 0, 0] sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), sum=3, max_part=1); S.an_element() [1, 1, 1, 0] sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), sum=4, max_part=1); S.an_element() [1, 1, 1, 1] sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), sum=5, max_part=1); S.an_element() Traceback (most recent call last): ... EmptySetError """ else:
def orbit(self, v): r""" Returns the orbit of the vector ``v`` under the action of the permutation group defining ``self``. The result is a set.
INPUT:
- ``v`` - an element of ``self`` or any list of length the degree of the permutation group.
EXAMPLES:
We convert the result in a list in increasing lexicographic order, to get a reproducible doctest::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]),4) sage: I.orbit([1,1,1,1]) {[1, 1, 1, 1]} sage: sorted(I.orbit([3,0,0,1])) [[0, 0, 1, 3], [0, 1, 3, 0], [1, 3, 0, 0], [3, 0, 0, 1]] """ return orbit(self._sgs, v)
class Element(ClonableIntArray): r""" Element class for the set of integer vectors with constraints enumerated modulo the action of a permutation group. These vectors are clonable lists of integers which must check conditions comming form the parent as in the method :meth:`~sage.combinat.integer_vectors_mod_permgroup.IntegerVectorsModPermutationGroup_with_constraints.Element.check`.
TESTS::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), 4) sage: v = I.element_class(I, [3,1,0,0]); v [3, 1, 0, 0] sage: TestSuite(v).run() sage: v = I.element_class(I, [3,2,0,0]) Traceback (most recent call last): ... AssertionError: [3, 2, 0, 0] should be a integer vector of sum 4 """ def check(self): r""" Checks that ``self`` meets the constraints of being an element of ``self.parent()``.
EXAMPLES::
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), 4) sage: v = I.an_element() sage: v.check() sage: w = I([0,4,0,0], check=False); w [0, 4, 0, 0] sage: w.check() Traceback (most recent call last): ... AssertionError """ assert max(self) <= self.parent()._max_part, 'Entries of %s must be inferiors to %s'%(self, self.parent()._max_part) |