Coverage for /usr/lib/python3/dist-packages/sympy/combinatorics/named_groups.py: 10%

1from sympy.combinatorics.group_constructs import DirectProduct 

2from sympy.combinatorics.perm_groups import PermutationGroup 

3from sympy.combinatorics.permutations import Permutation 

4 

5_af_new = Permutation._af_new 

6 

7 

8def AbelianGroup(*cyclic_orders): 

9 """ 

10 Returns the direct product of cyclic groups with the given orders. 

11 

12 Explanation 

13 =========== 

14 

15 According to the structure theorem for finite abelian groups ([1]), 

16 every finite abelian group can be written as the direct product of 

17 finitely many cyclic groups. 

18 

19 Examples 

20 ======== 

21 

22 >>> from sympy.combinatorics.named_groups import AbelianGroup 

23 >>> AbelianGroup(3, 4) 

24 PermutationGroup([ 

25 (6)(0 1 2), 

26 (3 4 5 6)]) 

27 >>> _.is_group 

28 True 

29 

30 See Also 

31 ======== 

32 

33 DirectProduct 

34 

35 References 

36 ========== 

37 

38 .. [1] https://groupprops.subwiki.org/wiki/Structure_theorem_for_finitely_generated_abelian_groups 

39 

40 """ 

41 groups = [] 

42 degree = 0 

43 order = 1 

44 for size in cyclic_orders: 

45 degree += size 

46 order *= size 

47 groups.append(CyclicGroup(size)) 

48 G = DirectProduct(*groups) 

49 G._is_abelian = True 

50 G._degree = degree 

51 G._order = order 

52 

53 return G 

54 

55 

56def AlternatingGroup(n): 

57 """ 

58 Generates the alternating group on ``n`` elements as a permutation group. 

59 

60 Explanation 

61 =========== 

62 

63 For ``n > 2``, the generators taken are ``(0 1 2), (0 1 2 ... n-1)`` for 

64 ``n`` odd 

65 and ``(0 1 2), (1 2 ... n-1)`` for ``n`` even (See [1], p.31, ex.6.9.). 

66 After the group is generated, some of its basic properties are set. 

67 The cases ``n = 1, 2`` are handled separately. 

68 

69 Examples 

70 ======== 

71 

72 >>> from sympy.combinatorics.named_groups import AlternatingGroup 

73 >>> G = AlternatingGroup(4) 

74 >>> G.is_group 

75 True 

76 >>> a = list(G.generate_dimino()) 

77 >>> len(a) 

78 12 

79 >>> all(perm.is_even for perm in a) 

80 True 

81 

82 See Also 

83 ======== 

84 

85 SymmetricGroup, CyclicGroup, DihedralGroup 

86 

87 References 

88 ========== 

89 

90 .. [1] Armstrong, M. "Groups and Symmetry" 

91 

92 """ 

93 # small cases are special 

94 if n in (1, 2): 

95 return PermutationGroup([Permutation([0])]) 

96 

97 a = list(range(n)) 

98 a[0], a[1], a[2] = a[1], a[2], a[0] 

99 gen1 = a 

100 if n % 2: 

101 a = list(range(1, n)) 

102 a.append(0) 

103 gen2 = a 

104 else: 

105 a = list(range(2, n)) 

106 a.append(1) 

107 a.insert(0, 0) 

108 gen2 = a 

109 gens = [gen1, gen2] 

110 if gen1 == gen2: 

111 gens = gens[:1] 

112 G = PermutationGroup([_af_new(a) for a in gens], dups=False) 

113 

114 set_alternating_group_properties(G, n, n) 

115 G._is_alt = True 

116 return G 

117 

118 

119def set_alternating_group_properties(G, n, degree): 

120 """Set known properties of an alternating group. """ 

121 if n < 4: 

122 G._is_abelian = True 

123 G._is_nilpotent = True 

124 else: 

125 G._is_abelian = False 

126 G._is_nilpotent = False 

127 if n < 5: 

128 G._is_solvable = True 

129 else: 

130 G._is_solvable = False 

131 G._degree = degree 

132 G._is_transitive = True 

133 G._is_dihedral = False 

134 

135 

136def CyclicGroup(n): 

137 """ 

138 Generates the cyclic group of order ``n`` as a permutation group. 

139 

140 Explanation 

141 =========== 

142 

143 The generator taken is the ``n``-cycle ``(0 1 2 ... n-1)`` 

144 (in cycle notation). After the group is generated, some of its basic 

145 properties are set. 

146 

147 Examples 

148 ======== 

149 

150 >>> from sympy.combinatorics.named_groups import CyclicGroup 

151 >>> G = CyclicGroup(6) 

152 >>> G.is_group 

153 True 

154 >>> G.order() 

155 6 

156 >>> list(G.generate_schreier_sims(af=True)) 

157 [[0, 1, 2, 3, 4, 5], [1, 2, 3, 4, 5, 0], [2, 3, 4, 5, 0, 1], 

158 [3, 4, 5, 0, 1, 2], [4, 5, 0, 1, 2, 3], [5, 0, 1, 2, 3, 4]] 

159 

160 See Also 

161 ======== 

162 

163 SymmetricGroup, DihedralGroup, AlternatingGroup 

164 

165 """ 

166 a = list(range(1, n)) 

167 a.append(0) 

168 gen = _af_new(a) 

169 G = PermutationGroup([gen]) 

170 

171 G._is_abelian = True 

172 G._is_nilpotent = True 

173 G._is_solvable = True 

174 G._degree = n 

175 G._is_transitive = True 

176 G._order = n 

177 G._is_dihedral = (n == 2) 

178 return G 

179 

180 

181def DihedralGroup(n): 

182 r""" 

183 Generates the dihedral group `D_n` as a permutation group. 

184 

185 Explanation 

186 =========== 

187 

188 The dihedral group `D_n` is the group of symmetries of the regular 

189 ``n``-gon. The generators taken are the ``n``-cycle ``a = (0 1 2 ... n-1)`` 

190 (a rotation of the ``n``-gon) and ``b = (0 n-1)(1 n-2)...`` 

191 (a reflection of the ``n``-gon) in cycle rotation. It is easy to see that 

192 these satisfy ``a**n = b**2 = 1`` and ``bab = ~a`` so they indeed generate 

193 `D_n` (See [1]). After the group is generated, some of its basic properties 

194 are set. 

195 

196 Examples 

197 ======== 

198 

199 >>> from sympy.combinatorics.named_groups import DihedralGroup 

200 >>> G = DihedralGroup(5) 

201 >>> G.is_group 

202 True 

203 >>> a = list(G.generate_dimino()) 

204 >>> [perm.cyclic_form for perm in a] 

205 [[], [[0, 1, 2, 3, 4]], [[0, 2, 4, 1, 3]], 

206 [[0, 3, 1, 4, 2]], [[0, 4, 3, 2, 1]], [[0, 4], [1, 3]], 

207 [[1, 4], [2, 3]], [[0, 1], [2, 4]], [[0, 2], [3, 4]], 

208 [[0, 3], [1, 2]]] 

209 

210 See Also 

211 ======== 

212 

213 SymmetricGroup, CyclicGroup, AlternatingGroup 

214 

215 References 

216 ========== 

217 

218 .. [1] https://en.wikipedia.org/wiki/Dihedral_group 

219 

220 """ 

221 # small cases are special 

222 if n == 1: 

223 return PermutationGroup([Permutation([1, 0])]) 

224 if n == 2: 

225 return PermutationGroup([Permutation([1, 0, 3, 2]), 

226 Permutation([2, 3, 0, 1]), Permutation([3, 2, 1, 0])]) 

227 

228 a = list(range(1, n)) 

229 a.append(0) 

230 gen1 = _af_new(a) 

231 a = list(range(n)) 

232 a.reverse() 

233 gen2 = _af_new(a) 

234 G = PermutationGroup([gen1, gen2]) 

235 # if n is a power of 2, group is nilpotent 

236 if n & (n-1) == 0: 

237 G._is_nilpotent = True 

238 else: 

239 G._is_nilpotent = False 

240 G._is_dihedral = True 

241 G._is_abelian = False 

242 G._is_solvable = True 

243 G._degree = n 

244 G._is_transitive = True 

245 G._order = 2*n 

246 return G 

247 

248 

249def SymmetricGroup(n): 

250 """ 

251 Generates the symmetric group on ``n`` elements as a permutation group. 

252 

253 Explanation 

254 =========== 

255 

256 The generators taken are the ``n``-cycle 

257 ``(0 1 2 ... n-1)`` and the transposition ``(0 1)`` (in cycle notation). 

258 (See [1]). After the group is generated, some of its basic properties 

259 are set. 

260 

261 Examples 

262 ======== 

263 

264 >>> from sympy.combinatorics.named_groups import SymmetricGroup 

265 >>> G = SymmetricGroup(4) 

266 >>> G.is_group 

267 True 

268 >>> G.order() 

269 24 

270 >>> list(G.generate_schreier_sims(af=True)) 

271 [[0, 1, 2, 3], [1, 2, 3, 0], [2, 3, 0, 1], [3, 1, 2, 0], [0, 2, 3, 1], 

272 [1, 3, 0, 2], [2, 0, 1, 3], [3, 2, 0, 1], [0, 3, 1, 2], [1, 0, 2, 3], 

273 [2, 1, 3, 0], [3, 0, 1, 2], [0, 1, 3, 2], [1, 2, 0, 3], [2, 3, 1, 0], 

274 [3, 1, 0, 2], [0, 2, 1, 3], [1, 3, 2, 0], [2, 0, 3, 1], [3, 2, 1, 0], 

275 [0, 3, 2, 1], [1, 0, 3, 2], [2, 1, 0, 3], [3, 0, 2, 1]] 

276 

277 See Also 

278 ======== 

279 

280 CyclicGroup, DihedralGroup, AlternatingGroup 

281 

282 References 

283 ========== 

284 

285 .. [1] https://en.wikipedia.org/wiki/Symmetric_group#Generators_and_relations 

286 

287 """ 

288 if n == 1: 

289 G = PermutationGroup([Permutation([0])]) 

290 elif n == 2: 

291 G = PermutationGroup([Permutation([1, 0])]) 

292 else: 

293 a = list(range(1, n)) 

294 a.append(0) 

295 gen1 = _af_new(a) 

296 a = list(range(n)) 

297 a[0], a[1] = a[1], a[0] 

298 gen2 = _af_new(a) 

299 G = PermutationGroup([gen1, gen2]) 

300 set_symmetric_group_properties(G, n, n) 

301 G._is_sym = True 

302 return G 

303 

304 

305def set_symmetric_group_properties(G, n, degree): 

306 """Set known properties of a symmetric group. """ 

307 if n < 3: 

308 G._is_abelian = True 

309 G._is_nilpotent = True 

310 else: 

311 G._is_abelian = False 

312 G._is_nilpotent = False 

313 if n < 5: 

314 G._is_solvable = True 

315 else: 

316 G._is_solvable = False 

317 G._degree = degree 

318 G._is_transitive = True 

319 G._is_dihedral = (n in [2, 3]) # cf Landau's func and Stirling's approx 

320 

321 

322def RubikGroup(n): 

323 """Return a group of Rubik's cube generators 

324 

325 >>> from sympy.combinatorics.named_groups import RubikGroup 

326 >>> RubikGroup(2).is_group 

327 True 

328 """ 

329 from sympy.combinatorics.generators import rubik 

330 if n <= 1: 

331 raise ValueError("Invalid cube. n has to be greater than 1") 

332 return PermutationGroup(rubik(n))