Permutation Groups¶

class
diofant.combinatorics.perm_groups.
PermutationGroup
[source]¶ The class defining a Permutation group.
PermutationGroup([p1, p2, …, pn]) returns the permutation group generated by the list of permutations. This group can be supplied to Polyhedron if one desires to decorate the elements to which the indices of the permutation refer.
Examples
>>> Permutation.print_cyclic = True
The permutations corresponding to motion of the front, right and bottom face of a 2x2 Rubik’s cube are defined:
>>> F = Permutation(2, 19, 21, 8)(3, 17, 20, 10)(4, 6, 7, 5) >>> R = Permutation(1, 5, 21, 14)(3, 7, 23, 12)(8, 10, 11, 9) >>> D = Permutation(6, 18, 14, 10)(7, 19, 15, 11)(20, 22, 23, 21)
These are passed as permutations to PermutationGroup:
>>> G = PermutationGroup(F, R, D) >>> G.order() 3674160
The group can be supplied to a Polyhedron in order to track the objects being moved. An example involving the 2x2 Rubik’s cube is given there, but here is a simple demonstration:
>>> a = Permutation(2, 1) >>> b = Permutation(1, 0) >>> G = PermutationGroup(a, b) >>> P = Polyhedron(list('ABC'), pgroup=G) >>> P.corners (A, B, C) >>> P.rotate(0) # apply permutation 0 >>> P.corners (A, C, B) >>> P.reset() >>> P.corners (A, B, C)
Or one can make a permutation as a product of selected permutations and apply them to an iterable directly:
>>> P10 = G.make_perm([0, 1]) >>> P10('ABC') ['C', 'A', 'B']
See also
diofant.combinatorics.polyhedron.Polyhedron
,diofant.combinatorics.permutations.Permutation
References
[1] Holt, D., Eick, B., O’Brien, E. “Handbook of Computational Group Theory”
[2] Seress, A. “Permutation Group Algorithms”
[3] https://en.wikipedia.org/wiki/Schreier_vector
[4] https://en.wikipedia.org/wiki/Nielsen_transformation #Product_replacement_algorithm
[5] Frank Celler, Charles R.LeedhamGreen, Scott H.Murray, Alice C.Niemeyer, and E.A.O’Brien. “Generating Random Elements of a Finite Group”
[6] https://en.wikipedia.org/wiki/Block_%28permutation_group_theory%29
[7] https://web.archive.org/web/20170105021515/http://www.algorithmist.com:80/index.php/Union_Find
[8] https://en.wikipedia.org/wiki/Multiply_transitive_group#Multiply_transitive_groups
[9] https://en.wikipedia.org/wiki/Center_%28group_theory%29
[10] https://en.wikipedia.org/wiki/Centralizer_and_normalizer
[11] https://groupprops.subwiki.org/wiki/Derived_subgroup
[12] https://en.wikipedia.org/wiki/Nilpotent_group
[13] http://www.math.colostate.edu/~hulpke/CGT/cgtnotes.pdf

__contains__
(i)[source]¶ Return True if \(i\) is contained in PermutationGroup.
Examples
>>> p = Permutation(1, 2, 3) >>> Permutation(3) in PermutationGroup(p) True

__eq__
(other)[source]¶ Return True if PermutationGroup generated by elements in the group are same i.e they represent the same PermutationGroup.
Examples
>>> p = Permutation(0, 1, 2, 3, 4, 5) >>> G = PermutationGroup([p, p**2]) >>> H = PermutationGroup([p**2, p]) >>> G.generators == H.generators False >>> G == H True

__mul__
(other)[source]¶ Return the direct product of two permutation groups as a permutation group.
This implementation realizes the direct product by shifting the index set for the generators of the second group: so if we have G acting on n1 points and H acting on n2 points, G*H acts on n1 + n2 points.
Examples
>>> G = CyclicGroup(5) >>> H = G*G >>> H PermutationGroup([ Permutation(9)(0, 1, 2, 3, 4), Permutation(5, 6, 7, 8, 9)]) >>> H.order() 25

static
__new__
(cls, *args, **kwargs)[source]¶ The default constructor. Accepts Cycle and Permutation forms. Removes duplicates unless
dups
keyword is False.

_random_pr_init
(r, n, _random_prec_n=None)[source]¶ Initialize random generators for the product replacement algorithm.
The implementation uses a modification of the original product replacement algorithm due to LeedhamGreen, as described in [1], pp. 6971; also, see [2], pp. 2729 for a detailed theoretical analysis of the original product replacement algorithm, and [4].
The product replacement algorithm is used for producing random, uniformly distributed elements of a group
G
with a set of generatorsS
. For the initialization_random_pr_init
, a listR
of\max\{r, S\}
group generators is created as the attributeG._random_gens
, repeating elements ofS
if necessary, and the identity element ofG
is appended toR
 we shall refer to this last element as the accumulator. Then the functionrandom_pr()
is calledn
times, randomizing the listR
while preserving the generation ofG
byR
. The functionrandom_pr()
itself takes two random elementsg, h
among all elements ofR
but the accumulator and replacesg
with a randomly chosen element from\{gh, g(~h), hg, (~h)g\}
. Then the accumulator is multiplied by whateverg
was replaced by. The new value of the accumulator is then returned byrandom_pr()
.The elements returned will eventually (for
n
large enough) become uniformly distributed acrossG
([5]). For practical purposes however, the valuesn = 50, r = 11
are suggested in [1].Notes
THIS FUNCTION HAS SIDE EFFECTS: it changes the attribute self._random_gens
See also

_union_find_merge
(first, second, ranks, parents, not_rep)[source]¶ Merges two classes in a unionfind data structure.
Used in the implementation of Atkinson’s algorithm as suggested in [1], pp. 8387. The class merging process uses union by rank as an optimization. ([7])
Notes
THIS FUNCTION HAS SIDE EFFECTS: the list of class representatives,
parents
, the list of class sizes,ranks
, and the list of elements that are not representatives,not_rep
, are changed due to class merging.See also
References
[1] Holt, D., Eick, B., O’Brien, E. “Handbook of computational group theory”
[7] https://web.archive.org/web/20170105021515/http://www.algorithmist.com:80/index.php/Union_Find

_union_find_rep
(num, parents)[source]¶ Find representative of a class in a unionfind data structure.
Used in the implementation of Atkinson’s algorithm as suggested in [1], pp. 8387. After the representative of the class to which
num
belongs is found, path compression is performed as an optimization ([7]).Notes
THIS FUNCTION HAS SIDE EFFECTS: the list of class representatives,
parents
, is altered due to path compression.See also
References
[1] Holt, D., Eick, B., O’Brien, E. “Handbook of computational group theory”
[7] https://web.archive.org/web/20170105021515/http://www.algorithmist.com:80/index.php/Union_Find

base
¶ Return a base from the SchreierSims algorithm.
For a permutation group
G
, a base is a sequence of pointsB = (b_1, b_2, ..., b_k)
such that no element ofG
apart from the identity fixes all the points inB
. The concepts of a base and strong generating set and their applications are discussed in depth in [1], pp. 8789 and [2], pp. 5557.An alternative way to think of
B
is that it gives the indices of the stabilizer cosets that contain more than the identity permutation.Examples
>>> G = PermutationGroup([Permutation(0, 1, 3)(2, 4)]) >>> G.base [0, 2]
See also
strong_gens
,basic_transversals
,basic_orbits
,basic_stabilizers

baseswap
(base, strong_gens, pos, randomized=False, transversals=None, basic_orbits=None, strong_gens_distr=None)[source]¶ Swap two consecutive base points in base and strong generating set.
If a base for a group
G
is given by(b_1, b_2, ..., b_k)
, this function returns a base(b_1, b_2, ..., b_{i+1}, b_i, ..., b_k)
, wherei
is given bypos
, and a strong generating set relative to that base. The original base and strong generating set are not modified.The randomized version (default) is of Las Vegas type.
Parameters:  base, strong_gens – The base and strong generating set.
 pos – The position at which swapping is performed.
 randomized – A switch between randomized and deterministic version.
 transversals – The transversals for the basic orbits, if known.
 basic_orbits – The basic orbits, if known.
 strong_gens_distr – The strong generators distributed by basic stabilizers, if known.
Returns: (base, strong_gens) –
base
is the new base, andstrong_gens
is a generating set relative to it.Examples
>>> from diofant.combinatorics.testutil import _verify_bsgs >>> S = SymmetricGroup(4) >>> S.schreier_sims() >>> S.base [0, 1, 2] >>> base, gens = S.baseswap(S.base, S.strong_gens, 1, randomized=False) >>> base, gens ([0, 2, 1], [Permutation(0, 1, 2, 3), Permutation(3)(0, 1), Permutation(1, 3, 2), Permutation(2, 3), Permutation(1, 3)])
check that base, gens is a BSGS
>>> S1 = PermutationGroup(gens) >>> _verify_bsgs(S1, base, gens) True
See also
Notes
The deterministic version of the algorithm is discussed in [1], pp. 102103; the randomized version is discussed in [1], p.103, and [2], p.98. It is of Las Vegas type. Notice that [1] contains a mistake in the pseudocode and discussion of BASESWAP: on line 3 of the pseudocode,
\beta_{i+1}^{\left\langle T\right\rangle}
should be replaced by\beta_{i}^{\left\langle T\right\rangle}
, and the same for the discussion of the algorithm.

basic_orbits
¶ Return the basic orbits relative to a base and strong generating set.
If
(b_1, b_2, ..., b_k)
is a base for a groupG
, andG^{(i)} = G_{b_1, b_2, ..., b_{i1}}
is thei
th basic stabilizer (so thatG^{(1)} = G
), thei
th basic orbit relative to this base is the orbit ofb_i
underG^{(i)}
. See [1], pp. 8789 for more information.Examples
>>> S = SymmetricGroup(4) >>> S.basic_orbits [[0, 1, 2, 3], [1, 2, 3], [2, 3]]
See also

basic_stabilizers
¶ Return a chain of stabilizers relative to a base and strong generating set.
The
i
th basic stabilizerG^{(i)}
relative to a base(b_1, b_2, ..., b_k)
isG_{b_1, b_2, ..., b_{i1}}
. For more information, see [1], pp. 8789.Examples
>>> A = AlternatingGroup(4) >>> A.schreier_sims() >>> A.base [0, 1] >>> for g in A.basic_stabilizers: ... print(g) ... PermutationGroup([ Permutation(3)(0, 1, 2), Permutation(1, 2, 3)]) PermutationGroup([ Permutation(1, 2, 3)])
See also

basic_transversals
¶ Return basic transversals relative to a base and strong generating set.
The basic transversals are transversals of the basic orbits. They are provided as a list of dictionaries, each dictionary having keys  the elements of one of the basic orbits, and values  the corresponding transversal elements. See [1], pp. 8789 for more information.
Examples
>>> A = AlternatingGroup(4) >>> A.basic_transversals [{0: Permutation(3), 1: Permutation(3)(0, 1, 2), 2: Permutation(3)(0, 2, 1), 3: Permutation(0, 3, 1)}, {1: Permutation(3), 2: Permutation(1, 2, 3), 3: Permutation(1, 3, 2)}]
See also

center
()[source]¶ Return the center of a permutation group.
The center for a group
G
is defined asZ(G) = \{z\in G  \forall g\in G, zg = gz \}
, the set of elements ofG
that commute with all elements ofG
. It is equal to the centralizer ofG
insideG
, and is naturally a subgroup ofG
([9]).Examples
>>> D = DihedralGroup(4) >>> G = D.center() >>> G.order() 2
See also
Notes
This is a naive implementation that is a straightforward application of
.centralizer()

centralizer
(other)[source]¶ Return the centralizer of a group/set/element.
The centralizer of a set of permutations
S
inside a groupG
is the set of elements ofG
that commute with all elements ofS
:``C_G(S) = \{ g \in G  gs = sg \forall s \in S\}`` ([10])
Usually,
S
is a subset ofG
, but ifG
is a proper subgroup of the full symmetric group, we allow forS
to have elements outsideG
.It is naturally a subgroup of
G
; the centralizer of a permutation group is equal to the centralizer of any set of generators for that group, since any element commuting with the generators commutes with any product of the generators.Parameters: other – a permutation group/list of permutations/single permutation Examples
>>> S = SymmetricGroup(6) >>> C = CyclicGroup(6) >>> H = S.centralizer(C) >>> H.is_subgroup(C) True
See also
Notes
The implementation is an application of
.subgroup_search()
with tests using a specific base for the groupG
.

commutator
(G, H)[source]¶ Return the commutator of two subgroups.
For a permutation group
K
and subgroupsG
,H
, the commutator ofG
andH
is defined as the group generated by all the commutators[g, h] = hgh^{1}g^{1}
forg
inG
andh
inH
. It is naturally a subgroup ofK
([1], p.27).Examples
>>> S = SymmetricGroup(5) >>> A = AlternatingGroup(5) >>> G = S.commutator(S, A) >>> G.is_subgroup(A) True
See also
Notes
The commutator of two subgroups
H, G
is equal to the normal closure of the commutators of all the generators, i.e.hgh^{1}g^{1}
forh
a generator ofH
andg
a generator ofG
([1], p.28)

contains
(g, strict=True)[source]¶ Test if permutation
g
belong to self,G
.If
g
is an element ofG
it can be written as a product of factors drawn from the cosets ofG
’s stabilizers. To see ifg
is one of the actual generators defining the group useG.has(g)
.If
strict
is not True,g
will be resized, if necessary, to match the size of permutations inself
.Examples
>>> Permutation.print_cyclic = True
>>> a = Permutation(1, 2) >>> b = Permutation(2, 3, 1) >>> G = PermutationGroup(a, b, degree=5) >>> G.contains(G[0]) # trivial check True >>> elem = Permutation([[2, 3]], size=5) >>> G.contains(elem) True >>> G.contains(Permutation(4)(0, 1, 2, 3)) False
If strict is False, a permutation will be resized, if necessary:
>>> H = PermutationGroup(Permutation(5)) >>> H.contains(Permutation(3)) False >>> H.contains(Permutation(3), strict=False) True
To test if a given permutation is present in the group:
>>> elem in G.generators False >>> G.has(elem) False
See also

coset_factor
(g, factor_index=False)[source]¶ Return
G
’s (self’s) coset factorization ofg
If
g
is an element ofG
then it can be written as the product of permutations drawn from the SchreierSims coset decomposition,The permutations returned in
f
are those for which the product givesg
:g = f[n]*...f[1]*f[0]
wheren = len(B)
andB = G.base
. f[i] is one of the permutations inself._basic_orbits[i]
.If factor_index==True, returns a tuple
[b[0],..,b[n]]
, whereb[i]
belongs toself._basic_orbits[i]
Examples
>>> Permutation.print_cyclic = True >>> a = Permutation(0, 1, 3, 7, 6, 4)(2, 5) >>> b = Permutation(0, 1, 3, 2)(4, 5, 7, 6) >>> G = PermutationGroup([a, b])
Define g:
>>> g = Permutation(7)(1, 2, 4)(3, 6, 5)
Confirm that it is an element of G:
>>> G.contains(g) True
Thus, it can be written as a product of factors (up to 3) drawn from u. See below that a factor from u1 and u2 and the Identity permutation have been used:
>>> f = G.coset_factor(g) >>> f[2]*f[1]*f[0] == g True >>> f1 = G.coset_factor(g, True); f1 [0, 4, 4] >>> tr = G.basic_transversals >>> f[0] == tr[0][f1[0]] True
If g is not an element of G then [] is returned:
>>> c = Permutation(5, 6, 7) >>> G.coset_factor(c) []
see util._strip

coset_rank
(g)[source]¶ rank using SchreierSims representation
The coset rank of
g
is the ordering number in which it appears in the lexicographic listing according to the coset decompositionThe ordering is the same as in G.generate(method=’coset’). If
g
does not belong to the group it returns None.Examples
>>> Permutation.print_cyclic = True >>> a = Permutation(0, 1, 3, 7, 6, 4)(2, 5) >>> b = Permutation(0, 1, 3, 2)(4, 5, 7, 6) >>> G = PermutationGroup([a, b]) >>> c = Permutation(7)(2, 4)(3, 5) >>> G.coset_rank(c) 16 >>> G.coset_unrank(16) Permutation(7)(2, 4)(3, 5)
See also

coset_unrank
(rank, af=False)[source]¶ unrank using SchreierSims representation
coset_unrank is the inverse operation of coset_rank if 0 <= rank < order; otherwise it returns None.

degree
¶ Returns the size of the permutations in the group.
The number of permutations comprising the group is given by len(group); the number of permutations that can be generated by the group is given by group.order().
Examples
>>> Permutation.print_cyclic = True >>> a = Permutation([1, 0, 2]) >>> G = PermutationGroup([a]) >>> G.degree 3 >>> len(G) 1 >>> G.order() 2 >>> list(G.generate()) [Permutation(2), Permutation(2)(0, 1)]
See also

derived_series
()[source]¶ Return the derived series for the group.
The derived series for a group
G
is defined asG = G_0 > G_1 > G_2 > \ldots
whereG_i = [G_{i1}, G_{i1}]
, i.e.G_i
is the derived subgroup ofG_{i1}
, fori\in\mathbb{N}
. When we haveG_k = G_{k1}
for somek\in\mathbb{N}
, the series terminates.Returns:  A list of permutation groups containing the members of the derived
 series in the order
G = G_0, G_1, G_2, \ldots
.
Examples
>>> A = AlternatingGroup(5) >>> len(A.derived_series()) 1 >>> S = SymmetricGroup(4) >>> len(S.derived_series()) 4 >>> S.derived_series()[1].is_subgroup(AlternatingGroup(4)) True >>> S.derived_series()[2].is_subgroup(DihedralGroup(2)) True
See also

derived_subgroup
()[source]¶ Compute the derived subgroup.
The derived subgroup, or commutator subgroup is the subgroup generated by all commutators
[g, h] = hgh^{1}g^{1}
forg, h\in G
; it is equal to the normal closure of the set of commutators of the generators ([1], p.28, [11]).Examples
>>> Permutation.print_cyclic = True >>> a = Permutation([1, 0, 2, 4, 3]) >>> b = Permutation([0, 1, 3, 2, 4]) >>> G = PermutationGroup([a, b]) >>> C = G.derived_subgroup() >>> list(C.generate(af=True)) [[0, 1, 2, 3, 4], [0, 1, 3, 4, 2], [0, 1, 4, 2, 3]]
See also

elements
¶ Returns all the elements of the permutation group in a list
Examples

generate
(method='coset', af=False)[source]¶ Return iterator to generate the elements of the group
Iteration is done with one of these methods:
method='coset' using the SchreierSims coset representation method='dimino' using the Dimino method
If af = True it yields the array form of the permutations
Examples
>>> Permutation.print_cyclic = True
The permutation group given in the tetrahedron object is also true groups:
>>> G = tetrahedron.pgroup >>> G.is_group True
Also the group generated by the permutations in the tetrahedron pgroup – even the first two – is a proper group:
>>> H = PermutationGroup(G[0], G[1]) >>> J = PermutationGroup(list(H.generate())); J PermutationGroup([ Permutation(0, 1)(2, 3), Permutation(3), Permutation(1, 2, 3), Permutation(1, 3, 2), Permutation(0, 3, 1), Permutation(0, 2, 3), Permutation(0, 3)(1, 2), Permutation(0, 1, 3), Permutation(3)(0, 2, 1), Permutation(0, 3, 2), Permutation(3)(0, 1, 2), Permutation(0, 2)(1, 3)]) >>> _.is_group True

generate_dimino
(af=False)[source]¶ Yield group elements using Dimino’s algorithm
If af == True it yields the array form of the permutations
References
[1] The Implementation of Various Algorithms for Permutation Groups in the Computer Algebra System: AXIOM, N.J. Doye, M.Sc. Thesis
Examples
>>> Permutation.print_cyclic = True >>> a = Permutation([0, 2, 1, 3]) >>> b = Permutation([0, 2, 3, 1]) >>> g = PermutationGroup([a, b]) >>> list(g.generate_dimino(af=True)) [[0, 1, 2, 3], [0, 2, 1, 3], [0, 2, 3, 1], [0, 1, 3, 2], [0, 3, 2, 1], [0, 3, 1, 2]]

generate_schreier_sims
(af=False)[source]¶ Yield group elements using the SchreierSims representation in coset_rank order
If af = True it yields the array form of the permutations
Examples
>>> Permutation.print_cyclic = True >>> a = Permutation([0, 2, 1, 3]) >>> b = Permutation([0, 2, 3, 1]) >>> g = PermutationGroup([a, b]) >>> list(g.generate_schreier_sims(af=True)) [[0, 1, 2, 3], [0, 2, 1, 3], [0, 3, 2, 1], [0, 1, 3, 2], [0, 2, 3, 1], [0, 3, 1, 2]]

generators
¶ Returns the generators of the group.
Examples
>>> Permutation.print_cyclic = True >>> a = Permutation([0, 2, 1]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.generators [Permutation(1, 2), Permutation(2)(0, 1)]

is_abelian
¶ Test if the group is Abelian.
Examples
>>> Permutation.print_cyclic = True >>> a = Permutation([0, 2, 1]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.is_abelian False >>> a = Permutation([0, 2, 1]) >>> G = PermutationGroup([a]) >>> G.is_abelian True

is_alt_sym
(eps=0.05, _random_prec=None)[source]¶ Monte Carlo test for the symmetric/alternating group for degrees >= 8.
More specifically, it is onesided Monte Carlo with the answer True (i.e., G is symmetric/alternating) guaranteed to be correct, and the answer False being incorrect with probability eps.
Notes
The algorithm itself uses some nontrivial results from group theory and number theory: 1) If a transitive group
G
of degreen
contains an element with a cycle of lengthn/2 < p < n2
forp
a prime,G
is the symmetric or alternating group ([1], pp. 8182) 2) The proportion of elements in the symmetric/alternating group having the property described in 1) is approximately\log(2)/\log(n)
([1], p.82; [2], pp. 226227). The helper function_check_cycles_alt_sym
is used to go over the cycles in a permutation and look for ones satisfying 1).Examples
>>> D = DihedralGroup(10) >>> D.is_alt_sym() False

is_nilpotent
¶ Test if the group is nilpotent.
A group
G
is nilpotent if it has a central series of finite length. Alternatively,G
is nilpotent if its lower central series terminates with the trivial group. Every nilpotent group is also solvable ([1], p.29, [12]).Examples
>>> C = CyclicGroup(6) >>> C.is_nilpotent True >>> S = SymmetricGroup(5) >>> S.is_nilpotent False
See also

is_normal
(gr, strict=True)[source]¶ Test if G=self is a normal subgroup of gr.
G is normal in gr if for each g2 in G, g1 in gr, g = g1*g2*g1**1 belongs to G It is sufficient to check this for each g1 in gr.generator and g2 g2 in G.generator
Examples
>>> Permutation.print_cyclic = True >>> a = Permutation([1, 2, 0]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G1 = PermutationGroup([a, Permutation([2, 0, 1])]) >>> G1.is_normal(G) True

is_primitive
(randomized=True)[source]¶ Test if a group is primitive.
A permutation group
G
acting on a setS
is called primitive ifS
contains no nontrivial block under the action ofG
(a block is nontrivial if its cardinality is more than1
).Notes
The algorithm is described in [1], p.83, and uses the function minimal_block to search for blocks of the form
\{0, k\}
fork
ranging over representatives for the orbits ofG_0
, the stabilizer of0
. This algorithm has complexityO(n^2)
wheren
is the degree of the group, and will perform badly ifG_0
is small.There are two implementations offered: one finds
G_0
deterministically using the functionstabilizer
, and the other (default) produces random elements ofG_0
usingrandom_stab
, hoping that they generate a subgroup ofG_0
with not too many more orbits than G_0 (this is suggested in [1], p.83). Behavior is changed by therandomized
flag.Examples
>>> D = DihedralGroup(10) >>> D.is_primitive() False
See also

is_solvable
¶ Test if the group is solvable.
G
is solvable if its derived series terminates with the trivial group ([1], p.29).Examples
>>> S = SymmetricGroup(3) >>> S.is_solvable True
See also

is_subgroup
(G, strict=True)[source]¶ Return True if all elements of self belong to G.
If
strict
is False then ifself
’s degree is smaller thanG
’s, the elements will be resized to have the same degree.Examples
Testing is strict by default: the degree of each group must be the same:
>>> p = Permutation(0, 1, 2, 3, 4, 5) >>> G1 = PermutationGroup([Permutation(0, 1, 2), Permutation(0, 1)]) >>> G2 = PermutationGroup([Permutation(0, 2), Permutation(0, 1, 2)]) >>> G3 = PermutationGroup([p, p**2]) >>> assert G1.order() == G2.order() == G3.order() == 6 >>> G1.is_subgroup(G2) True >>> G1.is_subgroup(G3) False >>> G3.is_subgroup(PermutationGroup(G3[1])) False >>> G3.is_subgroup(PermutationGroup(G3[0])) True
To ignore the size, set
strict
to False:>>> S3 = SymmetricGroup(3) >>> S5 = SymmetricGroup(5) >>> S3.is_subgroup(S5, strict=False) True >>> C7 = CyclicGroup(7) >>> G = S5*C7 >>> S5.is_subgroup(G, False) True >>> C7.is_subgroup(G, 0) False

is_transitive
(strict=True)[source]¶ Test if the group is transitive.
A group is transitive if it has a single orbit.
If
strict
is False the group is transitive if it has a single orbit of length different from 1.Examples
>>> a = Permutation([0, 2, 1, 3]) >>> b = Permutation([2, 0, 1, 3]) >>> G1 = PermutationGroup([a, b]) >>> G1.is_transitive() False >>> G1.is_transitive(strict=False) True >>> c = Permutation([2, 3, 0, 1]) >>> G2 = PermutationGroup([a, c]) >>> G2.is_transitive() True >>> d = Permutation([1, 0, 2, 3]) >>> e = Permutation([0, 1, 3, 2]) >>> G3 = PermutationGroup([d, e]) >>> G3.is_transitive() or G3.is_transitive(strict=False) False

is_trivial
¶ Test if the group is the trivial group.
This is true if the group contains only the identity permutation.
Examples
>>> G = PermutationGroup([Permutation([0, 1, 2])]) >>> G.is_trivial True

lower_central_series
()[source]¶ Return the lower central series for the group.
The lower central series for a group
G
is the seriesG = G_0 > G_1 > G_2 > \ldots
whereG_k = [G, G_{k1}]
, i.e. every term after the first is equal to the commutator ofG
and the previous term inG1
([1], p.29).Returns:  A list of permutation groups in the order
G = G_0, G_1, G_2, \ldots
Examples
>>> A = AlternatingGroup(4) >>> len(A.lower_central_series()) 2 >>> A.lower_central_series()[1].is_subgroup(DihedralGroup(2)) True
See also

make_perm
(n, seed=None)[source]¶ Multiply
n
randomly selected permutations from pgroup together, starting with the identity permutation. Ifn
is a list of integers, those integers will be used to select the permutations and they will be applied in L to R order: make_perm((A, B, C)) will give CBA(I) where I is the identity permutation.seed
is used to set the seed for the random selection of permutations from pgroup. If this is a list of integers, the corresponding permutations from pgroup will be selected in the order give. This is mainly used for testing purposes.Examples
>>> Permutation.print_cyclic = True >>> a, b = [Permutation([1, 0, 3, 2]), Permutation([1, 3, 0, 2])] >>> G = PermutationGroup([a, b]) >>> G.make_perm(1, [0]) Permutation(0, 1)(2, 3) >>> G.make_perm(3, [0, 1, 0]) Permutation(0, 2, 3, 1) >>> G.make_perm([0, 1, 0]) Permutation(0, 2, 3, 1)
See also

max_div
¶ Maximum proper divisor of the degree of a permutation group.
Notes
Obviously, this is the degree divided by its minimal proper divisor (larger than
1
, if one exists). As it is guaranteed to be prime, thesieve
fromdiofant.ntheory
is used. This function is also used as an optimization tool for the functionsminimal_block
and_union_find_merge
.Examples
>>> G = PermutationGroup([Permutation([0, 2, 1, 3])]) >>> G.max_div 2
See also

minimal_block
(points)[source]¶ For a transitive group, finds the block system generated by
points
.If a group
G
acts on a setS
, a nonempty subsetB
ofS
is called a block under the action ofG
if for allg
inG
we havegB = B
(g
fixesB
) orgB
andB
have no common points (g
movesB
entirely). ([1], p.23; [6]).The distinct translates
gB
of a blockB
forg
inG
partition the setS
and this set of translates is known as a block system. Moreover, we obviously have that all blocks in the partition have the same size, hence the block size dividesS
([1], p.23). AG
congruence is an equivalence relation~
on the setS
such thata ~ b
impliesg(a) ~ g(b)
for allg
inG
. For a transitive group, the equivalence classes of aG
congruence and the blocks of a block system are the same thing ([1], p.23).The algorithm below checks the group for transitivity, and then finds the
G
congruence generated by the pairs(p_0, p_1), (p_0, p_2), ..., (p_0,p_{k1})
which is the same as finding the maximal block system (i.e., the one with minimum block size) such thatp_0, ..., p_{k1}
are in the same block ([1], p.83).It is an implementation of Atkinson’s algorithm, as suggested in [1], and manipulates an equivalence relation on the set
S
using a unionfind data structure. The running time is just aboveO(pointsS)
. ([1], pp. 8387; [7]).Examples
>>> D = DihedralGroup(10) >>> D.minimal_block([0, 5]) [0, 6, 2, 8, 4, 0, 6, 2, 8, 4] >>> D.minimal_block([0, 1]) [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

normal_closure
(other, k=10)[source]¶ Return the normal closure of a subgroup/set of permutations.
If
S
is a subset of a groupG
, the normal closure ofA
inG
is defined as the intersection of all normal subgroups ofG
that containA
([1], p.14). Alternatively, it is the group generated by the conjugatesx^{1}yx
forx
a generator ofG
andy
a generator of the subgroup\left\langle S\right\rangle
generated byS
(for some chosen generating set for\left\langle S\right\rangle
) ([1], p.73).Parameters:  other – a subgroup/list of permutations/single permutation
 k – an implementationspecific parameter that determines the number
of conjugates that are adjoined to
other
at once
Examples
>>> S = SymmetricGroup(5) >>> C = CyclicGroup(5) >>> G = S.normal_closure(C) >>> G.order() 60 >>> G.is_subgroup(AlternatingGroup(5)) True
See also
Notes
The algorithm is described in [1], pp. 7374; it makes use of the generation of random elements for permutation groups by the product replacement algorithm.

orbit
(alpha, action='tuples')[source]¶ Compute the orbit of alpha
\{g(\alpha)  g \in G\}
as a set.The time complexity of the algorithm used here is
O(Orb*r)
whereOrb
is the size of the orbit andr
is the number of generators of the group. For a more detailed analysis, see [1], p.78, [2], pp. 1921. Here alpha can be a single point, or a list of points.If alpha is a single point, the ordinary orbit is computed. if alpha is a list of points, there are three available options:
‘union’  computes the union of the orbits of the points in the list ‘tuples’  computes the orbit of the list interpreted as an ordered tuple under the group action ( i.e., g((1,2,3)) = (g(1), g(2), g(3)) ) ‘sets’  computes the orbit of the list interpreted as a sets
Examples
>>> a = Permutation([1, 2, 0, 4, 5, 6, 3]) >>> G = PermutationGroup([a]) >>> G.orbit(0) {0, 1, 2} >>> G.orbit([0, 4], 'union') {0, 1, 2, 3, 4, 5, 6}
See also

orbit_rep
(alpha, beta, schreier_vector=None)[source]¶ Return a group element which sends
alpha
tobeta
.If
beta
is not in the orbit ofalpha
, the function returnsFalse
. This implementation makes use of the schreier vector. For a proof of correctness, see [1], p.80Examples
>>> Permutation.print_cyclic = True >>> G = AlternatingGroup(5) >>> G.orbit_rep(0, 4) Permutation(0, 4, 1, 2, 3)
See also

orbit_transversal
(alpha, pairs=False)[source]¶ Computes a transversal for the orbit of
alpha
as a set.For a permutation group
G
, a transversal for the orbitOrb = \{g(\alpha)  g \in G\}
is a set\{g_\beta  g_\beta(\alpha) = \beta\}
for\beta \in Orb
. Note that there may be more than one possible transversal. Ifpairs
is set toTrue
, it returns the list of pairs(\beta, g_\beta)
. For a proof of correctness, see [1], p.79Examples
>>> Permutation.print_cyclic = True >>> G = DihedralGroup(6) >>> G.orbit_transversal(0) [Permutation(5), Permutation(0, 1, 2, 3, 4, 5), Permutation(0, 5)(1, 4)(2, 3), Permutation(0, 2, 4)(1, 3, 5), Permutation(5)(0, 4)(1, 3), Permutation(0, 3)(1, 4)(2, 5)]
See also

orbits
(rep=False)[source]¶ Return the orbits of self, ordered according to lowest element in each orbit.
Examples
>>> a = Permutation(1, 5)(2, 3)(4, 0, 6) >>> b = Permutation(1, 5)(3, 4)(2, 6, 0) >>> G = PermutationGroup([a, b]) >>> G.orbits() [{0, 2, 3, 4, 6}, {1, 5}]

order
()[source]¶ Return the order of the group: the number of permutations that can be generated from elements of the group.
The number of permutations comprising the group is given by len(group); the length of each permutation in the group is given by group.size.
Examples
>>> a = Permutation([1, 0, 2]) >>> G = PermutationGroup([a]) >>> G.degree 3 >>> len(G) 1 >>> G.order() 2 >>> list(G.generate()) [Permutation(2), Permutation(2)(0, 1)]
>>> a = Permutation([0, 2, 1]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.order() 6
See also

pointwise_stabilizer
(points, incremental=True)[source]¶ Return the pointwise stabilizer for a set of points.
For a permutation group
G
and a set of points\{p_1, p_2,\ldots, p_k\}
, the pointwise stabilizer ofp_1, p_2, \ldots, p_k
is defined asG_{p_1,\ldots, p_k} = \{g\in G  g(p_i) = p_i \forall i\in\{1, 2,\ldots,k\}\} ([1],p20). It is a subgroup of ``G
.Examples
>>> S = SymmetricGroup(7) >>> Stab = S.pointwise_stabilizer([2, 3, 5]) >>> Stab.is_subgroup(S.stabilizer(2).stabilizer(3).stabilizer(5)) True
See also
Notes
When incremental == True, rather than the obvious implementation using successive calls to .stabilizer(), this uses the incremental SchreierSims algorithm to obtain a base with starting segment  the given points.

random_pr
(gen_count=11, iterations=50, _random_prec=None)[source]¶ Return a random group element using product replacement.
For the details of the product replacement algorithm, see
_random_pr_init
Inrandom_pr
the actual ‘product replacement’ is performed. Notice that if the attribute_random_gens
is empty, it needs to be initialized by_random_pr_init
.See also

random_stab
(alpha, schreier_vector=None, _random_prec=None)[source]¶ Random element from the stabilizer of
alpha
.The schreier vector for
alpha
is an optional argument used for speeding up repeated calls. The algorithm is described in [1], p.81See also

schreier_sims
()[source]¶ SchreierSims algorithm.
It computes the generators of the chain of stabilizers G > G_{b_1} > .. > G_{b1,..,b_r} > 1 in which G_{b_1,..,b_i} stabilizes b_1,..,b_i, and the corresponding
s
cosets. An element of the group can be written as the product h_1*..*h_s.We use the incremental SchreierSims algorithm.
Examples
>>> a = Permutation([0, 2, 1]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.schreier_sims() >>> G.basic_transversals [{0: Permutation(2)(0, 1), 1: Permutation(2), 2: Permutation(1, 2)}, {0: Permutation(2), 2: Permutation(0, 2)}]

schreier_sims_incremental
(base=None, gens=None)[source]¶ Extend a sequence of points and generating set to a base and strong generating set.
Parameters:  base – The sequence of points to be extended to a base. Optional
parameter with default value
[]
.  gens – The generating set to be extended to a strong generating set
relative to the base obtained. Optional parameter with default
value
self.generators
.
Returns: (base, strong_gens) –
base
is the base obtained, andstrong_gens
is the strong generating set relative to it. The original parametersbase
,gens
remain unchanged.Examples
>>> from diofant.combinatorics.testutil import _verify_bsgs >>> A = AlternatingGroup(7) >>> base = [2, 3] >>> seq = [2, 3] >>> base, strong_gens = A.schreier_sims_incremental(base=seq) >>> _verify_bsgs(A, base, strong_gens) True >>> base[:2] [2, 3]
Notes
This version of the SchreierSims algorithm runs in polynomial time. There are certain assumptions in the implementation  if the trivial group is provided,
base
andgens
are returned immediately, as any sequence of points is a base for the trivial group. If the identity is present in the generatorsgens
, it is removed as it is a redundant generator. The implementation is described in [1], pp. 9093.See also
 base – The sequence of points to be extended to a base. Optional
parameter with default value

schreier_sims_random
(base=None, gens=None, consec_succ=10, _random_prec=None)[source]¶ Randomized SchreierSims algorithm.
The randomized SchreierSims algorithm takes the sequence
base
and the generating setgens
, and extendsbase
to a base, andgens
to a strong generating set relative to that base with probability of a wrong answer at most2^{consec\_succ}
, provided the random generators are sufficiently random.Parameters:  base – The sequence to be extended to a base.
 gens – The generating set to be extended to a strong generating set.
 consec_succ – The parameter defining the probability of a wrong answer.
 _random_prec – An internal parameter used for testing purposes.
Returns: (base, strong_gens) –
base
is the base andstrong_gens
is the strong generating set relative to it.Examples
>>> from diofant.combinatorics.testutil import _verify_bsgs >>> S = SymmetricGroup(5) >>> base, strong_gens = S.schreier_sims_random(consec_succ=5) >>> _verify_bsgs(S, base, strong_gens) # doctest: +SKIP True
Notes
The algorithm is described in detail in [1], pp. 9798. It extends the orbits
orbs
and the permutation groupsstabs
to basic orbits and basic stabilizers for the base and strong generating set produced in the end. The idea of the extension process is to “sift” random group elements through the stabilizer chain and amend the stabilizers/orbits along the way when a sift is not successful. The helper function_strip
is used to attempt to decompose a random group element according to the current state of the stabilizer chain and report whether the element was fully decomposed (successful sift) or not (unsuccessful sift). In the latter case, the level at which the sift failed is reported and used to amendstabs
,base
,gens
andorbs
accordingly. The halting condition is forconsec_succ
consecutive successful sifts to pass. This makes sure that the currentbase
andgens
form a BSGS with probability at least1  1/\text{consec\_succ}
.See also

schreier_vector
(alpha)[source]¶ Computes the schreier vector for
alpha
.The Schreier vector efficiently stores information about the orbit of
alpha
. It can later be used to quickly obtain elements of the group that sendalpha
to a particular element in the orbit. Notice that the Schreier vector depends on the order in which the group generators are listed. For a definition, see [3]. Since list indices start from zero, we adopt the convention to use “None” instead of 0 to signify that an element doesn’t belong to the orbit. For the algorithm and its correctness, see [2], pp.7880.Examples
>>> a = Permutation([2, 4, 6, 3, 1, 5, 0]) >>> b = Permutation([0, 1, 3, 5, 4, 6, 2]) >>> G = PermutationGroup([a, b]) >>> G.schreier_vector(0) [1, None, 0, 1, None, 1, 0]
See also

stabilizer
(alpha)[source]¶ Return the stabilizer subgroup of
alpha
.The stabilizer of
\alpha
is the groupG_\alpha = \{g \in G  g(\alpha) = \alpha\}
. For a proof of correctness, see [1], p.79.Examples
>>> Permutation.print_cyclic = True >>> G = DihedralGroup(6) >>> G.stabilizer(5) PermutationGroup([ Permutation(5)(0, 4)(1, 3), Permutation(5)])
See also

strong_gens
¶ Return a strong generating set from the SchreierSims algorithm.
A generating set
S = \{g_1, g_2, ..., g_t\}
for a permutation groupG
is a strong generating set relative to the sequence of points (referred to as a “base”)(b_1, b_2, ..., b_k)
if, for1 \leq i \leq k
we have that the intersection of the pointwise stabilizerG^{(i+1)} := G_{b_1, b_2, ..., b_i}
withS
generates the pointwise stabilizerG^{(i+1)}
. The concepts of a base and strong generating set and their applications are discussed in depth in [1], pp. 8789 and [2], pp. 5557.Examples
>>> D = DihedralGroup(4) >>> D.strong_gens [Permutation(0, 1, 2, 3), Permutation(0, 3)(1, 2), Permutation(1, 3)] >>> D.base [0, 1]
See also

subgroup_search
(prop, base=None, strong_gens=None, tests=None, init_subgroup=None)[source]¶ Find the subgroup of all elements satisfying the property
prop
.This is done by a depthfirst search with respect to base images that uses several tests to prune the search tree.
Parameters:  prop – The property to be used. Has to be callable on group elements
and always return
True
orFalse
. It is assumed that all group elements satisfyingprop
indeed form a subgroup.  base – A base for the supergroup.
 strong_gens – A strong generating set for the supergroup.
 tests – A list of callables of length equal to the length of
base
. These are used to rule out group elements by partial base images, so thattests[l](g)
returns False if the elementg
is known not to satisfy prop base on where g sends the firstl + 1
base points.  init_subgroup – if a subgroup of the sought group is known in advance, it can be passed to the function as this parameter.
Returns: res – The subgroup of all elements satisfying
prop
. The generating set for this group is guaranteed to be a strong generating set relative to the basebase
.Examples
>>> from diofant.combinatorics.testutil import _verify_bsgs >>> S = SymmetricGroup(7) >>> prop_even = lambda x: x.is_even >>> base, strong_gens = S.schreier_sims_incremental() >>> G = S.subgroup_search(prop_even, base=base, strong_gens=strong_gens) >>> G.is_subgroup(AlternatingGroup(7)) True >>> _verify_bsgs(G, base, G.generators) True
Notes
This function is extremely lenghty and complicated and will require some careful attention. The implementation is described in [1], pp. 114117, and the comments for the code here follow the lines of the pseudocode in the book for clarity.
The complexity is exponential in general, since the search process by itself visits all members of the supergroup. However, there are a lot of tests which are used to prune the search tree, and users can define their own tests via the
tests
parameter, so in practice, and for some computations, it’s not terrible.A crucial part in the procedure is the frequent base change performed (this is line 11 in the pseudocode) in order to obtain a new basic stabilizer. The book mentiones that this can be done by using
.baseswap(...)
, however the current implementation uses a more straightforward way to find the next basic stabilizer  calling the function.stabilizer(...)
on the previous basic stabilizer. prop – The property to be used. Has to be callable on group elements
and always return

transitivity_degree
¶ Compute the degree of transitivity of the group.
A permutation group
G
acting on\Omega = \{0, 1, ..., n1\}
isk
fold transitive, if, for any k points(a_1, a_2, ..., a_k)\in\Omega
and any k points(b_1, b_2, ..., b_k)\in\Omega
there existsg\in G
such thatg(a_1)=b_1, g(a_2)=b_2, ..., g(a_k)=b_k
The degree of transitivity ofG
is the maximumk
such thatG
isk
fold transitive. ([8])Examples
>>> a = Permutation([1, 2, 0]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.transitivity_degree 3
See also
