1from sympy.combinatorics.permutations import Permutation
2from sympy.core.symbol import symbols
3from sympy.matrices import Matrix
4from sympy.utilities.iterables import variations, rotate_left
5
6
7def symmetric(n):
8    """
9    Generates the symmetric group of order n, Sn.
10
11    Examples
12    ========
13
14    >>> from sympy.combinatorics.generators import symmetric
15    >>> list(symmetric(3))
16    [(2), (1 2), (2)(0 1), (0 1 2), (0 2 1), (0 2)]
17    """
18    for perm in variations(list(range(n)), n):
19        yield Permutation(perm)
20
21
22def cyclic(n):
23    """
24    Generates the cyclic group of order n, Cn.
25
26    Examples
27    ========
28
29    >>> from sympy.combinatorics.generators import cyclic
30    >>> list(cyclic(5))
31    [(4), (0 1 2 3 4), (0 2 4 1 3),
32     (0 3 1 4 2), (0 4 3 2 1)]
33
34    See Also
35    ========
36
37    dihedral
38    """
39    gen = list(range(n))
40    for i in range(n):
41        yield Permutation(gen)
42        gen = rotate_left(gen, 1)
43
44
45def alternating(n):
46    """
47    Generates the alternating group of order n, An.
48
49    Examples
50    ========
51
52    >>> from sympy.combinatorics.generators import alternating
53    >>> list(alternating(3))
54    [(2), (0 1 2), (0 2 1)]
55    """
56    for perm in variations(list(range(n)), n):
57        p = Permutation(perm)
58        if p.is_even:
59            yield p
60
61
62def dihedral(n):
63    """
64    Generates the dihedral group of order 2n, Dn.
65
66    The result is given as a subgroup of Sn, except for the special cases n=1
67    (the group S2) and n=2 (the Klein 4-group) where that's not possible
68    and embeddings in S2 and S4 respectively are given.
69
70    Examples
71    ========
72
73    >>> from sympy.combinatorics.generators import dihedral
74    >>> list(dihedral(3))
75    [(2), (0 2), (0 1 2), (1 2), (0 2 1), (2)(0 1)]
76
77    See Also
78    ========
79
80    cyclic
81    """
82    if n == 1:
83        yield Permutation([0, 1])
84        yield Permutation([1, 0])
85    elif n == 2:
86        yield Permutation([0, 1, 2, 3])
87        yield Permutation([1, 0, 3, 2])
88        yield Permutation([2, 3, 0, 1])
89        yield Permutation([3, 2, 1, 0])
90    else:
91        gen = list(range(n))
92        for i in range(n):
93            yield Permutation(gen)
94            yield Permutation(gen[::-1])
95            gen = rotate_left(gen, 1)
96
97
98def rubik_cube_generators():
99    """Return the permutations of the 3x3 Rubik's cube, see
100    http://www.gap-system.org/Doc/Examples/rubik.html
101    """
102    a = [
103        [(1, 3, 8, 6), (2, 5, 7, 4), (9, 33, 25, 17), (10, 34, 26, 18),
104         (11, 35, 27, 19)],
105        [(9, 11, 16, 14), (10, 13, 15, 12), (1, 17, 41, 40), (4, 20, 44, 37),
106         (6, 22, 46, 35)],
107        [(17, 19, 24, 22), (18, 21, 23, 20), (6, 25, 43, 16), (7, 28, 42, 13),
108         (8, 30, 41, 11)],
109        [(25, 27, 32, 30), (26, 29, 31, 28), (3, 38, 43, 19), (5, 36, 45, 21),
110         (8, 33, 48, 24)],
111        [(33, 35, 40, 38), (34, 37, 39, 36), (3, 9, 46, 32), (2, 12, 47, 29),
112         (1, 14, 48, 27)],
113        [(41, 43, 48, 46), (42, 45, 47, 44), (14, 22, 30, 38),
114         (15, 23, 31, 39), (16, 24, 32, 40)]
115    ]
116    return [Permutation([[i - 1 for i in xi] for xi in x], size=48) for x in a]
117
118
119def rubik(n):
120    """Return permutations for an nxn Rubik's cube.
121
122    Permutations returned are for rotation of each of the slice
123    from the face up to the last face for each of the 3 sides (in this order):
124    front, right and bottom. Hence, the first n - 1 permutations are for the
125    slices from the front.
126    """
127
128    if n < 2:
129        raise ValueError('dimension of cube must be > 1')
130
131    # 1-based reference to rows and columns in Matrix
132    def getr(f, i):
133        return faces[f].col(n - i)
134
135    def getl(f, i):
136        return faces[f].col(i - 1)
137
138    def getu(f, i):
139        return faces[f].row(i - 1)
140
141    def getd(f, i):
142        return faces[f].row(n - i)
143
144    def setr(f, i, s):
145        faces[f][:, n - i] = Matrix(n, 1, s)
146
147    def setl(f, i, s):
148        faces[f][:, i - 1] = Matrix(n, 1, s)
149
150    def setu(f, i, s):
151        faces[f][i - 1, :] = Matrix(1, n, s)
152
153    def setd(f, i, s):
154        faces[f][n - i, :] = Matrix(1, n, s)
155
156    # motion of a single face
157    def cw(F, r=1):
158        for _ in range(r):
159            face = faces[F]
160            rv = []
161            for c in range(n):
162                for r in range(n - 1, -1, -1):
163                    rv.append(face[r, c])
164            faces[F] = Matrix(n, n, rv)
165
166    def ccw(F):
167        cw(F, 3)
168
169    # motion of plane i from the F side;
170    # fcw(0) moves the F face, fcw(1) moves the plane
171    # just behind the front face, etc...
172    def fcw(i, r=1):
173        for _ in range(r):
174            if i == 0:
175                cw(F)
176            i += 1
177            temp = getr(L, i)
178            setr(L, i, list(getu(D, i)))
179            setu(D, i, list(reversed(getl(R, i))))
180            setl(R, i, list(getd(U, i)))
181            setd(U, i, list(reversed(temp)))
182            i -= 1
183
184    def fccw(i):
185        fcw(i, 3)
186
187    # motion of the entire cube from the F side
188    def FCW(r=1):
189        for _ in range(r):
190            cw(F)
191            ccw(B)
192            cw(U)
193            t = faces[U]
194            cw(L)
195            faces[U] = faces[L]
196            cw(D)
197            faces[L] = faces[D]
198            cw(R)
199            faces[D] = faces[R]
200            faces[R] = t
201
202    def FCCW():
203        FCW(3)
204
205    # motion of the entire cube from the U side
206    def UCW(r=1):
207        for _ in range(r):
208            cw(U)
209            ccw(D)
210            t = faces[F]
211            faces[F] = faces[R]
212            faces[R] = faces[B]
213            faces[B] = faces[L]
214            faces[L] = t
215
216    def UCCW():
217        UCW(3)
218
219    # defining the permutations for the cube
220
221    U, F, R, B, L, D = names = symbols('U, F, R, B, L, D')
222
223    # the faces are represented by nxn matrices
224    faces = {}
225    count = 0
226    for fi in range(6):
227        f = []
228        for a in range(n**2):
229            f.append(count)
230            count += 1
231        faces[names[fi]] = Matrix(n, n, f)
232
233    # this will either return the value of the current permutation
234    # (show != 1) or else append the permutation to the group, g
235    def perm(show=0):
236        # add perm to the list of perms
237        p = []
238        for f in names:
239            p.extend(faces[f])
240        if show:
241            return p
242        g.append(Permutation(p))
243
244    g = []  # container for the group's permutations
245    I = list(range(6*n**2))  # the identity permutation used for checking
246
247    # define permutations corresponding to cw rotations of the planes
248    # up TO the last plane from that direction; by not including the
249    # last plane, the orientation of the cube is maintained.
250
251    # F slices
252    for i in range(n - 1):
253        fcw(i)
254        perm()
255        fccw(i)  # restore
256    assert perm(1) == I
257
258    # R slices
259    # bring R to front
260    UCW()
261    for i in range(n - 1):
262        fcw(i)
263        # put it back in place
264        UCCW()
265        # record
266        perm()
267        # restore
268        # bring face to front
269        UCW()
270        fccw(i)
271    # restore
272    UCCW()
273    assert perm(1) == I
274
275    # D slices
276    # bring up bottom
277    FCW()
278    UCCW()
279    FCCW()
280    for i in range(n - 1):
281        # turn strip
282        fcw(i)
283        # put bottom back on the bottom
284        FCW()
285        UCW()
286        FCCW()
287        # record
288        perm()
289        # restore
290        # bring up bottom
291        FCW()
292        UCCW()
293        FCCW()
294        # turn strip
295        fccw(i)
296    # put bottom back on the bottom
297    FCW()
298    UCW()
299    FCCW()
300    assert perm(1) == I
301
302    return g
303