# Source

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261``` ```CL-PERMUTATION ============== A library for operating on permutations and permutation groups. NOTES ===== Creating Permutations --------------------- Permutations are represented by the structure PERM, which is read-only/immutable. A permutation of size N is essentially a sequence of numbers from 1 to N. One-based permutations was chosen because that is the dominating convention in mathematics. All we lose, essentially, is direct compatibility with array indexing, and one fixnum worth of space (internally, the permutations are stored in an array of size N+1, where the zeroth element is always zero). A permutation can be created via MAKE-PERM: PERM> (make-perm 1 2 3) # The permutation will be checked for validity. PERM> (make-perm 1 2 5) Given permutation must contain the numbers 1 to 3 [Condition of type SIMPLE-ERROR] One can also create permutations with LIST-TO-PERM, which converts a list to a permutation. Lastly, there is an experimental reader macro for permutations, which are created at read time. To enable the syntax, use (enable-perm-reader) and then one may type #[3 1 2 4 5] for permutations instead. Permutation Operations ---------------------- There is a slew of permutation operations: perm-identity : construct an identity perm perm-identity-p : check if a perm is an identity perm random-perm : construct a random perm with specified parity perm-ref : zero-based reference perm-eval : one-based (standard) reference perm-eval* : one-based (standard) reference with out-of-bounds handling perm-size : the size of the permutation (number of mapped elements) perm-length : number of inversions perm-even-p | perm-odd-p : check for evenness/oddness perm-sign | perm-compose : compose two permutations perm-expt : compose a perm with itself a number of times perm-order : order of a permutation perm-transpose-indexes : swap two indexes, keeping the entries fixed perm-transpose-entries : swap two entries, keeping the indexes fixed perm-inverse : invert a permutation permute : permute an array according to a permutation Permutation Generation ---------------------- There are ways of efficiently generating all permutations of a given length incrementally. Instead of generating all permutations at once in memory -- which takes O(n*n!) space -- we generate permutations on the fly. The first way is to iterate over the permutations using a DOLIST-style macro called DOPERMS. PERM> (let ((i 1)) (doperms (p 3) (format t "~D: ~A~%" i p) (incf i))) 1: # 2: # 3: # 4: # 5: # 6: # The other way is to produce a generator object (a closure, in fact) which generates the permutations. Simply FUNCALL the object to receive the next permutation. When they're all exhausted, the closure will return NIL. PERM> (defparameter S3 (make-perm-generator 3)) S3 PERM> (defparameter S2 (make-perm-generator 2)) S2 PERM> (list (funcall S2) (funcall S3)) (# #) PERM> (list (funcall S2) (funcall S3)) (# #) PERM> (list (funcall S2) (funcall S3)) (NIL #) PERM> (list (funcall S2) (funcall S3)) (NIL #) PERM> (list (funcall S2) (funcall S3)) (NIL #) Cycle Operations ---------------- There's also a number of operations for cycles. Cycles are just represented as Lisp lists. 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: * No fixed points. * Cycles contain their least element first. * Cycle length is descending. * For cycles of equal length, order by ascending first elements. FROM-CYCLES allows the specification of the permutation's length. For example: PERM> (from-cycles '((1 3 2))) # PERM> (from-cycles '((1 3 2)) 5) # Lastly, there is a (mostly useless) function CYCLES-TO-ONE-LINE which converts cycles to one-line notation. That is, the cycles (1 2 3)(4 5) gets converted to the permutation 12345. Let me know if you find a good use. As of now, the error checking in cycle code is dismal. Permutation Groups ------------------ There is initial support for permutation groups at the moment. Permutation groups are represented by the structure PERM-GROUP. We can create a permutation group from its generators via GENERATE-PERMUTATION-GROUP. A shorthand syntax is provided which, instead of taking a list of PERM objects, takes a list of lists representing perms. This shorthand is GROUP-FROM. For example, the following two are the same group: PERM> (generate-perm-group (list (make-perm 1 3 2 4) (make-perm 3 2 4 1))) # PERM> (group-from '((1 3 2 4) (3 2 4 1))) # 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) # Once we have generated a group, we can do some operations on it. For example, let's define the group for 3x3 Rubik's cubes. A cube has six moves: we can turn the front, back, left, right, top, and bottom. Label each sticker with a number like so: +--------------+ | | | 1 2 3 | | | | 4 up 5 | | | | 6 7 8 | | | +--------------+--------------+--------------+--------------+ | | | | | | 9 10 11 | 17 18 19 | 25 26 27 | 33 34 35 | | | | | | | 12 left 13 | 20 front 21 | 28 right 29 | 36 back 37 | | | | | | | 14 15 16 | 22 23 24 | 30 31 32 | 38 39 40 | | | | | | +--------------+--------------+--------------+--------------+ | | | 41 42 43 | | | | 44 down 45 | | | | 46 47 48 | | | +--------------+ Each turn corresponds to a permutation of stickers. I'll do the hard work of specifying them: (defparameter rubik-3x3 (group-from '((3 5 8 2 7 1 4 6 33 34 35 12 13 14 15 16 9 10 11 20 21 22 23 24 17 18 19 28 29 30 31 32 25 26 27 36 37 38 39 40 41 42 43 44 45 46 47 48) (17 2 3 20 5 22 7 8 11 13 16 10 15 9 12 14 41 18 19 44 21 46 23 24 25 26 27 28 29 30 31 32 33 34 6 36 4 38 39 1 40 42 43 37 45 35 47 48) (1 2 3 4 5 25 28 30 9 10 8 12 7 14 15 6 19 21 24 18 23 17 20 22 43 26 27 42 29 41 31 32 33 34 35 36 37 38 39 40 11 13 16 44 45 46 47 48) (1 2 38 4 36 6 7 33 9 10 11 12 13 14 15 16 17 18 3 20 5 22 23 8 27 29 32 26 31 25 28 30 48 34 35 45 37 43 39 40 41 42 19 44 21 46 47 24) (14 12 9 4 5 6 7 8 46 10 11 47 13 48 15 16 17 18 19 20 21 22 23 24 25 26 1 28 2 30 31 3 35 37 40 34 39 33 36 38 41 42 43 44 45 32 29 27) (1 2 3 4 5 6 7 8 9 10 11 12 13 22 23 24 17 18 19 20 21 30 31 32 25 26 27 28 29 38 39 40 33 34 35 36 37 14 15 16 43 45 48 42 47 41 44 46)))) Now we have our group: PERM> rubik-3x3 # Let's query the group's order: PERM> (group-order rubik-3x3) 43252003274489856000 A lot of positions! Let's generate a random cube: PERM> (random-group-element rubik-3x3) # 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)) Let's check if flipping an edge piece is valid: PERM> (group-element-p (from-cycles '((7 18)) 48) rubik-3x3) NIL 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) T As can be seen, the few operations we have are powerful in studying finite groups. ```