Coverage for /usr/lib/python3/dist-packages/sympy/combinatorics/generators.py: 7%

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(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(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 https://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