cl-permutation / README

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)
#<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. The companion function PERM-TO-LIST does the
opposite operation, but it's not recommended to use list
representations of permutations.

One can also create permutations with WORD-TO-PERM, which is analogous
to LIST-TO-PERM, except it works for words, which are conventionally
arrays. The reverse is PERM-TO-WORD.

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-inverse-eval : one-based (standard) reference of inverse
perm-inverse-eval* : one-based (standard) reference of inverse 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
perm-fixpoints : compute the fixed points of 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: #<PERM 1 2 3>
2: #<PERM 1 3 2>
3: #<PERM 3 1 2>
4: #<PERM 3 2 1>
5: #<PERM 2 3 1>
6: #<PERM 2 1 3>

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 1 2> #<PERM 1 2 3>)
PERM> (list (funcall S2) (funcall S3))
(#<PERM 2 1> #<PERM 1 3 2>)
PERM> (list (funcall S2) (funcall S3))
(NIL #<PERM 3 1 2>)
PERM> (list (funcall S2) (funcall S3))
(NIL #<PERM 3 2 1>)
PERM> (list (funcall S2) (funcall S3))
(NIL #<PERM 2 3 1>)


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 3 1 2>
PERM> (from-cycles '((1 3 2)) 5)
#<PERM 3 1 2 4 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-PERM-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 of 2 generators>
PERM> (group-from '((1 3 2 4)
                    (3 2 4 1)))
#<PERM-GROUP of 2 generators>

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 of 2 generators>

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
#<PERM-GROUP of 6 generators>
      
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)
#<PERM 1 20 24 39 12 40 29 41 9 47 46 21 45 11 34 8 14 36 22 31 44 25 10 48
       16 37 43 15 26 32 7 33 30 13 35 5 28 27 23 17 19 4 38 2 18 6 42 3>

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.
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.