Commits

Robert Smith committed aba7349

Update documentation.

  • Participants
  • Parent commits df04792

Comments (0)

Files changed (2)

 Cycle Operations
 ----------------
 
-XXX: THIS IS OUT OF DATE!
-
-There's also a number of operations for cycles. Cycles are just
-represented as Lisp lists. We can convert to and from cycle
+There's also a number of operations for cycles. Cycles are represented
+by the CYCLE structure. We can convert to and from cycle
 representation using TO-CYCLES and FROM-CYCLES. Cycles created by
-TO-CYCLES are automatically normalized with
-NORMALIZE-CYCLES. Normalization is defined as:
+TO-CYCLES are automatically canonicalized with
+CANONICALIZE-CYCLES. Canonicalization is defined as:
 
   * No fixed points.
   * Cycles contain their least element first.
   * Cycle length is descending.
   * For cycles of equal length, order by ascending first elements.
 
+Cycles that have not been canonicalized are printed with an
+asterisk. We can observe this by explicitly disabling cycle
+canonicalization:
+
+PERM> (make-cycle 3 1)
+#<CYCLE (1 3)>
+PERM> (let ((*canonicalize-cycle-on-creation* nil))
+        (make-cycle 3 1))
+#<CYCLE (3 1)*>
+
+An example use of TO-CYCLES is as follows:
+
+PERM> (let ((r (random-perm 10)))
+        (values r (to-cycles r)))
+#<PERM 7 1 6 9 10 8 2 3 5 4>
+(#<CYCLE (4 9 5 10)> #<CYCLE (1 7 2)> #<CYCLE (3 6 8)>)
+
 FROM-CYCLES allows the specification of the permutation's length. For example:
 
-PERM> (from-cycles '((1 3 2)))
+PERM> (from-cycles (list (make-cycle 1 3 2)))
 #<PERM 3 1 2>
-PERM> (from-cycles '((1 3 2)) 5)
+PERM> (from-cycles (list (make-cycle 1 3 2)) 5)
 #<PERM 3 1 2 4 5>
 
 Lastly, there is a (mostly useless) function CYCLES-TO-ONE-LINE which
 
    12345.
 
+For example,
+
+PERM> (cycles-to-one-line (list (make-cycle 1 2 3)
+                                (make-cycle 4 5)))
+#<PERM 1 2 3 4 5>
+
 Let me know if you find a good use.
 
-As of now, the error checking in cycle code is dismal.
-
 
 Permutation Groups
 ------------------
 We can generate a permutation group from a list of cycles as well. The
 above is equivalent to
 
-PERM> (group-from-cycles '(((2 3))
-                           ((1 3 4))) 4) 
+PERM> (group-from-cycles (list (list (make-cycle 2 3))
+                               (list (make-cycle 1 3 4)))
+                         4) 
 #<PERM-GROUP of 2 generators>
 
 Once we have generated a group, we can do some operations on it.
 And as cycles...
 
 PERM> (to-cycles *)
-((2 20 31 7 29 26 37 28 15 34 13 45 18 36 5 12 21 44) (4 39 23 10 47 42)
- (6 40 17 14 11 46) (8 41 19 22 25 16) (3 24 48) (27 43 38) (30 32 33))
+(#<CYCLE (2 20 31 7 29 26 37 28 15 34 13 45 18 36 5 12 21 44)>
+ #<CYCLE (4 39 23 10 47 42)>
+ #<CYCLE (6 40 17 14 11 46)>
+ #<CYCLE (8 41 19 22 25 16)>
+ #<CYCLE (3 24 48)>
+ #<CYCLE (27 43 38)>
+ #<CYCLE (30 32 33)>)
 
 Let's check if flipping an edge piece is valid:
 
 
 No it's not. How about four edge pieces?
 
-PERM> (group-element-p (from-cycles '((7 18) (2 34) (4 10) (5 26)) 48) rubik-3x3)
+PERM> (group-element-p (from-cycles (list (make-cycle 7 18)
+                                          (make-cycle 2 34)
+                                          (make-cycle 4 10)
+                                          (make-cycle 5 26))
+                                    48)
+                       rubik-3x3)
 T
 
 As can be seen, the few operations we have are powerful in studying

permutation-group-examples.lisp

              (from-cycles cycles 200)))
     (generate-perm-group
      (list
-      (cyc '(1 9 7 5 3)
-           '(50 40 30 200 11)
-           '(52 42 32 22 13)
-           '(2 10 8 6 4)
-           '(51 41 31 21 12))
-      (cyc '(11 13 15 17 19)
-           '(3 200 72 62 54)
-           '(5 28 70 60 52)
-           '(12 14 16 18 20)
-           '(4 29 71 61 53))
-      (cyc '(200 22 24 26 28)
-           '(5 30 82 74 15)
-           '(7 38 80 72 13)
-           '(21 23 25 27 29)
-           '(6 39 81 73 14))
-      (cyc '(30 32 34 36 38)
-           '(7 40 92 84 24)
-           '(9 48 90 82 22)
-           '(31 33 35 37 39)
-           '(8 49 91 83 23))
-      (cyc '(40 42 44 46 48)
-           '(9 50 114 94 34)
-           '(1 58 112 92 32)
-           '(41 43 45 47 49)
-           '(10 59 113 93 33))
-      (cyc '(50 52 54 56 58)
-           '(1 11 60 116 44)
-           '(3 19 68 114 42)
-           '(51 53 55 57 59)
-           '(2 20 69 115 43))
-      (cyc '(60 62 64 66 68)
-           '(19 70 106 118 56)
-           '(17 78 104 116 54)
-           '(61 63 65 67 69)
-           '(18 79 105 117 55))
-      (cyc '(70 72 74 76 78)
-           '(17 28 80 108 64)
-           '(15 26 88 106 62)
-           '(71 73 75 77 79)
-           '(16 27 89 107 63))
-      (cyc '(80 82 84 86 88)
-           '(26 38 90 100 76)
-           '(24 36 98 108 74)
-           '(81 83 85 87 89)
-           '(25 37 99 109 75))
-      (cyc '(90 92 94 96 98)
-           '(36 48 112 102 86)
-           '(34 46 110 100 84)
-           '(91 93 95 97 99)
-           '(35 47 111 101 85))
-      (cyc '(100 102 104 106 108)
-           '(98 110 66 78 88)
-           '(96 118 64 76 86)
-           '(101 103 105 107 109)
-           '(97 119 65 77 87))
-      (cyc '(110 112 114 116 118)
-           '(96 46 58 68 104)
-           '(94 44 56 66 102)
-           '(111 113 115 117 119)
-           '(95 45 57 67 103))))))
+      (cyc (make-cycle 1 9 7 5 3)
+           (make-cycle 50 40 30 200 11)
+           (make-cycle 52 42 32 22 13)
+           (make-cycle 2 10 8 6 4)
+           (make-cycle 51 41 31 21 12))
+      (cyc (make-cycle 11 13 15 17 19)
+           (make-cycle 3 200 72 62 54)
+           (make-cycle 5 28 70 60 52)
+           (make-cycle 12 14 16 18 20)
+           (make-cycle 4 29 71 61 53))
+      (cyc (make-cycle 200 22 24 26 28)
+           (make-cycle 5 30 82 74 15)
+           (make-cycle 7 38 80 72 13)
+           (make-cycle 21 23 25 27 29)
+           (make-cycle 6 39 81 73 14))
+      (cyc (make-cycle 30 32 34 36 38)
+           (make-cycle 7 40 92 84 24)
+           (make-cycle 9 48 90 82 22)
+           (make-cycle 31 33 35 37 39)
+           (make-cycle 8 49 91 83 23))
+      (cyc (make-cycle 40 42 44 46 48)
+           (make-cycle 9 50 114 94 34)
+           (make-cycle 1 58 112 92 32)
+           (make-cycle 41 43 45 47 49)
+           (make-cycle 10 59 113 93 33))
+      (cyc (make-cycle 50 52 54 56 58)
+           (make-cycle 1 11 60 116 44)
+           (make-cycle 3 19 68 114 42)
+           (make-cycle 51 53 55 57 59)
+           (make-cycle 2 20 69 115 43))
+      (cyc (make-cycle 60 62 64 66 68)
+           (make-cycle 19 70 106 118 56)
+           (make-cycle 17 78 104 116 54)
+           (make-cycle 61 63 65 67 69)
+           (make-cycle 18 79 105 117 55))
+      (cyc (make-cycle 70 72 74 76 78)
+           (make-cycle 17 28 80 108 64)
+           (make-cycle 15 26 88 106 62)
+           (make-cycle 71 73 75 77 79)
+           (make-cycle 16 27 89 107 63))
+      (cyc (make-cycle 80 82 84 86 88)
+           (make-cycle 26 38 90 100 76)
+           (make-cycle 24 36 98 108 74)
+           (make-cycle 81 83 85 87 89)
+           (make-cycle 25 37 99 109 75))
+      (cyc (make-cycle 90 92 94 96 98)
+           (make-cycle 36 48 112 102 86)
+           (make-cycle 34 46 110 100 84)
+           (make-cycle 91 93 95 97 99)
+           (make-cycle 35 47 111 101 85))
+      (cyc (make-cycle 100 102 104 106 108)
+           (make-cycle 98 110 66 78 88)
+           (make-cycle 96 118 64 76 86)
+           (make-cycle 101 103 105 107 109)
+           (make-cycle 97 119 65 77 87))
+      (cyc (make-cycle 110 112 114 116 118)
+           (make-cycle 96 46 58 68 104)
+           (make-cycle 94 44 56 66 102)
+           (make-cycle 111 113 115 117 119)
+           (make-cycle 95 45 57 67 103))))))