Overview

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= : check for equality
perm=* : check for equality of different sized perms
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 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 canonicalized with
CANONICALIZE-CYCLES. Canonicalization is defined as:

  * Cycles contain their least element positionally first.
  * Cycles are listed in descending order of their first element.
  * No null cycles exist.
  * The sum of the cycle lengths of a decomposition of a permutation
    of size N is N.

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 4 8 5 2 10 3 9 1 6>
(#<CYCLE (6 10)> #<CYCLE (2 4 5)> #<CYCLE (1 7 3 8 9)>)

FROM-CYCLES allows the specification of the permutation's length. For example:

PERM> (from-cycles (list (make-cycle 1 3 2)))
#<PERM 3 1 2>
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
converts cycles to one-line notation. That is, the cycles

   (1 2 3)(4 5)

gets converted to the permutation

   12345.

For example,

PERM> (cycles-to-one-line (list (make-cycle 1 2 3)
                                (make-cycle 4 5)))
#<PERM 1 2 3 4 5>

If one takes a permutation which has been canonically decomposed into
cycles, then interestingly, there exists a bijection between one-line
notation and the cycle decomposition.


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 (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.

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

Let's check if flipping an edge piece is valid:

PERM> (group-element-p (from-cycles (list (make-cycle 7 18)) 48) rubik-3x3)
NIL

No it's not. How about four edge pieces?

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
finite groups.