Tools for enumeration modulo the action of a permutation group
Returns all the children of an integer vector (ClonableIntArray)
v in the tree of enumeration by lexicographic order. The children of
an integer vector v whose entries have the sum are all integer
vectors of sum
which follow v in the lexicographic order.
That means this function adds on the last non zero entries and the
following ones. For an integer vector
such that
then, the list of children is
EXAMPLES:
sage: from sage.combinat.enumeration_mod_permgroup import all_children
sage: from sage.structure.list_clone_demo import IncreasingIntArrays
sage: v = IncreasingIntArrays()([1,2,3,4])
sage: all_children(v, -1)
[[1, 2, 3, 5]]
Returns the canonical children of the integer vector v. This function computes all children of the integer vector v via the function all_children() and returns from this list only these which are canonicals identified via the function is_canonical().
EXAMPLES:
sage: from sage.combinat.enumeration_mod_permgroup import canonical_children
sage: G = PermutationGroup([[(1,2,3,4)]])
sage: sgs = G.strong_generating_system()
sage: from sage.structure.list_clone_demo import IncreasingIntArrays
sage: IA = IncreasingIntArrays()
sage: canonical_children(sgs, IA([1,2,3,5]), -1)
[]
Returns the maximal vector for the lexicographic order living in
the orbit of under the action of the permutation group whose
strong generating system is sgs. The maximal vector is also
called “canonical”. Hence, this method returns the canonical
vector inside the orbit of
. If
is already canonical,
the method returns
.
Let to be the permutation group which admits sgs as a strong
generating system. An integer vector
is said to be
canonical under the action of
if and only if:
EXAMPLES:
sage: from sage.combinat.enumeration_mod_permgroup import canonical_representative_of_orbit_of
sage: G = PermutationGroup([[(1,2,3,4)]])
sage: sgs = G.strong_generating_system()
sage: from sage.structure.list_clone_demo import IncreasingIntArrays
sage: IA = IncreasingIntArrays()
sage: canonical_representative_of_orbit_of(sgs, IA([1,2,3,5]))
[5, 1, 2, 3]
Returns True if the integer vector is maximal with respect to
the lexicographic order in its orbit under the action of the
permutation group whose strong generating system is sgs. Such
vectors are said to be canonical.
Let to be the permutation group which admit sgs as a strong
generating system. An integer vector
is said to be
canonical under the action of
if and only if:
EXAMPLES:
sage: from sage.combinat.enumeration_mod_permgroup import is_canonical
sage: G = PermutationGroup([[(1,2,3,4)]])
sage: sgs = G.strong_generating_system()
sage: from sage.structure.list_clone_demo import IncreasingIntArrays
sage: IA = IncreasingIntArrays()
sage: is_canonical(sgs, IA([1,2,3,6]))
False
Lexicographic comparison of ClonableIntArray.
INPUT:
Two instances of ClonableIntArray
OUPUT:
-1,0,1, depending on whether is lexicographically smaller, equal, or
greater than
.
EXAMPLES:
sage: I = IntegerVectorsModPermutationGroup(SymmetricGroup(5),5)
sage: I = IntegerVectorsModPermutationGroup(SymmetricGroup(5))
sage: J = IntegerVectorsModPermutationGroup(SymmetricGroup(6))
sage: v1 = I([2,3,1,2,3], check=False)
sage: v2 = I([2,3,2,3,2], check=False)
sage: v3 = J([2,3,1,2,3,1], check=False)
sage: from sage.combinat.enumeration_mod_permgroup import lex_cmp
sage: lex_cmp(v1, v1)
0
sage: lex_cmp(v1, v2)
-1
sage: lex_cmp(v2, v1)
1
sage: lex_cmp(v1, v3)
-1
sage: lex_cmp(v3, v1)
1
Partial comparison of the two lists according the lexicographic order. It compares the step-th first entries.
EXAMPLES:
sage: from sage.combinat.enumeration_mod_permgroup import lex_cmp_partial
sage: from sage.structure.list_clone_demo import IncreasingIntArrays
sage: IA = IncreasingIntArrays()
sage: lex_cmp_partial(IA([0,1,2,3]),IA([0,1,2,4]),3)
0
sage: lex_cmp_partial(IA([0,1,2,3]),IA([0,1,2,4]),4)
-1
Returns the orbit of the integer vector v under the action of the permutation group whose strong generating system is sgs.
NOTE:
The returned orbit is a set. In the doctests, we convert it into a sorted list.
EXAMPLES:
sage: from sage.combinat.enumeration_mod_permgroup import orbit
sage: G = PermutationGroup([[(1,2,3,4)]])
sage: sgs = G.strong_generating_system()
sage: from sage.structure.list_clone_demo import IncreasingIntArrays
sage: IA = IncreasingIntArrays()
sage: sorted(orbit(sgs, IA([1,2,3,4])))
[[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]]