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