# Integer vectors modulo the action of a permutation group#

AUTHORS:

• Nicolas Borie (2010-2012) - original module

• Jukka Kohonen (2023) - fast cardinality method, Issue #36787, Issue #36681

class sage.combinat.integer_vectors_mod_permgroup.IntegerVectorsModPermutationGroup[source]#

Return 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

$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]$$

$s_1 \cdot v = [a_2, a_1, a_3, \dots , a_n]$

This function returns a parent which contains, from each orbit orbit under the action of the permutation group $$G$$, a single canonical vector. The canonical vector is the one that is maximal within the orbit according to lexicographic order.

INPUT:

• G – a permutation group

• sum – (default: None) - a nonnegative integer

• max_part – (default: None) - a nonnegative integer setting the maximum value for every element

• 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 (lists of integers) maximal in their orbit for the lexicographic order. Exceptionally, if the domain of G is empty, the result is a finite enumerated set that contains one element, namely the empty vector.

• 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]

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3))]]))
>>> I.category()
Category of infinite enumerated quotients of sets
>>> I.cardinality()
+Infinity
>>> I.list()
Traceback (most recent call last):
...
NotImplementedError: cannot list an infinite set
>>> p = iter(I)
>>> for i in range(Integer(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 is_canonical() tests if an 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 an integer vector

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]))
>>> I.is_canonical([Integer(5),Integer(2),Integer(0),Integer(4)])
True
>>> I.is_canonical([Integer(5),Integer(0),Integer(6),Integer(4)])
False
>>> I.is_canonical([Integer(1),Integer(1),Integer(1),Integer(1)])
True
>>> [Integer(2),Integer(3),Integer(1),Integer(0)] in I
False
>>> [Integer(5),Integer(0),Integer(5),Integer(0)] in I
True
>>> 'Bla' in I
False
>>> I.is_canonical('bla')
Traceback (most recent call last):
...
AssertionError: bla should be a list or an 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

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3))]]), sum=Integer(6))
>>> I.cardinality()
10
>>> 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]]
>>> 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 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]}

>>> from sage.all import *
>>> sorted(I.orbit([Integer(6),Integer(0),Integer(0)]))
[[0, 0, 6], [0, 6, 0], [6, 0, 0]]
>>> sorted(I.orbit([Integer(5),Integer(1),Integer(0)]))
[[0, 5, 1], [1, 0, 5], [5, 1, 0]]
>>> I.orbit([Integer(2),Integer(2),Integer(2)])
{[2, 2, 2]}


Even without constraints, for an empty domain the result is a singleton set:

sage: G = PermutationGroup([], domain=[])
sage: sgs = tuple(tuple(s) for s in G.strong_generating_system())
sage: list(IntegerVectorsModPermutationGroup(G, sgs=sgs))
[[]]

>>> from sage.all import *
>>> G = PermutationGroup([], domain=[])
>>> sgs = tuple(tuple(s) for s in G.strong_generating_system())
>>> list(IntegerVectorsModPermutationGroup(G, sgs=sgs))
[[]]


Warning

Because of Issue #36527, permutation groups that have different domains but similar generators can be erroneously treated as the same group. This will silently produce erroneous results. To avoid this issue, compute a strong generating system for the group as:

sgs = tuple(tuple(s) for s in G.strong_generating_system())


and provide it as the optional sgs argument to the constructor.

class sage.combinat.integer_vectors_mod_permgroup.IntegerVectorsModPermutationGroup_All(G, sgs=None)[source]#

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)]])); 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]

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]])); I
Integer vectors of length 4 enumerated up to the action of
Permutation Group with generators [(1,2,3,4)]
>>> I.cardinality()
+Infinity
>>> TestSuite(I).run()
>>> it = iter(I)
>>> [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]]
>>> x = next(it); x
[3, 0, 0, 0]
>>> I.first()
[0, 0, 0, 0]

class Element[source]#

Element class for the set of integer vectors of given sum enumerated modulo the action of a permutation group. These vectors are clonable lists of integers which must satisfy conditions coming from the parent appearing in the method check().

check()[source]#

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

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]))
>>> v = I.an_element()
>>> v.check()
>>> w = I([Integer(0),Integer(4),Integer(0),Integer(0)], check=False); w
[0, 4, 0, 0]
>>> w.check()
Traceback (most recent call last):
...
AssertionError

ambient()[source]#

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

>>> from sage.all import *
>>> S = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]))
>>> S.ambient()
Integer vectors of length 4

children(x)[source]#

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 RecursivelyEnumeratedSet_forest.

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]]

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]))
>>> I.children(I([Integer(2),Integer(1),Integer(0),Integer(0)], check=False))
[[2, 2, 0, 0], [2, 1, 1, 0], [2, 1, 0, 1]]

is_canonical(v, check=True)[source]#

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

$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

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]))
>>> I.is_canonical([Integer(4),Integer(3),Integer(2),Integer(1)])
True
>>> I.is_canonical([Integer(4),Integer(0),Integer(0),Integer(1)])
True
>>> I.is_canonical([Integer(4),Integer(0),Integer(3),Integer(3)])
True
>>> I.is_canonical([Integer(4),Integer(0),Integer(4),Integer(4)])
False

lift(elt)[source]#

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)
<class 'list'>

>>> from sage.all import *
>>> S = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]))
>>> v = S.lift(S([Integer(4),Integer(3),Integer(0),Integer(1)])); v
[4, 3, 0, 1]
>>> type(v)
<class 'list'>

orbit(v)[source]#

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]}

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]))
>>> sorted(I.orbit([Integer(2),Integer(2),Integer(0),Integer(0)]))
[[0, 0, 2, 2], [0, 2, 2, 0], [2, 0, 0, 2], [2, 2, 0, 0]]
>>> sorted(I.orbit([Integer(2),Integer(1),Integer(0),Integer(0)]))
[[0, 0, 2, 1], [0, 2, 1, 0], [1, 0, 0, 2], [2, 1, 0, 0]]
>>> sorted(I.orbit([Integer(2),Integer(0),Integer(1),Integer(0)]))
[[0, 1, 0, 2], [0, 2, 0, 1], [1, 0, 2, 0], [2, 0, 1, 0]]
>>> sorted(I.orbit([Integer(2),Integer(0),Integer(2),Integer(0)]))
[[0, 2, 0, 2], [2, 0, 2, 0]]
>>> I.orbit([Integer(1),Integer(1),Integer(1),Integer(1)])
{[1, 1, 1, 1]}

permutation_group()[source]#

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)]

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]))
>>> I.permutation_group()
Permutation Group with generators [(1,2,3,4)]

retract(elt)[source]#

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]

>>> from sage.all import *
>>> [Integer(0),Integer(0),Integer(0),Integer(0)] in IntegerVectors(Integer(0),Integer(4))
True
>>> [Integer(1),Integer(0),Integer(0),Integer(0)] in IntegerVectors(Integer(1),Integer(4))
True
>>> [Integer(0),Integer(1),Integer(0),Integer(0)] in IntegerVectors(Integer(1),Integer(4))
True
>>> [Integer(1),Integer(0),Integer(1),Integer(0)] in IntegerVectors(Integer(2),Integer(4))
True
>>> [Integer(0),Integer(1),Integer(0),Integer(1)] in IntegerVectors(Integer(2),Integer(4))
True
>>> S = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]))
>>> S.retract([Integer(0),Integer(0),Integer(0),Integer(0)])
[0, 0, 0, 0]
>>> S.retract([Integer(1),Integer(0),Integer(0),Integer(0)])
[1, 0, 0, 0]
>>> S.retract([Integer(0),Integer(1),Integer(0),Integer(0)])
[1, 0, 0, 0]
>>> S.retract([Integer(1),Integer(0),Integer(1),Integer(0)])
[1, 0, 1, 0]
>>> S.retract([Integer(0),Integer(1),Integer(0),Integer(1)])
[1, 0, 1, 0]

roots()[source]#

Returns the root of generation of self. This method is required to build the tree structure of self which inherits from the class RecursivelyEnumeratedSet_forest.

EXAMPLES:

sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]))
sage: I.roots()
[[0, 0, 0, 0]]

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]))
>>> I.roots()
[[0, 0, 0, 0]]

subset(sum=None, max_part=None)[source]#

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)]

>>> from sage.all import *
>>> S = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]))
>>> S.subset(Integer(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 sage.combinat.integer_vectors_mod_permgroup.IntegerVectorsModPermutationGroup_with_constraints(G, d, max_part, sgs=None)[source]#

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 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]]

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]),
...                                       max_part=Integer(1))
>>> 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]]
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]),
...                                       sum=Integer(6), max_part=Integer(4))
>>> 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)
sage: G.cardinality()
34

>>> from sage.all import *
>>> G = IntegerVectorsModPermutationGroup(TransitiveGroup(Integer(10),Integer(12)), max_part=Integer(1))
>>> G.cardinality()
34

class Element[source]#

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 satisfy conditions coming from the parent as in the method check().

check()[source]#

Check 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

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]), Integer(4))
>>> v = I.an_element()
>>> v.check()
>>> w = I([Integer(0),Integer(4),Integer(0),Integer(0)], check=False); w
[0, 4, 0, 0]
>>> w.check()
Traceback (most recent call last):
...
AssertionError

ambient()[source]#

Return the ambient space from which self is a quotient.

EXAMPLES:

sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), 6)
sage: S.ambient()
Integer vectors that sum to 6
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]),
....:                                       6, max_part=12)
sage: S.ambient()
Integer vectors that sum to 6 with constraints: max_part=12
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]),
....:                                       max_part=12)
sage: S.ambient()
Integer vectors with constraints: max_part=12

>>> from sage.all import *
>>> S = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]), Integer(6))
>>> S.ambient()
Integer vectors that sum to 6
>>> S = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]),
...                                       Integer(6), max_part=Integer(12))
>>> S.ambient()
Integer vectors that sum to 6 with constraints: max_part=12
>>> S = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]),
...                                       max_part=Integer(12))
>>> S.ambient()
Integer vectors with constraints: max_part=12

an_element()[source]#

Return an element of self.

Raises an EmptySetError when self is empty.

EXAMPLES:

sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]),
....:                                       sum=0, max_part=1)
sage: S.an_element()
[0, 0, 0, 0]
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]),
....:                                       sum=1, max_part=1)
sage: S.an_element()
[1, 0, 0, 0]
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]),
....:                                       sum=2, max_part=1)
sage: S.an_element()
[1, 1, 0, 0]
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]),
....:                                       sum=3, max_part=1)
sage: S.an_element()
[1, 1, 1, 0]
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]),
....:                                       sum=4, max_part=1)
sage: S.an_element()
[1, 1, 1, 1]
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]),
....:                                       sum=5, max_part=1)
sage: S.an_element()
Traceback (most recent call last):
...
EmptySetError

>>> from sage.all import *
>>> S = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]),
...                                       sum=Integer(0), max_part=Integer(1))
>>> S.an_element()
[0, 0, 0, 0]
>>> S = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]),
...                                       sum=Integer(1), max_part=Integer(1))
>>> S.an_element()
[1, 0, 0, 0]
>>> S = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]),
...                                       sum=Integer(2), max_part=Integer(1))
>>> S.an_element()
[1, 1, 0, 0]
>>> S = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]),
...                                       sum=Integer(3), max_part=Integer(1))
>>> S.an_element()
[1, 1, 1, 0]
>>> S = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]),
...                                       sum=Integer(4), max_part=Integer(1))
>>> S.an_element()
[1, 1, 1, 1]
>>> S = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]),
...                                       sum=Integer(5), max_part=Integer(1))
>>> S.an_element()
Traceback (most recent call last):
...
EmptySetError

cardinality()[source]#

Return the number of integer vectors in the set.

The algorithm utilises Cycle Index Theorem, allowing for a faster than a plain enumeration computation.

EXAMPLES:

With a trivial group all vectors are canonical:

sage: G = PermutationGroup([], domain=[1,2,3])
sage: IntegerVectorsModPermutationGroup(G, 5).cardinality()
21
sage: IntegerVectors(5, 3).cardinality()
21

>>> from sage.all import *
>>> G = PermutationGroup([], domain=[Integer(1),Integer(2),Integer(3)])
>>> IntegerVectorsModPermutationGroup(G, Integer(5)).cardinality()
21
>>> IntegerVectors(Integer(5), Integer(3)).cardinality()
21


With two interchangeable elements, the smaller one ranges from zero to sum//2:

sage: G = PermutationGroup([(1,2)])
sage: IntegerVectorsModPermutationGroup(G, 1000).cardinality()
501

>>> from sage.all import *
>>> G = PermutationGroup([(Integer(1),Integer(2))])
>>> IntegerVectorsModPermutationGroup(G, Integer(1000)).cardinality()
501


Binary vectors up to full symmetry are first some ones and then some zeros:

sage: G = SymmetricGroup(10)
sage: I = IntegerVectorsModPermutationGroup(G, max_part=1)
sage: I.cardinality()
11

>>> from sage.all import *
>>> G = SymmetricGroup(Integer(10))
>>> I = IntegerVectorsModPermutationGroup(G, max_part=Integer(1))
>>> I.cardinality()
11


Binary vectors of constant weight, up to PGL(2,17), which is 3-transitive, but not 4-transitive:

sage: G=PGL(2,17)
sage: I = IntegerVectorsModPermutationGroup(G, sum=3, max_part=1)
sage: I.cardinality()
1
sage: I = IntegerVectorsModPermutationGroup(G, sum=4, max_part=1)
sage: I.cardinality()
3

>>> from sage.all import *
>>> G=PGL(Integer(2),Integer(17))
>>> I = IntegerVectorsModPermutationGroup(G, sum=Integer(3), max_part=Integer(1))
>>> I.cardinality()
1
>>> I = IntegerVectorsModPermutationGroup(G, sum=Integer(4), max_part=Integer(1))
>>> I.cardinality()
3

children(x)[source]#

Return the list of children of the element x.

This method is required to build the tree structure of self which inherits from the class RecursivelyEnumeratedSet_forest.

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]]

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]))
>>> I.children(I([Integer(2),Integer(1),Integer(0),Integer(0)], check=False))
[[2, 2, 0, 0], [2, 1, 1, 0], [2, 1, 0, 1]]

is_canonical(v, check=True)[source]#

Return 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

$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

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]),
...                                       max_part=Integer(3))
>>> I.is_canonical([Integer(3),Integer(0),Integer(0),Integer(0)])
True
>>> I.is_canonical([Integer(1),Integer(0),Integer(2),Integer(0)])
False
>>> I.is_canonical([Integer(2),Integer(0),Integer(1),Integer(0)])
True

lift(elt)[source]#

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

>>> from sage.all import *
>>> S = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]),
...                                       max_part=Integer(1))
>>> v = S.lift([Integer(1),Integer(0),Integer(1),Integer(0)]); v
[1, 0, 1, 0]
>>> v in IntegerVectors(Integer(2),Integer(4),max_part=Integer(1))
True
>>> S = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]),
...                                       sum=Integer(6))
>>> v = S.lift(S.list()[Integer(5)]); v
[4, 1, 1, 0]
>>> v in IntegerVectors(n=Integer(6))
True

orbit(v)[source]#

Return 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]]

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]), Integer(4))
>>> I.orbit([Integer(1),Integer(1),Integer(1),Integer(1)])
{[1, 1, 1, 1]}
>>> sorted(I.orbit([Integer(3),Integer(0),Integer(0),Integer(1)]))
[[0, 0, 1, 3], [0, 1, 3, 0], [1, 3, 0, 0], [3, 0, 0, 1]]

permutation_group()[source]#

Return 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)]

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3))]]), Integer(5))
>>> I.permutation_group()
Permutation Group with generators [(1,2,3)]

retract(elt)[source]#

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]

>>> from sage.all import *
>>> S = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]),
...                                       sum=Integer(2), max_part=Integer(1))
>>> S.retract([Integer(1),Integer(1),Integer(0),Integer(0)])
[1, 1, 0, 0]
>>> S.retract([Integer(1),Integer(0),Integer(1),Integer(0)])
[1, 0, 1, 0]
>>> S.retract([Integer(1),Integer(0),Integer(0),Integer(1)])
[1, 1, 0, 0]
>>> S.retract([Integer(0),Integer(1),Integer(1),Integer(0)])
[1, 1, 0, 0]
>>> S.retract([Integer(0),Integer(1),Integer(0),Integer(1)])
[1, 0, 1, 0]
>>> S.retract([Integer(0),Integer(0),Integer(1),Integer(1)])
[1, 1, 0, 0]

roots()[source]#

Return the root of generation of self.

This method is required to build the tree structure of self which inherits from the class RecursivelyEnumeratedSet_forest.

EXAMPLES:

sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]))
sage: I.roots()
[[0, 0, 0, 0]]

>>> from sage.all import *
>>> I = IntegerVectorsModPermutationGroup(PermutationGroup([[(Integer(1),Integer(2),Integer(3),Integer(4))]]))
>>> I.roots()
[[0, 0, 0, 0]]