Permutation Groups

class sympy.combinatorics.perm_groups.PermutationGroup

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

>>> from sympy.combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from sympy.combinatorics.permutations import Cycle
>>> from sympy.combinatorics.polyhedron import Polyhedron
>>> from sympy.combinatorics.perm_groups import PermutationGroup

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

sympy.combinatorics.polyhedron.Polyhedron, sympy.combinatorics.permutations.Permutation

References

R33

Holt, D., Eick, B., O’Brien, E. “Handbook of Computational Group Theory”

R34

Seress, A. “Permutation Group Algorithms”

R35

https://en.wikipedia.org/wiki/Schreier_vector

R36

https://en.wikipedia.org/wiki/Nielsen_transformation#Product_replacement_algorithm

R37

Frank Celler, Charles R.Leedham-Green, Scott H.Murray, Alice C.Niemeyer, and E.A.O’Brien. “Generating Random Elements of a Finite Group”

R38

https://en.wikipedia.org/wiki/Block_%28permutation_group_theory%29

R39

http://www.algorithmist.com/index.php/Union_Find

R40

https://en.wikipedia.org/wiki/Multiply_transitive_group#Multiply_transitive_groups

R41

https://en.wikipedia.org/wiki/Center_%28group_theory%29

10

https://en.wikipedia.org/wiki/Centralizer_and_normalizer

11

http://groupprops.subwiki.org/wiki/Derived_subgroup

12

https://en.wikipedia.org/wiki/Nilpotent_group

13

http://www.math.colostate.edu/~hulpke/CGT/cgtnotes.pdf

base

Return a base from the Schreier-Sims algorithm.

For a permutation group \(G\), a base is a sequence of points \(B = (b_1, b_2, ..., b_k)\) such that no element of \(G\) apart from the identity fixes all the points in \(B\). The concepts of a base and strong generating set and their applications are discussed in depth in [1], pp. 87-89 and [2], pp. 55-57.

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

>>> from sympy.combinatorics import Permutation, PermutationGroup
>>> 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)

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)\), where \(i\) is given by pos, 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, and strong_gens is a generating set relative to it.

Examples

>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> from sympy.combinatorics.testutil import _verify_bsgs
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> 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],
[(0 1 2 3), (3)(0 1), (1 3 2),
 (2 3), (1 3)])

check that base, gens is a BSGS

>>> S1 = PermutationGroup(gens)
>>> _verify_bsgs(S1, base, gens)
True

Notes

The deterministic version of the algorithm is discussed in [1], pp. 102-103; 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.

See also

schreier_sims

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 group \(G\), and \(G^{(i)} = G_{b_1, b_2, ..., b_{i-1}}\) is the i-th basic stabilizer (so that \(G^{(1)} = G\)), the i-th basic orbit relative to this base is the orbit of \(b_i\) under \(G^{(i)}\). See [1], pp. 87-89 for more information.

Examples

>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> S = SymmetricGroup(4)
>>> S.basic_orbits
[[0, 1, 2, 3], [1, 2, 3], [2, 3]]

See also

base, strong_gens, basic_transversals, basic_stabilizers

basic_stabilizers

Return a chain of stabilizers relative to a base and strong generating set.

The i-th basic stabilizer \(G^{(i)}\) relative to a base \((b_1, b_2, ..., b_k)\) is \(G_{b_1, b_2, ..., b_{i-1}}\). For more information, see [1], pp. 87-89.

Examples

>>> from sympy.combinatorics.named_groups import AlternatingGroup
>>> A = AlternatingGroup(4)
>>> A.schreier_sims()
>>> A.base
[0, 1]
>>> for g in A.basic_stabilizers:
...     print(g)
...
PermutationGroup([
    (3)(0 1 2),
    (1 2 3)])
PermutationGroup([
    (1 2 3)])

See also

base, strong_gens, basic_orbits, basic_transversals

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. 87-89 for more information.

Examples

>>> from sympy.combinatorics.named_groups import AlternatingGroup
>>> A = AlternatingGroup(4)
>>> A.basic_transversals
[{0: (3), 1: (3)(0 1 2), 2: (3)(0 2 1), 3: (0 3 1)}, {1: (3), 2: (1 2 3), 3: (1 3 2)}]

See also

strong_gens, base, basic_orbits, basic_stabilizers

center()

Return the center of a permutation group.

The center for a group \(G\) is defined as \(Z(G) = \{z\in G | \forall g\in G, zg = gz \}\), the set of elements of \(G\) that commute with all elements of \(G\). It is equal to the centralizer of \(G\) inside \(G\), and is naturally a subgroup of \(G\) ([9]).

Examples

>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> D = DihedralGroup(4)
>>> G = D.center()
>>> G.order()
2

Notes

This is a naive implementation that is a straightforward application of .centralizer()

See also

centralizer

centralizer(other)

Return the centralizer of a group/set/element.

The centralizer of a set of permutations S inside a group G is the set of elements of G that commute with all elements of S:

`C_G(S) = \{ g \in G | gs = sg \forall s \in S\}` ([10])

Usually, S is a subset of G, but if G is a proper subgroup of the full symmetric group, we allow for S to have elements outside G.

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

>>> from sympy.combinatorics.named_groups import (SymmetricGroup,
... CyclicGroup)
>>> S = SymmetricGroup(6)
>>> C = CyclicGroup(6)
>>> H = S.centralizer(C)
>>> H.is_subgroup(C)
True

Notes

The implementation is an application of .subgroup_search() with tests using a specific base for the group G.

See also

subgroup_search

commutator(G, H)

Return the commutator of two subgroups.

For a permutation group K and subgroups G, H, the commutator of G and H is defined as the group generated by all the commutators \([g, h] = hgh^{-1}g^{-1}\) for g in G and h in H. It is naturally a subgroup of K ([1], p.27).

Examples

>>> from sympy.combinatorics.named_groups import (SymmetricGroup,
... AlternatingGroup)
>>> S = SymmetricGroup(5)
>>> A = AlternatingGroup(5)
>>> G = S.commutator(S, A)
>>> G.is_subgroup(A)
True

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}\) for \(h\) a generator of \(H\) and \(g\) a generator of \(G\) ([1], p.28)

See also

derived_subgroup

contains(g, strict=True)

Test if permutation g belong to self, G.

If g is an element of G it can be written as a product of factors drawn from the cosets of G’s stabilizers. To see if g is one of the actual generators defining the group use G.has(g).

If strict is not True, g will be resized, if necessary, to match the size of permutations in self.

Examples

>>> from sympy.combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from sympy.combinatorics.perm_groups import PermutationGroup

>>> 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, has, in

coset_factor(g, factor_index=False)

Return G’s (self’s) coset factorization of g

If g is an element of G then it can be written as the product of permutations drawn from the Schreier-Sims coset decomposition,

The permutations returned in f are those for which the product gives g: g = f[n]*...f[1]*f[0] where n = len(B) and B = G.base. f[i] is one of the permutations in self._basic_orbits[i].

If factor_index==True, returns a tuple [b[0],..,b[n]], where b[i] belongs to self._basic_orbits[i]

Examples

>>> from sympy.combinatorics import Permutation, PermutationGroup
>>> 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 also

util._strip

coset_rank(g)

rank using Schreier-Sims representation

The coset rank of g is the ordering number in which it appears in the lexicographic listing according to the coset decomposition

The ordering is the same as in G.generate(method=’coset’). If g does not belong to the group it returns None.

Examples

>>> from sympy.combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> 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)
(7)(2 4)(3 5)

See also

coset_factor

coset_table(H)

Return the standardised (right) coset table of self in H as a list of lists.

coset_transversal(H)

Return a transversal of the right cosets of self by its subgroup H using the second method described in [1], Subsection 4.6.7

coset_unrank(rank, af=False)

unrank using Schreier-Sims 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

>>> from sympy.combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> a = Permutation([1, 0, 2])
>>> G = PermutationGroup([a])
>>> G.degree
3
>>> len(G)
1
>>> G.order()
2
>>> list(G.generate())
[(2), (2)(0 1)]

See also

order

derived_series()

Return the derived series for the group.

The derived series for a group \(G\) is defined as \(G = G_0 > G_1 > G_2 > \ldots\) where \(G_i = [G_{i-1}, G_{i-1}]\), i.e. \(G_i\) is the derived subgroup of \(G_{i-1}\), for \(i\in\mathbb{N}\). When we have \(G_k = G_{k-1}\) for some \(k\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

>>> from sympy.combinatorics.named_groups import (SymmetricGroup,
... AlternatingGroup, DihedralGroup)
>>> 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

derived_subgroup()

Compute the derived subgroup.

The derived subgroup, or commutator subgroup is the subgroup generated by all commutators \([g, h] = hgh^{-1}g^{-1}\) for \(g, h\in G\) ; it is equal to the normal closure of the set of commutators of the generators ([1], p.28, [11]).

Examples

>>> from sympy.combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> 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

derived_series

elements

Returns all the elements of the permutation group as a set

Examples

>>> from sympy.combinatorics import Permutation, PermutationGroup
>>> p = PermutationGroup(Permutation(1, 3), Permutation(1, 2))
>>> p.elements
{(3), (2 3), (3)(1 2), (1 2 3), (1 3 2), (1 3)}

generate(method='coset', af=False)

Return iterator to generate the elements of the group

Iteration is done with one of these methods:

method='coset'  using the Schreier-Sims coset representation
method='dimino' using the Dimino method

If af = True it yields the array form of the permutations

Examples

>>> from sympy.combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from sympy.combinatorics import PermutationGroup
>>> from sympy.combinatorics.polyhedron import tetrahedron

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([
    (0 1)(2 3),
    (1 2 3),
    (1 3 2),
    (0 3 1),
    (0 2 3),
    (0 3)(1 2),
    (0 1 3),
    (3)(0 2 1),
    (0 3 2),
    (3)(0 1 2),
    (0 2)(1 3)])
>>> _.is_group
True

generate_dimino(af=False)

Yield group elements using Dimino’s algorithm

If af == True it yields the array form of the permutations

Examples

>>> from sympy.combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> 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]]

References

R42

The Implementation of Various Algorithms for Permutation Groups in the Computer Algebra System: AXIOM, N.J. Doye, M.Sc. Thesis

generate_schreier_sims(af=False)

Yield group elements using the Schreier-Sims representation in coset_rank order

If af = True it yields the array form of the permutations

Examples

>>> from sympy.combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> 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]]

generator_product(g, original=False)

Return a list of strong generators \([s1, ..., sn]\) s.t \(g = sn*...*s1\). If \(original=True\), make the list contain only the original group generators

generators

Returns the generators of the group.

Examples

>>> from sympy.combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> a = Permutation([0, 2, 1])
>>> b = Permutation([1, 0, 2])
>>> G = PermutationGroup([a, b])
>>> G.generators
[(1 2), (2)(0 1)]

identity

Return the identity element of the permutation group.

is_abelian

Test if the group is Abelian.

Examples

>>> from sympy.combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> 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)

Monte Carlo test for the symmetric/alternating group for degrees >= 8.

More specifically, it is one-sided 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.

For degree < 8, the order of the group is checked so the test is deterministic.

Notes

The algorithm itself uses some nontrivial results from group theory and number theory: 1) If a transitive group G of degree n contains an element with a cycle of length n/2 < p < n-2 for p a prime, G is the symmetric or alternating group ([1], pp. 81-82) 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. 226-227). The helper function _check_cycles_alt_sym is used to go over the cycles in a permutation and look for ones satisfying 1).

Examples

>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> D = DihedralGroup(10)
>>> D.is_alt_sym()
False

See also

_check_cycles_alt_sym

is_elementary(p)

Return True if the group is elementary abelian. An elementary abelian group is a finite abelian group, where every nontrivial element has order \(p\), where \(p\) is a prime.

Examples

>>> from sympy.combinatorics import Permutation
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> a = Permutation([0, 2, 1])
>>> G = PermutationGroup([a])
>>> G.is_elementary(2)
True
>>> a = Permutation([0, 2, 1, 3])
>>> b = Permutation([3, 1, 2, 0])
>>> G = PermutationGroup([a, b])
>>> G.is_elementary(2)
True
>>> G.is_elementary(3)
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

>>> from sympy.combinatorics.named_groups import (SymmetricGroup,
... CyclicGroup)
>>> C = CyclicGroup(6)
>>> C.is_nilpotent
True
>>> S = SymmetricGroup(5)
>>> S.is_nilpotent
False

See also

lower_central_series, is_solvable

is_normal(gr, strict=True)

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.generators and g2 in G.generators.

Examples

>>> from sympy.combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> 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_polycyclic

Return True if a group is polycyclic. A group is polycyclic if it has a subnormal series with cyclic factors. For finite groups, this is the same as if the group is solvable.

Examples

>>> from sympy.combinatorics import Permutation, PermutationGroup
>>> a = Permutation([0, 2, 1, 3])
>>> b = Permutation([2, 0, 1, 3])
>>> G = PermutationGroup([a, b])
>>> G.is_polycyclic
True

is_primitive(randomized=True)

Test if a group is primitive.

A permutation group G acting on a set S is called primitive if S contains no nontrivial block under the action of G (a block is nontrivial if its cardinality is more than 1).

Notes

The algorithm is described in [1], p.83, and uses the function minimal_block to search for blocks of the form \(\{0, k\}\) for k ranging over representatives for the orbits of \(G_0\), the stabilizer of 0. This algorithm has complexity \(O(n^2)\) where n is the degree of the group, and will perform badly if \(G_0\) is small.

There are two implementations offered: one finds \(G_0\) deterministically using the function stabilizer, and the other (default) produces random elements of \(G_0\) using random_stab, hoping that they generate a subgroup of \(G_0\) with not too many more orbits than \(G_0\) (this is suggested in [1], p.83). Behavior is changed by the randomized flag.

Examples

>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> D = DihedralGroup(10)
>>> D.is_primitive()
False

See also

minimal_block, random_stab

is_solvable

Test if the group is solvable.

G is solvable if its derived series terminates with the trivial group ([1], p.29).

Examples

>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> S = SymmetricGroup(3)
>>> S.is_solvable
True

See also

is_nilpotent, derived_series

is_subgroup(G, strict=True)

Return True if all elements of self belong to G.

If strict is False then if self’s degree is smaller than G’s, the elements will be resized to have the same degree.

Examples

>>> from sympy.combinatorics import Permutation, PermutationGroup
>>> from sympy.combinatorics.named_groups import (SymmetricGroup,
...    CyclicGroup)

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)

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

>>> from sympy.combinatorics.permutations import Permutation
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> 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

>>> from sympy.combinatorics import Permutation
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> G = PermutationGroup([Permutation([0, 1, 2])])
>>> G.is_trivial
True

lower_central_series()

Return the lower central series for the group.

The lower central series for a group \(G\) is the series \(G = G_0 > G_1 > G_2 > \ldots\) where \(G_k = [G, G_{k-1}]\), i.e. every term after the first is equal to the commutator of \(G\) and the previous term in \(G1\) ([1], p.29).

Returns

A list of permutation groups in the order \(G = G_0, G_1, G_2, \ldots\)

Examples

>>> from sympy.combinatorics.named_groups import (AlternatingGroup,
... DihedralGroup)
>>> A = AlternatingGroup(4)
>>> len(A.lower_central_series())
2
>>> A.lower_central_series()[1].is_subgroup(DihedralGroup(2))
True

See also

commutator, derived_series

make_perm(n, seed=None)

Multiply n randomly selected permutations from pgroup together, starting with the identity permutation. If n 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

>>> from sympy.combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> a, b = [Permutation([1, 0, 3, 2]), Permutation([1, 3, 0, 2])]
>>> G = PermutationGroup([a, b])
>>> G.make_perm(1, [0])
(0 1)(2 3)
>>> G.make_perm(3, [0, 1, 0])
(0 2 3 1)
>>> G.make_perm([0, 1, 0])
(0 2 3 1)

See also

random

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, the sieve from sympy.ntheory is used. This function is also used as an optimization tool for the functions minimal_block and _union_find_merge.

Examples

>>> from sympy.combinatorics import Permutation
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> G = PermutationGroup([Permutation([0, 2, 1, 3])])
>>> G.max_div
2

See also

minimal_block, _union_find_merge

minimal_block(points)

For a transitive group, finds the block system generated by points.

If a group G acts on a set S, a nonempty subset B of S is called a block under the action of G if for all g in G we have gB = B (g fixes B) or gB and B have no common points (g moves B entirely). ([1], p.23; [6]).

The distinct translates gB of a block B for g in G partition the set S 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 divides |S| ([1], p.23). A G-congruence is an equivalence relation ~ on the set S such that a ~ b implies g(a) ~ g(b) for all g in G. For a transitive group, the equivalence classes of a G-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_{k-1}) which is the same as finding the maximal block system (i.e., the one with minimum block size) such that p_0, ..., p_{k-1} 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 union-find data structure. The running time is just above \(O(|points||S|)\). ([1], pp. 83-87; [7]).

Examples

>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> D = DihedralGroup(10)
>>> D.minimal_block([0, 5])
[0, 1, 2, 3, 4, 0, 1, 2, 3, 4]
>>> D.minimal_block([0, 1])
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

See also

_union_find_rep, _union_find_merge, is_transitive, is_primitive

minimal_blocks(randomized=True)

For a transitive group, return the list of all minimal block systems. If a group is intransitive, return \(False\).

Examples

>>> from sympy.combinatorics import Permutation
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> DihedralGroup(6).minimal_blocks()
[[0, 1, 0, 1, 0, 1], [0, 1, 2, 0, 1, 2]]
>>> G = PermutationGroup(Permutation(1,2,5))
>>> G.minimal_blocks()
False

See also

minimal_block, is_transitive, is_primitive

normal_closure(other, k=10)

Return the normal closure of a subgroup/set of permutations.

If S is a subset of a group G, the normal closure of A in G is defined as the intersection of all normal subgroups of G that contain A ([1], p.14). Alternatively, it is the group generated by the conjugates x^{-1}yx for x a generator of G and y a generator of the subgroup \left\langle S\right\rangle generated by S (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 implementation-specific parameter that determines the number of conjugates that are adjoined to other at once

Examples

>>> from sympy.combinatorics.named_groups import (SymmetricGroup,
... CyclicGroup, AlternatingGroup)
>>> S = SymmetricGroup(5)
>>> C = CyclicGroup(5)
>>> G = S.normal_closure(C)
>>> G.order()
60
>>> G.is_subgroup(AlternatingGroup(5))
True

Notes

The algorithm is described in [1], pp. 73-74; it makes use of the generation of random elements for permutation groups by the product replacement algorithm.

See also

commutator, derived_subgroup, random_pr

orbit(alpha, action='tuples')

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)\) where \(|Orb|\) is the size of the orbit and r is the number of generators of the group. For a more detailed analysis, see [1], p.78, [2], pp. 19-21. 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

>>> from sympy.combinatorics import Permutation
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> 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_transversal

orbit_rep(alpha, beta, schreier_vector=None)

Return a group element which sends alpha to beta.

If beta is not in the orbit of alpha, the function returns False. This implementation makes use of the schreier vector. For a proof of correctness, see [1], p.80

Examples

>>> from sympy.combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> from sympy.combinatorics.named_groups import AlternatingGroup
>>> G = AlternatingGroup(5)
>>> G.orbit_rep(0, 4)
(0 4 1 2 3)

See also

schreier_vector

orbit_transversal(alpha, pairs=False)

Computes a transversal for the orbit of alpha as a set.

For a permutation group \(G\), a transversal for the orbit \(Orb = \{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. If pairs is set to True, it returns the list of pairs \((\beta, g_\beta)\). For a proof of correctness, see [1], p.79

Examples

>>> from sympy.combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> G = DihedralGroup(6)
>>> G.orbit_transversal(0)
[(5), (0 1 2 3 4 5), (0 5)(1 4)(2 3), (0 2 4)(1 3 5), (5)(0 4)(1 3), (0 3)(1 4)(2 5)]

See also

orbit

orbits(rep=False)

Return the orbits of self, ordered according to lowest element in each orbit.

Examples

>>> from sympy.combinatorics.permutations import Permutation
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> 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()

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

>>> from sympy.combinatorics.permutations import Permutation
>>> from sympy.combinatorics.perm_groups import PermutationGroup

>>> a = Permutation([1, 0, 2])
>>> G = PermutationGroup([a])
>>> G.degree
3
>>> len(G)
1
>>> G.order()
2
>>> list(G.generate())
[(2), (2)(0 1)]

>>> a = Permutation([0, 2, 1])
>>> b = Permutation([1, 0, 2])
>>> G = PermutationGroup([a, b])
>>> G.order()
6

See also

degree

pointwise_stabilizer(points, incremental=True)

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 of \(p_1, p_2, \ldots, p_k\) is defined as \(G_{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

>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> S = SymmetricGroup(7)
>>> Stab = S.pointwise_stabilizer([2, 3, 5])
>>> Stab.is_subgroup(S.stabilizer(2).stabilizer(3).stabilizer(5))
True

Notes

When incremental == True, rather than the obvious implementation using successive calls to .stabilizer(), this uses the incremental Schreier-Sims algorithm to obtain a base with starting segment - the given points.

See also

stabilizer, schreier_sims_incremental

presentation(eliminate_gens=True)

Return an \(FpGroup\) presentation of the group.

The algorithm is described in [1], Chapter 6.1.

random(af=False)

Return a random group element

random_pr(gen_count=11, iterations=50, _random_prec=None)

Return a random group element using product replacement.

For the details of the product replacement algorithm, see _random_pr_init In random_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_pr_init

random_stab(alpha, schreier_vector=None, _random_prec=None)

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.81

See also

random_pr, orbit_rep

schreier_sims()

Schreier-Sims 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 Schreier-Sims algorithm.

Examples

>>> from sympy.combinatorics.permutations import Permutation
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> a = Permutation([0, 2, 1])
>>> b = Permutation([1, 0, 2])
>>> G = PermutationGroup([a, b])
>>> G.schreier_sims()
>>> G.basic_transversals
[{0: (2)(0 1), 1: (2), 2: (1 2)},
 {0: (2), 2: (0 2)}]

schreier_sims_incremental(base=None, gens=None, slp_dict=False)

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.

slp_dict

If \(True\), return a dictionary \({g: gens}\) for each strong generator \(g\) where \(gens\) is a list of strong generators coming before \(g\) in \(strong_gens\), such that the product of the elements of \(gens\) is equal to \(g\).

Returns

(base, strong_gens)

base is the base obtained, and strong_gens is the strong generating set relative to it. The original parameters base, gens remain unchanged.

Examples

>>> from sympy.combinatorics.named_groups import AlternatingGroup
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> from sympy.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 Schreier-Sims algorithm runs in polynomial time. There are certain assumptions in the implementation - if the trivial group is provided, base and gens are returned immediately, as any sequence of points is a base for the trivial group. If the identity is present in the generators gens, it is removed as it is a redundant generator. The implementation is described in [1], pp. 90-93.

See also

schreier_sims, schreier_sims_random

schreier_sims_random(base=None, gens=None, consec_succ=10, _random_prec=None)

Randomized Schreier-Sims algorithm.

The randomized Schreier-Sims algorithm takes the sequence base and the generating set gens, and extends base to a base, and gens to a strong generating set relative to that base with probability of a wrong answer at most \(2^{-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 and strong_gens is the strong generating set relative to it.

Examples

>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> from sympy.combinatorics.testutil import _verify_bsgs
>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> 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. 97-98. It extends the orbits orbs and the permutation groups stabs 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 amend stabs, base, gens and orbs accordingly. The halting condition is for consec_succ consecutive successful sifts to pass. This makes sure that the current base and gens form a BSGS with probability at least \(1 - 1/\text{consec\_succ}\).

See also

schreier_sims

schreier_vector(alpha)

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 send alpha 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.78-80.

Examples

>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> from sympy.combinatorics.permutations import Permutation
>>> 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

orbit

stabilizer(alpha)

Return the stabilizer subgroup of alpha.

The stabilizer of \(\alpha\) is the group \(G_\alpha = \{g \in G | g(\alpha) = \alpha\}\). For a proof of correctness, see [1], p.79.

Examples

>>> from sympy.combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> G = DihedralGroup(6)
>>> G.stabilizer(5)
PermutationGroup([
    (5)(0 4)(1 3)])

See also

orbit

strong_gens

Return a strong generating set from the Schreier-Sims algorithm.

A generating set \(S = \{g_1, g_2, ..., g_t\}\) for a permutation group \(G\) is a strong generating set relative to the sequence of points (referred to as a “base”) \((b_1, b_2, ..., b_k)\) if, for \(1 \leq i \leq k\) we have that the intersection of the pointwise stabilizer \(G^{(i+1)} := G_{b_1, b_2, ..., b_i}\) with \(S\) generates the pointwise stabilizer \(G^{(i+1)}\). The concepts of a base and strong generating set and their applications are discussed in depth in [1], pp. 87-89 and [2], pp. 55-57.

Examples

>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> D = DihedralGroup(4)
>>> D.strong_gens
[(0 1 2 3), (0 3)(1 2), (1 3)]
>>> D.base
[0, 1]

See also

base, basic_transversals, basic_orbits, basic_stabilizers

strong_presentation()

Return a strong finite presentation of \(G\). The generators of the returned group are in the same order as the strong generators of \(G\).

The algorithm is based on Sims’ Verify algorithm described in [1], Chapter 6.

Examples

>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> P = DihedralGroup(4)
>>> G = P.strong_presentation()
>>> P.order() == G.order()
True

See also

presentation, _verify

subgroup(gens)

Return the subgroup generated by \(gens\) which is a list of elements of the group

subgroup_search(prop, base=None, strong_gens=None, tests=None, init_subgroup=None)

Find the subgroup of all elements satisfying the property prop.

This is done by a depth-first 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 or False. It is assumed that all group elements satisfying prop 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 that tests[l](g) returns False if the element g is known not to satisfy prop base on where g sends the first l + 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 base base.

Examples

>>> from sympy.combinatorics.named_groups import (SymmetricGroup,
... AlternatingGroup)
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> from sympy.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 lengthy and complicated and will require some careful attention. The implementation is described in [1], pp. 114-117, 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.

sylow_subgroup(p)

Return a p-Sylow subgroup of the group.

The algorithm is described in [1], Chapter 4, Section 7

Examples

>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> from sympy.combinatorics.named_groups import AlternatingGroup

>>> D = DihedralGroup(6)
>>> S = D.sylow_subgroup(2)
>>> S.order()
4
>>> G = SymmetricGroup(6)
>>> S = G.sylow_subgroup(5)
>>> S.order()
5

>>> G1 = AlternatingGroup(3)
>>> G2 = AlternatingGroup(5)
>>> G3 = AlternatingGroup(9)

>>> S1 = G1.sylow_subgroup(3)
>>> S2 = G2.sylow_subgroup(3)
>>> S3 = G3.sylow_subgroup(3)

>>> len1 = len(S1.lower_central_series())
>>> len2 = len(S2.lower_central_series())
>>> len3 = len(S3.lower_central_series())

>>> len1 == len2
True
>>> len1 < len3
True

transitivity_degree

Compute the degree of transitivity of the group.

A permutation group \(G\) acting on \(\Omega = \{0, 1, ..., n-1\}\) is k-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 exists \(g\in G\) such that \(g(a_1)=b_1, g(a_2)=b_2, ..., g(a_k)=b_k\) The degree of transitivity of \(G\) is the maximum k such that \(G\) is k-fold transitive. ([8])

Examples

>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> from sympy.combinatorics.permutations import Permutation
>>> a = Permutation([1, 2, 0])
>>> b = Permutation([1, 0, 2])
>>> G = PermutationGroup([a, b])
>>> G.transitivity_degree
3

See also

is_transitive, orbit