/

# Source code for sympy.combinatorics.named_groups

from __future__ import print_function, division

from sympy.combinatorics.perm_groups import PermutationGroup
from sympy.combinatorics.group_constructs import DirectProduct
from sympy.combinatorics.permutations import Permutation

_af_new = Permutation._af_new

[docs]def AbelianGroup(*cyclic_orders):
"""
Returns the direct product of cyclic groups with the given orders.

According to the structure theorem for finite abelian groups (),
every finite abelian group can be written as the direct product of finitely
many cyclic groups.
 http://groupprops.subwiki.org/wiki/Structure_theorem_for_finitely_generated_abelian_groups

Examples
========

>>> from sympy.combinatorics import Permutation
>>> Permutation.print_cyclic = True
>>> from sympy.combinatorics.named_groups import AbelianGroup
>>> AbelianGroup(3, 4)
PermutationGroup([
Permutation(6)(0, 1, 2),
Permutation(3, 4, 5, 6)])
>>> _.is_group()
False

See Also
========
DirectProduct
"""
groups = []
degree = 0
order = 1
for size in cyclic_orders:
degree += size
order *= size
groups.append(CyclicGroup(size))
G = DirectProduct(*groups)
G._is_abelian = True
G._degree = degree
G._order = order

return G

[docs]def AlternatingGroup(n):
"""
Generates the alternating group on n elements as a permutation group.

For n > 2, the generators taken are (0 1 2), (0 1 2 ... n-1) for
n odd
and (0 1 2), (1 2 ... n-1) for n even (See , p.31, ex.6.9.).
After the group is generated, some of its basic properties are set.
The cases n = 1, 2 are handled separately.

Examples
========

>>> from sympy.combinatorics.named_groups import AlternatingGroup
>>> G = AlternatingGroup(4)
>>> G.is_group()
False
>>> a = list(G.generate_dimino())
>>> len(a)
12
>>> all(perm.is_even for perm in a)
True

See Also
========

SymmetricGroup, CyclicGroup, DihedralGroup

References
==========

 Armstrong, M. "Groups and Symmetry"

"""
# small cases are special
if n in (1, 2):
return PermutationGroup([Permutation()])

a = list(range(n))
a, a, a = a, a, a
gen1 = a
if n % 2:
a = list(range(1, n))
a.append(0)
gen2 = a
else:
a = list(range(2, n))
a.append(1)
a.insert(0, 0)
gen2 = a
gens = [gen1, gen2]
if gen1 == gen2:
gens = gens[:1]
G = PermutationGroup([_af_new(a) for a in gens], dups=False)

if n < 4:
G._is_abelian = True
G._is_nilpotent = True
else:
G._is_abelian = False
G._is_nilpotent = False
if n < 5:
G._is_solvable = True
else:
G._is_solvable = False
G._degree = n
G._is_transitive = True
G._is_alt = True
return G

[docs]def CyclicGroup(n):
"""
Generates the cyclic group of order n as a permutation group.

The generator taken is the n-cycle (0 1 2 ... n-1)
(in cycle notation). After the group is generated, some of its basic
properties are set.

Examples
========

>>> from sympy.combinatorics.named_groups import CyclicGroup
>>> G = CyclicGroup(6)
>>> G.is_group()
False
>>> G.order()
6
>>> list(G.generate_schreier_sims(af=True))
[[0, 1, 2, 3, 4, 5], [1, 2, 3, 4, 5, 0], [2, 3, 4, 5, 0, 1],
[3, 4, 5, 0, 1, 2], [4, 5, 0, 1, 2, 3], [5, 0, 1, 2, 3, 4]]

See Also
========

SymmetricGroup, DihedralGroup, AlternatingGroup

"""
a = list(range(1, n))
a.append(0)
gen = _af_new(a)
G = PermutationGroup([gen])

G._is_abelian = True
G._is_nilpotent = True
G._is_solvable = True
G._degree = n
G._is_transitive = True
G._order = n
return G

[docs]def DihedralGroup(n):
r"""
Generates the dihedral group D_n as a permutation group.

The dihedral group D_n is the group of symmetries of the regular
n-gon. The generators taken are the n-cycle a = (0 1 2 ... n-1)
(a rotation of the n-gon) and b = (0 n-1)(1 n-2)...
(a reflection of the n-gon) in cycle rotation. It is easy to see that
these satisfy a**n = b**2 = 1 and bab = ~a so they indeed generate
D_n (See ). After the group is generated, some of its basic properties
are set.

Examples
========

>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> G = DihedralGroup(5)
>>> G.is_group()
False
>>> a = list(G.generate_dimino())
>>> [perm.cyclic_form for perm in a]
[[], [[0, 1, 2, 3, 4]], [[0, 2, 4, 1, 3]],
[[0, 3, 1, 4, 2]], [[0, 4, 3, 2, 1]], [[0, 4], [1, 3]],
[[1, 4], [2, 3]], [[0, 1], [2, 4]], [[0, 2], [3, 4]],
[[0, 3], [1, 2]]]

See Also
========

SymmetricGroup, CyclicGroup, AlternatingGroup

References
==========

 http://en.wikipedia.org/wiki/Dihedral_group

"""
# small cases are special
if n == 1:
return PermutationGroup([Permutation([1, 0])])
if n == 2:
return PermutationGroup([Permutation([1, 0, 3, 2]),
Permutation([2, 3, 0, 1]), Permutation([3, 2, 1, 0])])

a = list(range(1, n))
a.append(0)
gen1 = _af_new(a)
a = list(range(n))
a.reverse()
gen2 = _af_new(a)
G = PermutationGroup([gen1, gen2])
# if n is a power of 2, group is nilpotent
if n & (n-1) == 0:
G._is_nilpotent = True
else:
G._is_nilpotent = False
G._is_abelian = False
G._is_solvable = True
G._degree = n
G._is_transitive = True
G._order = 2*n
return G

[docs]def SymmetricGroup(n):
"""
Generates the symmetric group on n elements as a permutation group.

The generators taken are the n-cycle
(0 1 2 ... n-1) and the transposition (0 1) (in cycle notation).
(See ). After the group is generated, some of its basic properties
are set.

Examples
========

>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> G = SymmetricGroup(4)
>>> G.is_group()
False
>>> G.order()
24
>>> list(G.generate_schreier_sims(af=True))
[[0, 1, 2, 3], [1, 2, 3, 0], [2, 3, 0, 1], [3, 1, 2, 0], [0, 2, 3, 1],
[1, 3, 0, 2], [2, 0, 1, 3], [3, 2, 0, 1], [0, 3, 1, 2], [1, 0, 2, 3],
[2, 1, 3, 0], [3, 0, 1, 2], [0, 1, 3, 2], [1, 2, 0, 3], [2, 3, 1, 0],
[3, 1, 0, 2], [0, 2, 1, 3], [1, 3, 2, 0], [2, 0, 3, 1], [3, 2, 1, 0],
[0, 3, 2, 1], [1, 0, 3, 2], [2, 1, 0, 3], [3, 0, 2, 1]]

See Also
========

CyclicGroup, DihedralGroup, AlternatingGroup

References
==========

 http://en.wikipedia.org/wiki/Symmetric_group#Generators_and_relations

"""
if n == 1:
G = PermutationGroup([Permutation()])
elif n == 2:
G = PermutationGroup([Permutation([1, 0])])
else:
a = list(range(1, n))
a.append(0)
gen1 = _af_new(a)
a = list(range(n))
a, a = a, a
gen2 = _af_new(a)
G = PermutationGroup([gen1, gen2])
if n < 3:
G._is_abelian = True
G._is_nilpotent = True
else:
G._is_abelian = False
G._is_nilpotent = False
if n < 5:
G._is_solvable = True
else:
G._is_solvable = False
G._degree = n
G._is_transitive = True
G._is_sym = True
return G

def RubikGroup(n):
"""Return a group of Rubik's cube generators.
>>> from sympy.combinatorics.named_groups import RubikGroup
>>> RubikGroup(2).is_group()
False
"""
from sympy.combinatorics.generators import rubik
assert n > 1
return PermutationGroup(rubik(n))