Tools for enumeration modulo the action of a permutation group¶
-
sage.combinat.enumeration_mod_permgroup.
all_children
(v, max_part)¶ Returns all the children of an integer vector (
ClonableIntArray
)v
in the tree of enumeration by lexicographic order. The children of an integer vectorv
whose entries have the sumare 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]]
-
sage.combinat.enumeration_mod_permgroup.
canonical_children
(sgs, v, max_part)¶ Returns the canonical children of the integer vector
v
. This function computes all children of the integer vectorv
via the functionall_children()
and returns from this list only these which are canonicals identified via the functionis_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) []
-
sage.combinat.enumeration_mod_permgroup.
canonical_representative_of_orbit_of
(sgs, v)¶ 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 vectoris 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]
-
sage.combinat.enumeration_mod_permgroup.
is_canonical
(sgs, v)¶ Returns
True
if the integer vectoris 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 vectoris 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
-
sage.combinat.enumeration_mod_permgroup.
lex_cmp
(v1, v2)¶ Lexicographic comparison of
ClonableIntArray
.INPUT:
Two instances
of
ClonableIntArray
OUPUT:
-1,0,1
, depending on whetheris 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
-
sage.combinat.enumeration_mod_permgroup.
lex_cmp_partial
(v1, v2, step)¶ 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
-
sage.combinat.enumeration_mod_permgroup.
orbit
(sgs, v)¶ Returns the orbit of the integer vector
v
under the action of the permutation group whose strong generating system issgs
.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]]