Integer vectors modulo the action of a permutation group¶
-
sage.combinat.integer_vectors_mod_permgroup.
IntegerVectorsModPermutationGroup
¶ 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
\[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 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 groupsum
- (default: None) - a nonnegative integermax_part
- (default: None) - a nonnegative integer setting the maximum of entries of elementssgs
- (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
andmax_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 tosum
.
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
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 tosum
.: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
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]}
-
sage.combinat.integer_vectors_mod_permgroup.
IntegerVectorsModPermutationGroup_All
¶ 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]
-
sage.combinat.integer_vectors_mod_permgroup.
IntegerVectorsModPermutationGroup_with_constraints
¶ 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]]
Here is the enumeration of unlabeled graphs over 5 vertices:
sage: G = IntegerVectorsModPermutationGroup(TransitiveGroup(10,12), max_part=1) sage: G.cardinality() 34