Coverage for /usr/lib/python3/dist-packages/sympy/combinatorics/polyhedron.py: 42%

1from sympy.combinatorics import Permutation as Perm 

2from sympy.combinatorics.perm_groups import PermutationGroup 

3from sympy.core import Basic, Tuple, default_sort_key 

4from sympy.sets import FiniteSet 

5from sympy.utilities.iterables import (minlex, unflatten, flatten) 

6from sympy.utilities.misc import as_int 

7 

8rmul = Perm.rmul 

9 

10 

11class Polyhedron(Basic): 

12 """ 

13 Represents the polyhedral symmetry group (PSG). 

14 

15 Explanation 

16 =========== 

17 

18 The PSG is one of the symmetry groups of the Platonic solids. 

19 There are three polyhedral groups: the tetrahedral group 

20 of order 12, the octahedral group of order 24, and the 

21 icosahedral group of order 60. 

22 

23 All doctests have been given in the docstring of the 

24 constructor of the object. 

25 

26 References 

27 ========== 

28 

29 .. [1] https://mathworld.wolfram.com/PolyhedralGroup.html 

30 

31 """ 

32 _edges = None 

33 

34 def __new__(cls, corners, faces=(), pgroup=()): 

35 """ 

36 The constructor of the Polyhedron group object. 

37 

38 Explanation 

39 =========== 

40 

41 It takes up to three parameters: the corners, faces, and 

42 allowed transformations. 

43 

44 The corners/vertices are entered as a list of arbitrary 

45 expressions that are used to identify each vertex. 

46 

47 The faces are entered as a list of tuples of indices; a tuple 

48 of indices identifies the vertices which define the face. They 

49 should be entered in a cw or ccw order; they will be standardized 

50 by reversal and rotation to be give the lowest lexical ordering. 

51 If no faces are given then no edges will be computed. 

52 

53 >>> from sympy.combinatorics.polyhedron import Polyhedron 

54 >>> Polyhedron(list('abc'), [(1, 2, 0)]).faces 

55 {(0, 1, 2)} 

56 >>> Polyhedron(list('abc'), [(1, 0, 2)]).faces 

57 {(0, 1, 2)} 

58 

59 The allowed transformations are entered as allowable permutations 

60 of the vertices for the polyhedron. Instance of Permutations 

61 (as with faces) should refer to the supplied vertices by index. 

62 These permutation are stored as a PermutationGroup. 

63 

64 Examples 

65 ======== 

66 

67 >>> from sympy.combinatorics.permutations import Permutation 

68 >>> from sympy import init_printing 

69 >>> from sympy.abc import w, x, y, z 

70 >>> init_printing(pretty_print=False, perm_cyclic=False) 

71 

72 Here we construct the Polyhedron object for a tetrahedron. 

73 

74 >>> corners = [w, x, y, z] 

75 >>> faces = [(0, 1, 2), (0, 2, 3), (0, 3, 1), (1, 2, 3)] 

76 

77 Next, allowed transformations of the polyhedron must be given. This 

78 is given as permutations of vertices. 

79 

80 Although the vertices of a tetrahedron can be numbered in 24 (4!) 

81 different ways, there are only 12 different orientations for a 

82 physical tetrahedron. The following permutations, applied once or 

83 twice, will generate all 12 of the orientations. (The identity 

84 permutation, Permutation(range(4)), is not included since it does 

85 not change the orientation of the vertices.) 

86 

87 >>> pgroup = [Permutation([[0, 1, 2], [3]]), \ 

88 Permutation([[0, 1, 3], [2]]), \ 

89 Permutation([[0, 2, 3], [1]]), \ 

90 Permutation([[1, 2, 3], [0]]), \ 

91 Permutation([[0, 1], [2, 3]]), \ 

92 Permutation([[0, 2], [1, 3]]), \ 

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

94 

95 The Polyhedron is now constructed and demonstrated: 

96 

97 >>> tetra = Polyhedron(corners, faces, pgroup) 

98 >>> tetra.size 

99 4 

100 >>> tetra.edges 

101 {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)} 

102 >>> tetra.corners 

103 (w, x, y, z) 

104 

105 It can be rotated with an arbitrary permutation of vertices, e.g. 

106 the following permutation is not in the pgroup: 

107 

108 >>> tetra.rotate(Permutation([0, 1, 3, 2])) 

109 >>> tetra.corners 

110 (w, x, z, y) 

111 

112 An allowed permutation of the vertices can be constructed by 

113 repeatedly applying permutations from the pgroup to the vertices. 

114 Here is a demonstration that applying p and p**2 for every p in 

115 pgroup generates all the orientations of a tetrahedron and no others: 

116 

117 >>> all = ( (w, x, y, z), \ 

118 (x, y, w, z), \ 

119 (y, w, x, z), \ 

120 (w, z, x, y), \ 

121 (z, w, y, x), \ 

122 (w, y, z, x), \ 

123 (y, z, w, x), \ 

124 (x, z, y, w), \ 

125 (z, y, x, w), \ 

126 (y, x, z, w), \ 

127 (x, w, z, y), \ 

128 (z, x, w, y) ) 

129 

130 >>> got = [] 

131 >>> for p in (pgroup + [p**2 for p in pgroup]): 

132 ... h = Polyhedron(corners) 

133 ... h.rotate(p) 

134 ... got.append(h.corners) 

135 ... 

136 >>> set(got) == set(all) 

137 True 

138 

139 The make_perm method of a PermutationGroup will randomly pick 

140 permutations, multiply them together, and return the permutation that 

141 can be applied to the polyhedron to give the orientation produced 

142 by those individual permutations. 

143 

144 Here, 3 permutations are used: 

145 

146 >>> tetra.pgroup.make_perm(3) # doctest: +SKIP 

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

148 

149 To select the permutations that should be used, supply a list 

150 of indices to the permutations in pgroup in the order they should 

151 be applied: 

152 

153 >>> use = [0, 0, 2] 

154 >>> p002 = tetra.pgroup.make_perm(3, use) 

155 >>> p002 

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

157 

158 

159 Apply them one at a time: 

160 

161 >>> tetra.reset() 

162 >>> for i in use: 

163 ... tetra.rotate(pgroup[i]) 

164 ... 

165 >>> tetra.vertices 

166 (x, w, z, y) 

167 >>> sequentially = tetra.vertices 

168 

169 Apply the composite permutation: 

170 

171 >>> tetra.reset() 

172 >>> tetra.rotate(p002) 

173 >>> tetra.corners 

174 (x, w, z, y) 

175 >>> tetra.corners in all and tetra.corners == sequentially 

176 True 

177 

178 Notes 

179 ===== 

180 

181 Defining permutation groups 

182 --------------------------- 

183 

184 It is not necessary to enter any permutations, nor is necessary to 

185 enter a complete set of transformations. In fact, for a polyhedron, 

186 all configurations can be constructed from just two permutations. 

187 For example, the orientations of a tetrahedron can be generated from 

188 an axis passing through a vertex and face and another axis passing 

189 through a different vertex or from an axis passing through the 

190 midpoints of two edges opposite of each other. 

191 

192 For simplicity of presentation, consider a square -- 

193 not a cube -- with vertices 1, 2, 3, and 4: 

194 

195 1-----2 We could think of axes of rotation being: 

196 | | 1) through the face 

197 | | 2) from midpoint 1-2 to 3-4 or 1-3 to 2-4 

198 3-----4 3) lines 1-4 or 2-3 

199 

200 

201 To determine how to write the permutations, imagine 4 cameras, 

202 one at each corner, labeled A-D: 

203 

204 A B A B 

205 1-----2 1-----3 vertex index: 

206 | | | | 1 0 

207 | | | | 2 1 

208 3-----4 2-----4 3 2 

209 C D C D 4 3 

210 

211 original after rotation 

212 along 1-4 

213 

214 A diagonal and a face axis will be chosen for the "permutation group" 

215 from which any orientation can be constructed. 

216 

217 >>> pgroup = [] 

218 

219 Imagine a clockwise rotation when viewing 1-4 from camera A. The new 

220 orientation is (in camera-order): 1, 3, 2, 4 so the permutation is 

221 given using the *indices* of the vertices as: 

222 

223 >>> pgroup.append(Permutation((0, 2, 1, 3))) 

224 

225 Now imagine rotating clockwise when looking down an axis entering the 

226 center of the square as viewed. The new camera-order would be 

227 3, 1, 4, 2 so the permutation is (using indices): 

228 

229 >>> pgroup.append(Permutation((2, 0, 3, 1))) 

230 

231 The square can now be constructed: 

232 ** use real-world labels for the vertices, entering them in 

233 camera order 

234 ** for the faces we use zero-based indices of the vertices 

235 in *edge-order* as the face is traversed; neither the 

236 direction nor the starting point matter -- the faces are 

237 only used to define edges (if so desired). 

238 

239 >>> square = Polyhedron((1, 2, 3, 4), [(0, 1, 3, 2)], pgroup) 

240 

241 To rotate the square with a single permutation we can do: 

242 

243 >>> square.rotate(square.pgroup[0]) 

244 >>> square.corners 

245 (1, 3, 2, 4) 

246 

247 To use more than one permutation (or to use one permutation more 

248 than once) it is more convenient to use the make_perm method: 

249 

250 >>> p011 = square.pgroup.make_perm([0, 1, 1]) # diag flip + 2 rotations 

251 >>> square.reset() # return to initial orientation 

252 >>> square.rotate(p011) 

253 >>> square.corners 

254 (4, 2, 3, 1) 

255 

256 Thinking outside the box 

257 ------------------------ 

258 

259 Although the Polyhedron object has a direct physical meaning, it 

260 actually has broader application. In the most general sense it is 

261 just a decorated PermutationGroup, allowing one to connect the 

262 permutations to something physical. For example, a Rubik's cube is 

263 not a proper polyhedron, but the Polyhedron class can be used to 

264 represent it in a way that helps to visualize the Rubik's cube. 

265 

266 >>> from sympy import flatten, unflatten, symbols 

267 >>> from sympy.combinatorics import RubikGroup 

268 >>> facelets = flatten([symbols(s+'1:5') for s in 'UFRBLD']) 

269 >>> def show(): 

270 ... pairs = unflatten(r2.corners, 2) 

271 ... print(pairs[::2]) 

272 ... print(pairs[1::2]) 

273 ... 

274 >>> r2 = Polyhedron(facelets, pgroup=RubikGroup(2)) 

275 >>> show() 

276 [(U1, U2), (F1, F2), (R1, R2), (B1, B2), (L1, L2), (D1, D2)] 

277 [(U3, U4), (F3, F4), (R3, R4), (B3, B4), (L3, L4), (D3, D4)] 

278 >>> r2.rotate(0) # cw rotation of F 

279 >>> show() 

280 [(U1, U2), (F3, F1), (U3, R2), (B1, B2), (L1, D1), (R3, R1)] 

281 [(L4, L2), (F4, F2), (U4, R4), (B3, B4), (L3, D2), (D3, D4)] 

282 

283 Predefined Polyhedra 

284 ==================== 

285 

286 For convenience, the vertices and faces are defined for the following 

287 standard solids along with a permutation group for transformations. 

288 When the polyhedron is oriented as indicated below, the vertices in 

289 a given horizontal plane are numbered in ccw direction, starting from 

290 the vertex that will give the lowest indices in a given face. (In the 

291 net of the vertices, indices preceded by "-" indicate replication of 

292 the lhs index in the net.) 

293 

294 tetrahedron, tetrahedron_faces 

295 ------------------------------ 

296 

297 4 vertices (vertex up) net: 

298 

299 0 0-0 

300 1 2 3-1 

301 

302 4 faces: 

303 

304 (0, 1, 2) (0, 2, 3) (0, 3, 1) (1, 2, 3) 

305 

306 cube, cube_faces 

307 ---------------- 

308 

309 8 vertices (face up) net: 

310 

311 0 1 2 3-0 

312 4 5 6 7-4 

313 

314 6 faces: 

315 

316 (0, 1, 2, 3) 

317 (0, 1, 5, 4) (1, 2, 6, 5) (2, 3, 7, 6) (0, 3, 7, 4) 

318 (4, 5, 6, 7) 

319 

320 octahedron, octahedron_faces 

321 ---------------------------- 

322 

323 6 vertices (vertex up) net: 

324 

325 0 0 0-0 

326 1 2 3 4-1 

327 5 5 5-5 

328 

329 8 faces: 

330 

331 (0, 1, 2) (0, 2, 3) (0, 3, 4) (0, 1, 4) 

332 (1, 2, 5) (2, 3, 5) (3, 4, 5) (1, 4, 5) 

333 

334 dodecahedron, dodecahedron_faces 

335 -------------------------------- 

336 

337 20 vertices (vertex up) net: 

338 

339 0 1 2 3 4 -0 

340 5 6 7 8 9 -5 

341 14 10 11 12 13-14 

342 15 16 17 18 19-15 

343 

344 12 faces: 

345 

346 (0, 1, 2, 3, 4) (0, 1, 6, 10, 5) (1, 2, 7, 11, 6) 

347 (2, 3, 8, 12, 7) (3, 4, 9, 13, 8) (0, 4, 9, 14, 5) 

348 (5, 10, 16, 15, 14) (6, 10, 16, 17, 11) (7, 11, 17, 18, 12) 

349 (8, 12, 18, 19, 13) (9, 13, 19, 15, 14)(15, 16, 17, 18, 19) 

350 

351 icosahedron, icosahedron_faces 

352 ------------------------------ 

353 

354 12 vertices (face up) net: 

355 

356 0 0 0 0 -0 

357 1 2 3 4 5 -1 

358 6 7 8 9 10 -6 

359 11 11 11 11 -11 

360 

361 20 faces: 

362 

363 (0, 1, 2) (0, 2, 3) (0, 3, 4) 

364 (0, 4, 5) (0, 1, 5) (1, 2, 6) 

365 (2, 3, 7) (3, 4, 8) (4, 5, 9) 

366 (1, 5, 10) (2, 6, 7) (3, 7, 8) 

367 (4, 8, 9) (5, 9, 10) (1, 6, 10) 

368 (6, 7, 11) (7, 8, 11) (8, 9, 11) 

369 (9, 10, 11) (6, 10, 11) 

370 

371 >>> from sympy.combinatorics.polyhedron import cube 

372 >>> cube.edges 

373 {(0, 1), (0, 3), (0, 4), (1, 2), (1, 5), (2, 3), (2, 6), (3, 7), (4, 5), (4, 7), (5, 6), (6, 7)} 

374 

375 If you want to use letters or other names for the corners you 

376 can still use the pre-calculated faces: 

377 

378 >>> corners = list('abcdefgh') 

379 >>> Polyhedron(corners, cube.faces).corners 

380 (a, b, c, d, e, f, g, h) 

381 

382 References 

383 ========== 

384 

385 .. [1] www.ocf.berkeley.edu/~wwu/articles/platonicsolids.pdf 

386 

387 """ 

388 faces = [minlex(f, directed=False, key=default_sort_key) for f in faces] 

389 corners, faces, pgroup = args = \ 

390 [Tuple(*a) for a in (corners, faces, pgroup)] 

391 obj = Basic.__new__(cls, *args) 

392 obj._corners = tuple(corners) # in order given 

393 obj._faces = FiniteSet(*faces) 

394 if pgroup and pgroup[0].size != len(corners): 

395 raise ValueError("Permutation size unequal to number of corners.") 

396 # use the identity permutation if none are given 

397 obj._pgroup = PermutationGroup( 

398 pgroup or [Perm(range(len(corners)))] ) 

399 return obj 

400 

401 @property 

402 def corners(self): 

403 """ 

404 Get the corners of the Polyhedron. 

405 

406 The method ``vertices`` is an alias for ``corners``. 

407 

408 Examples 

409 ======== 

410 

411 >>> from sympy.combinatorics import Polyhedron 

412 >>> from sympy.abc import a, b, c, d 

413 >>> p = Polyhedron(list('abcd')) 

414 >>> p.corners == p.vertices == (a, b, c, d) 

415 True 

416 

417 See Also 

418 ======== 

419 

420 array_form, cyclic_form 

421 """ 

422 return self._corners 

423 vertices = corners 

424 

425 @property 

426 def array_form(self): 

427 """Return the indices of the corners. 

428 

429 The indices are given relative to the original position of corners. 

430 

431 Examples 

432 ======== 

433 

434 >>> from sympy.combinatorics.polyhedron import tetrahedron 

435 >>> tetrahedron = tetrahedron.copy() 

436 >>> tetrahedron.array_form 

437 [0, 1, 2, 3] 

438 

439 >>> tetrahedron.rotate(0) 

440 >>> tetrahedron.array_form 

441 [0, 2, 3, 1] 

442 >>> tetrahedron.pgroup[0].array_form 

443 [0, 2, 3, 1] 

444 

445 See Also 

446 ======== 

447 

448 corners, cyclic_form 

449 """ 

450 corners = list(self.args[0]) 

451 return [corners.index(c) for c in self.corners] 

452 

453 @property 

454 def cyclic_form(self): 

455 """Return the indices of the corners in cyclic notation. 

456 

457 The indices are given relative to the original position of corners. 

458 

459 See Also 

460 ======== 

461 

462 corners, array_form 

463 """ 

464 return Perm._af_new(self.array_form).cyclic_form 

465 

466 @property 

467 def size(self): 

468 """ 

469 Get the number of corners of the Polyhedron. 

470 """ 

471 return len(self._corners) 

472 

473 @property 

474 def faces(self): 

475 """ 

476 Get the faces of the Polyhedron. 

477 """ 

478 return self._faces 

479 

480 @property 

481 def pgroup(self): 

482 """ 

483 Get the permutations of the Polyhedron. 

484 """ 

485 return self._pgroup 

486 

487 @property 

488 def edges(self): 

489 """ 

490 Given the faces of the polyhedra we can get the edges. 

491 

492 Examples 

493 ======== 

494 

495 >>> from sympy.combinatorics import Polyhedron 

496 >>> from sympy.abc import a, b, c 

497 >>> corners = (a, b, c) 

498 >>> faces = [(0, 1, 2)] 

499 >>> Polyhedron(corners, faces).edges 

500 {(0, 1), (0, 2), (1, 2)} 

501 

502 """ 

503 if self._edges is None: 

504 output = set() 

505 for face in self.faces: 

506 for i in range(len(face)): 

507 edge = tuple(sorted([face[i], face[i - 1]])) 

508 output.add(edge) 

509 self._edges = FiniteSet(*output) 

510 return self._edges 

511 

512 def rotate(self, perm): 

513 """ 

514 Apply a permutation to the polyhedron *in place*. The permutation 

515 may be given as a Permutation instance or an integer indicating 

516 which permutation from pgroup of the Polyhedron should be 

517 applied. 

518 

519 This is an operation that is analogous to rotation about 

520 an axis by a fixed increment. 

521 

522 Notes 

523 ===== 

524 

525 When a Permutation is applied, no check is done to see if that 

526 is a valid permutation for the Polyhedron. For example, a cube 

527 could be given a permutation which effectively swaps only 2 

528 vertices. A valid permutation (that rotates the object in a 

529 physical way) will be obtained if one only uses 

530 permutations from the ``pgroup`` of the Polyhedron. On the other 

531 hand, allowing arbitrary rotations (applications of permutations) 

532 gives a way to follow named elements rather than indices since 

533 Polyhedron allows vertices to be named while Permutation works 

534 only with indices. 

535 

536 Examples 

537 ======== 

538 

539 >>> from sympy.combinatorics import Polyhedron, Permutation 

540 >>> from sympy.combinatorics.polyhedron import cube 

541 >>> cube = cube.copy() 

542 >>> cube.corners 

543 (0, 1, 2, 3, 4, 5, 6, 7) 

544 >>> cube.rotate(0) 

545 >>> cube.corners 

546 (1, 2, 3, 0, 5, 6, 7, 4) 

547 

548 A non-physical "rotation" that is not prohibited by this method: 

549 

550 >>> cube.reset() 

551 >>> cube.rotate(Permutation([[1, 2]], size=8)) 

552 >>> cube.corners 

553 (0, 2, 1, 3, 4, 5, 6, 7) 

554 

555 Polyhedron can be used to follow elements of set that are 

556 identified by letters instead of integers: 

557 

558 >>> shadow = h5 = Polyhedron(list('abcde')) 

559 >>> p = Permutation([3, 0, 1, 2, 4]) 

560 >>> h5.rotate(p) 

561 >>> h5.corners 

562 (d, a, b, c, e) 

563 >>> _ == shadow.corners 

564 True 

565 >>> copy = h5.copy() 

566 >>> h5.rotate(p) 

567 >>> h5.corners == copy.corners 

568 False 

569 """ 

570 if not isinstance(perm, Perm): 

571 perm = self.pgroup[perm] 

572 # and we know it's valid 

573 else: 

574 if perm.size != self.size: 

575 raise ValueError('Polyhedron and Permutation sizes differ.') 

576 a = perm.array_form 

577 corners = [self.corners[a[i]] for i in range(len(self.corners))] 

578 self._corners = tuple(corners) 

579 

580 def reset(self): 

581 """Return corners to their original positions. 

582 

583 Examples 

584 ======== 

585 

586 >>> from sympy.combinatorics.polyhedron import tetrahedron as T 

587 >>> T = T.copy() 

588 >>> T.corners 

589 (0, 1, 2, 3) 

590 >>> T.rotate(0) 

591 >>> T.corners 

592 (0, 2, 3, 1) 

593 >>> T.reset() 

594 >>> T.corners 

595 (0, 1, 2, 3) 

596 """ 

597 self._corners = self.args[0] 

598 

599 

600def _pgroup_calcs(): 

601 """Return the permutation groups for each of the polyhedra and the face 

602 definitions: tetrahedron, cube, octahedron, dodecahedron, icosahedron, 

603 tetrahedron_faces, cube_faces, octahedron_faces, dodecahedron_faces, 

604 icosahedron_faces 

605 

606 Explanation 

607 =========== 

608 

609 (This author did not find and did not know of a better way to do it though 

610 there likely is such a way.) 

611 

612 Although only 2 permutations are needed for a polyhedron in order to 

613 generate all the possible orientations, a group of permutations is 

614 provided instead. A set of permutations is called a "group" if:: 

615 

616 a*b = c (for any pair of permutations in the group, a and b, their 

617 product, c, is in the group) 

618 

619 a*(b*c) = (a*b)*c (for any 3 permutations in the group associativity holds) 

620 

621 there is an identity permutation, I, such that I*a = a*I for all elements 

622 in the group 

623 

624 a*b = I (the inverse of each permutation is also in the group) 

625 

626 None of the polyhedron groups defined follow these definitions of a group. 

627 Instead, they are selected to contain those permutations whose powers 

628 alone will construct all orientations of the polyhedron, i.e. for 

629 permutations ``a``, ``b``, etc... in the group, ``a, a**2, ..., a**o_a``, 

630 ``b, b**2, ..., b**o_b``, etc... (where ``o_i`` is the order of 

631 permutation ``i``) generate all permutations of the polyhedron instead of 

632 mixed products like ``a*b``, ``a*b**2``, etc.... 

633 

634 Note that for a polyhedron with n vertices, the valid permutations of the 

635 vertices exclude those that do not maintain its faces. e.g. the 

636 permutation BCDE of a square's four corners, ABCD, is a valid 

637 permutation while CBDE is not (because this would twist the square). 

638 

639 Examples 

640 ======== 

641 

642 The is_group checks for: closure, the presence of the Identity permutation, 

643 and the presence of the inverse for each of the elements in the group. This 

644 confirms that none of the polyhedra are true groups: 

645 

646 >>> from sympy.combinatorics.polyhedron import ( 

647 ... tetrahedron, cube, octahedron, dodecahedron, icosahedron) 

648 ... 

649 >>> polyhedra = (tetrahedron, cube, octahedron, dodecahedron, icosahedron) 

650 >>> [h.pgroup.is_group for h in polyhedra] 

651 ... 

652 [True, True, True, True, True] 

653 

654 Although tests in polyhedron's test suite check that powers of the 

655 permutations in the groups generate all permutations of the vertices 

656 of the polyhedron, here we also demonstrate the powers of the given 

657 permutations create a complete group for the tetrahedron: 

658 

659 >>> from sympy.combinatorics import Permutation, PermutationGroup 

660 >>> for h in polyhedra[:1]: 

661 ... G = h.pgroup 

662 ... perms = set() 

663 ... for g in G: 

664 ... for e in range(g.order()): 

665 ... p = tuple((g**e).array_form) 

666 ... perms.add(p) 

667 ... 

668 ... perms = [Permutation(p) for p in perms] 

669 ... assert PermutationGroup(perms).is_group 

670 

671 In addition to doing the above, the tests in the suite confirm that the 

672 faces are all present after the application of each permutation. 

673 

674 References 

675 ========== 

676 

677 .. [1] https://dogschool.tripod.com/trianglegroup.html 

678 

679 """ 

680 def _pgroup_of_double(polyh, ordered_faces, pgroup): 

681 n = len(ordered_faces[0]) 

682 # the vertices of the double which sits inside a give polyhedron 

683 # can be found by tracking the faces of the outer polyhedron. 

684 # A map between face and the vertex of the double is made so that 

685 # after rotation the position of the vertices can be located 

686 fmap = dict(zip(ordered_faces, 

687 range(len(ordered_faces)))) 

688 flat_faces = flatten(ordered_faces) 

689 new_pgroup = [] 

690 for i, p in enumerate(pgroup): 

691 h = polyh.copy() 

692 h.rotate(p) 

693 c = h.corners 

694 # reorder corners in the order they should appear when 

695 # enumerating the faces 

696 reorder = unflatten([c[j] for j in flat_faces], n) 

697 # make them canonical 

698 reorder = [tuple(map(as_int, 

699 minlex(f, directed=False))) 

700 for f in reorder] 

701 # map face to vertex: the resulting list of vertices are the 

702 # permutation that we seek for the double 

703 new_pgroup.append(Perm([fmap[f] for f in reorder])) 

704 return new_pgroup 

705 

706 tetrahedron_faces = [ 

707 (0, 1, 2), (0, 2, 3), (0, 3, 1), # upper 3 

708 (1, 2, 3), # bottom 

709 ] 

710 

711 # cw from top 

712 # 

713 _t_pgroup = [ 

714 Perm([[1, 2, 3], [0]]), # cw from top 

715 Perm([[0, 1, 2], [3]]), # cw from front face 

716 Perm([[0, 3, 2], [1]]), # cw from back right face 

717 Perm([[0, 3, 1], [2]]), # cw from back left face 

718 Perm([[0, 1], [2, 3]]), # through front left edge 

719 Perm([[0, 2], [1, 3]]), # through front right edge 

720 Perm([[0, 3], [1, 2]]), # through back edge 

721 ] 

722 

723 tetrahedron = Polyhedron( 

724 range(4), 

725 tetrahedron_faces, 

726 _t_pgroup) 

727 

728 cube_faces = [ 

729 (0, 1, 2, 3), # upper 

730 (0, 1, 5, 4), (1, 2, 6, 5), (2, 3, 7, 6), (0, 3, 7, 4), # middle 4 

731 (4, 5, 6, 7), # lower 

732 ] 

733 

734 # U, D, F, B, L, R = up, down, front, back, left, right 

735 _c_pgroup = [Perm(p) for p in 

736 [ 

737 [1, 2, 3, 0, 5, 6, 7, 4], # cw from top, U 

738 [4, 0, 3, 7, 5, 1, 2, 6], # cw from F face 

739 [4, 5, 1, 0, 7, 6, 2, 3], # cw from R face 

740 

741 [1, 0, 4, 5, 2, 3, 7, 6], # cw through UF edge 

742 [6, 2, 1, 5, 7, 3, 0, 4], # cw through UR edge 

743 [6, 7, 3, 2, 5, 4, 0, 1], # cw through UB edge 

744 [3, 7, 4, 0, 2, 6, 5, 1], # cw through UL edge 

745 [4, 7, 6, 5, 0, 3, 2, 1], # cw through FL edge 

746 [6, 5, 4, 7, 2, 1, 0, 3], # cw through FR edge 

747 

748 [0, 3, 7, 4, 1, 2, 6, 5], # cw through UFL vertex 

749 [5, 1, 0, 4, 6, 2, 3, 7], # cw through UFR vertex 

750 [5, 6, 2, 1, 4, 7, 3, 0], # cw through UBR vertex 

751 [7, 4, 0, 3, 6, 5, 1, 2], # cw through UBL 

752 ]] 

753 

754 cube = Polyhedron( 

755 range(8), 

756 cube_faces, 

757 _c_pgroup) 

758 

759 octahedron_faces = [ 

760 (0, 1, 2), (0, 2, 3), (0, 3, 4), (0, 1, 4), # top 4 

761 (1, 2, 5), (2, 3, 5), (3, 4, 5), (1, 4, 5), # bottom 4 

762 ] 

763 

764 octahedron = Polyhedron( 

765 range(6), 

766 octahedron_faces, 

767 _pgroup_of_double(cube, cube_faces, _c_pgroup)) 

768 

769 dodecahedron_faces = [ 

770 (0, 1, 2, 3, 4), # top 

771 (0, 1, 6, 10, 5), (1, 2, 7, 11, 6), (2, 3, 8, 12, 7), # upper 5 

772 (3, 4, 9, 13, 8), (0, 4, 9, 14, 5), 

773 (5, 10, 16, 15, 14), (6, 10, 16, 17, 11), (7, 11, 17, 18, 

774 12), # lower 5 

775 (8, 12, 18, 19, 13), (9, 13, 19, 15, 14), 

776 (15, 16, 17, 18, 19) # bottom 

777 ] 

778 

779 def _string_to_perm(s): 

780 rv = [Perm(range(20))] 

781 p = None 

782 for si in s: 

783 if si not in '01': 

784 count = int(si) - 1 

785 else: 

786 count = 1 

787 if si == '0': 

788 p = _f0 

789 elif si == '1': 

790 p = _f1 

791 rv.extend([p]*count) 

792 return Perm.rmul(*rv) 

793 

794 # top face cw 

795 _f0 = Perm([ 

796 1, 2, 3, 4, 0, 6, 7, 8, 9, 5, 11, 

797 12, 13, 14, 10, 16, 17, 18, 19, 15]) 

798 # front face cw 

799 _f1 = Perm([ 

800 5, 0, 4, 9, 14, 10, 1, 3, 13, 15, 

801 6, 2, 8, 19, 16, 17, 11, 7, 12, 18]) 

802 # the strings below, like 0104 are shorthand for F0*F1*F0**4 and are 

803 # the remaining 4 face rotations, 15 edge permutations, and the 

804 # 10 vertex rotations. 

805 _dodeca_pgroup = [_f0, _f1] + [_string_to_perm(s) for s in ''' 

806 0104 140 014 0410 

807 010 1403 03104 04103 102 

808 120 1304 01303 021302 03130 

809 0412041 041204103 04120410 041204104 041204102 

810 10 01 1402 0140 04102 0412 1204 1302 0130 03120'''.strip().split()] 

811 

812 dodecahedron = Polyhedron( 

813 range(20), 

814 dodecahedron_faces, 

815 _dodeca_pgroup) 

816 

817 icosahedron_faces = [ 

818 (0, 1, 2), (0, 2, 3), (0, 3, 4), (0, 4, 5), (0, 1, 5), 

819 (1, 6, 7), (1, 2, 7), (2, 7, 8), (2, 3, 8), (3, 8, 9), 

820 (3, 4, 9), (4, 9, 10), (4, 5, 10), (5, 6, 10), (1, 5, 6), 

821 (6, 7, 11), (7, 8, 11), (8, 9, 11), (9, 10, 11), (6, 10, 11)] 

822 

823 icosahedron = Polyhedron( 

824 range(12), 

825 icosahedron_faces, 

826 _pgroup_of_double( 

827 dodecahedron, dodecahedron_faces, _dodeca_pgroup)) 

828 

829 return (tetrahedron, cube, octahedron, dodecahedron, icosahedron, 

830 tetrahedron_faces, cube_faces, octahedron_faces, 

831 dodecahedron_faces, icosahedron_faces) 

832 

833# ----------------------------------------------------------------------- 

834# Standard Polyhedron groups 

835# 

836# These are generated using _pgroup_calcs() above. However to save 

837# import time we encode them explicitly here. 

838# ----------------------------------------------------------------------- 

839 

840tetrahedron = Polyhedron( 

841 Tuple(0, 1, 2, 3), 

842 Tuple( 

843 Tuple(0, 1, 2), 

844 Tuple(0, 2, 3), 

845 Tuple(0, 1, 3), 

846 Tuple(1, 2, 3)), 

847 Tuple( 

848 Perm(1, 2, 3), 

849 Perm(3)(0, 1, 2), 

850 Perm(0, 3, 2), 

851 Perm(0, 3, 1), 

852 Perm(0, 1)(2, 3), 

853 Perm(0, 2)(1, 3), 

854 Perm(0, 3)(1, 2) 

855 )) 

856 

857cube = Polyhedron( 

858 Tuple(0, 1, 2, 3, 4, 5, 6, 7), 

859 Tuple( 

860 Tuple(0, 1, 2, 3), 

861 Tuple(0, 1, 5, 4), 

862 Tuple(1, 2, 6, 5), 

863 Tuple(2, 3, 7, 6), 

864 Tuple(0, 3, 7, 4), 

865 Tuple(4, 5, 6, 7)), 

866 Tuple( 

867 Perm(0, 1, 2, 3)(4, 5, 6, 7), 

868 Perm(0, 4, 5, 1)(2, 3, 7, 6), 

869 Perm(0, 4, 7, 3)(1, 5, 6, 2), 

870 Perm(0, 1)(2, 4)(3, 5)(6, 7), 

871 Perm(0, 6)(1, 2)(3, 5)(4, 7), 

872 Perm(0, 6)(1, 7)(2, 3)(4, 5), 

873 Perm(0, 3)(1, 7)(2, 4)(5, 6), 

874 Perm(0, 4)(1, 7)(2, 6)(3, 5), 

875 Perm(0, 6)(1, 5)(2, 4)(3, 7), 

876 Perm(1, 3, 4)(2, 7, 5), 

877 Perm(7)(0, 5, 2)(3, 4, 6), 

878 Perm(0, 5, 7)(1, 6, 3), 

879 Perm(0, 7, 2)(1, 4, 6))) 

880 

881octahedron = Polyhedron( 

882 Tuple(0, 1, 2, 3, 4, 5), 

883 Tuple( 

884 Tuple(0, 1, 2), 

885 Tuple(0, 2, 3), 

886 Tuple(0, 3, 4), 

887 Tuple(0, 1, 4), 

888 Tuple(1, 2, 5), 

889 Tuple(2, 3, 5), 

890 Tuple(3, 4, 5), 

891 Tuple(1, 4, 5)), 

892 Tuple( 

893 Perm(5)(1, 2, 3, 4), 

894 Perm(0, 4, 5, 2), 

895 Perm(0, 1, 5, 3), 

896 Perm(0, 1)(2, 4)(3, 5), 

897 Perm(0, 2)(1, 3)(4, 5), 

898 Perm(0, 3)(1, 5)(2, 4), 

899 Perm(0, 4)(1, 3)(2, 5), 

900 Perm(0, 5)(1, 4)(2, 3), 

901 Perm(0, 5)(1, 2)(3, 4), 

902 Perm(0, 4, 1)(2, 3, 5), 

903 Perm(0, 1, 2)(3, 4, 5), 

904 Perm(0, 2, 3)(1, 5, 4), 

905 Perm(0, 4, 3)(1, 5, 2))) 

906 

907dodecahedron = Polyhedron( 

908 Tuple(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19), 

909 Tuple( 

910 Tuple(0, 1, 2, 3, 4), 

911 Tuple(0, 1, 6, 10, 5), 

912 Tuple(1, 2, 7, 11, 6), 

913 Tuple(2, 3, 8, 12, 7), 

914 Tuple(3, 4, 9, 13, 8), 

915 Tuple(0, 4, 9, 14, 5), 

916 Tuple(5, 10, 16, 15, 14), 

917 Tuple(6, 10, 16, 17, 11), 

918 Tuple(7, 11, 17, 18, 12), 

919 Tuple(8, 12, 18, 19, 13), 

920 Tuple(9, 13, 19, 15, 14), 

921 Tuple(15, 16, 17, 18, 19)), 

922 Tuple( 

923 Perm(0, 1, 2, 3, 4)(5, 6, 7, 8, 9)(10, 11, 12, 13, 14)(15, 16, 17, 18, 19), 

924 Perm(0, 5, 10, 6, 1)(2, 4, 14, 16, 11)(3, 9, 15, 17, 7)(8, 13, 19, 18, 12), 

925 Perm(0, 10, 17, 12, 3)(1, 6, 11, 7, 2)(4, 5, 16, 18, 8)(9, 14, 15, 19, 13),