Bases: sage.structure.unique_representation.UniqueRepresentation
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 is viewed as a subgroup of the
symmetric group
of degree
and
is said to be the degree
of
. Any integer vector
is said to be canonical if it
is maximal in its orbit under the action of
.
is
canonical if and only if
The action of is on position. This means for example that the
simple transposition
swaps the first and the second entries
of any integer vector
This functions returns a parent which contains a single integer
vector by orbit under the action of the permutation group . 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
.
INPUT:
OUTPUT:
EXAMPLES:
Here is the set enumerating integer vectors modulo the action of the cyclic
group of elements:
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3)]]))
sage: I.category()
Join of Category of infinite enumerated sets and Category of quotients of sets
sage: I.cardinality()
+Infinity
sage: I.list()
Traceback (most recent call last):
...
NotImplementedError: infinite list
sage: p = iter(I)
sage: for i in range(10): p.next()
[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 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 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]}
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(p.next())
... assert sorted(v, reverse=True) == v
We now check that there is as much of canonical vectors under the
symmetric group whose entries sum to
than partitions of
of at most
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 , all integer vectors of
length
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
Bases: sage.structure.unique_representation.UniqueRepresentation, sage.combinat.backtrack.SearchForest
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 for a certain
. This group has a natural action by
position on vectors of length
. 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: [it.next(), it.next(), it.next(), it.next(), it.next()]
[[0, 0, 0, 0],
[1, 0, 0, 0],
[2, 0, 0, 0],
[1, 1, 0, 0],
[1, 0, 1, 0]]
sage: x = it.next(); x
[3, 0, 0, 0]
sage: I.first()
[0, 0, 0, 0]
TESTS:
sage: TestSuite(I).run()
Bases: sage.structure.list_clone.ClonableIntArray
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 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
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
Return the ambient space from which self is a quotient.
EXAMPLES:
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]))
sage: S.ambient()
Integer vectors
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 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]]
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 is canonical if and only if
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
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)
<type 'list'>
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]}
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)]
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(length=4)
True
sage: [1,0,0,0] in IntegerVectors(length=4)
True
sage: [0,1,0,0] in IntegerVectors(length=4)
True
sage: [1,0,1,0] in IntegerVectors(length=4)
True
sage: [0,1,0,1] in IntegerVectors(length=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]
Returns the root of generation of self. This method is required to build the tree structure of self which inherits from the class SearchForest.
EXAMPLES:
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]))
sage: I.roots()
[[0, 0, 0, 0]]
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)]
Bases: sage.structure.unique_representation.UniqueRepresentation, sage.combinat.backtrack.SearchForest
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) # optional
sage: G.cardinality() # optional
34
TESTS:
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]),4)
sage: TestSuite(I).run()
Bases: sage.structure.list_clone.ClonableIntArray
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 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
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
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
Todo
Integer vectors should accept max_part as a single argument, and the following should change:
sage: S = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]), max_part=12); S.ambient()
Integer vectors
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
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 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]]
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 is canonical if and only if
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
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(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
Returns the orbit of the vector v under the action of the permutation group defining self. The result is a set.
INPUT:
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]]
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)]
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]
Returns the root of generation of self.This method is required to build the tree structure of self which inherits from the class SearchForest.
EXAMPLES:
sage: I = IntegerVectorsModPermutationGroup(PermutationGroup([[(1,2,3,4)]]))
sage: I.roots()
[[0, 0, 0, 0]]